Графы: семестровая работа

Графы, пример семестровой (вариант № 16)

Содержит: методы задания графа( графически, списком, матрицей инцинденции, матрицей смежности), идентификация графа (его описание: планарный или нет, связен/несвязен и т.п.), характеристики графа(сумма всех рёбер,  цикломатическое число графа и т.п.), эйлеровость, гамильтовость, правильная раскраска графа (вершинная и рёберная), топологическая декомпозиция графа.

Фрагменты:

а) Графически:   (изменим исходный граф, передвинув узлы так, что бы визуальное представление стало легче и проименуем все  дуги и вершины)

б) Списком:

• Вершины: {1, 2, 3, 4, 5, 6, 7, 8, 9 , 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36}
• Дуги:  { (1,2); (2,3); (2,4); (2,5); (3,6); (3,7); (4,8); (4,9); (5,10); (5,11); (6,16); (7,12); (8,13); (9,14); (10,20); (11,15); (12,17); (13,18); (14,19); (15,21); (22,23); (22,36); (23,24); (23,25); (23,26); (24,29); (23,30); (25,27); (26,32); (26,33); (26,34); (26,28); (27,31); (28,35) }

в) Матрицей смежности: ...

г) Матрицей инцинденции: ...

• Не пустой граф, т.к. присутствуют дуги.
• Является орграфом, так как в нём имеются только  дуги, имеющие направление (нет ни одного ребра).
• Это неполный орграф, так как не любые две вершины соединены парами дуг в каждом направлении.
• Это не мультиграф, потому что нет ни одного повторения элементов во множестве дуг.
• Не псевдограф, так как не имеется ни одной петли (дуги, у которой начальная и конечная вершины совпадают).
• Исходный граф (на рисунке 1) и преобразованный граф (на рисунке 2) являются изоморфными (их дуги и узлы полностью идентичны, их количество совпадает, направления дуг совпадают, узлы каждого графа соединены с другими аналогично соответствующим узлам из другого графа – устанавливается взаимно-однозначное соответствие)
• Исходный граф не является плоским графом, потому что имеются пересечения дуг. То есть в данном случае не все дуги являются плоскими непрерывными линиями.
• Исходный граф является планарным, так как он изоморфен графу на рисунке 2, который является плоским (его вершины -  точки плоскости и все дуги являются непрерывными плоскими линиями).
• Не смешанный, так как все узлы соединены только дугами (нет ни одного ребра)
• Не связен: сильно не связен, т.к. не для любых двух разных вершин существует путь ведущий из первой во вторую; просто не связен, т.к. даже без учёта ориентации дуг не каждые две вершины можно соединить, по крайней мере, одним путём.
• Возможно деление на подграфы. Причём число компонент связности K=2:
• Является лесом, так как граф является не связным и каждая компонента связности является деревом –  связные подграфы(из более чем единичного количества узлов), не имеющие петель, кратных дуг и не содержащие ни одного цикла.  К тому же можем сделать проверку необходимым и достаточным условием того, что данный связный подграф является деревом:
  

(G) = m – n + K = 34 – 36 + 2 = 0, то есть независимых циклов в нашем графе нет.  Так получилось т.к. граф является деревом. Физический смысл цикломатического числа в данном случае состоит в том, что нам не нужно удалять ни одного ребра, чтобы разорвать все циклы и получить дерево (граф и так без циклов и является деревом).




Граф не является эйлеровым (нет цикла содержащего всего рёбра графа) так как он не связен и есть аж 22 вершины с нечётными степенями.  По той же самой причине нету и эйлерова цикла.

Для того, что бы преобразовать граф в эйлеров нам необходимо проделать L/2 = 22/2 = 11 операций удаления/добавления его рёбер (где L  – количество вершин с нечётными степенями).



Гамильтовым называется граф, имеющий гамильтонов цикл, содержащий каждую вершину графа.
Исходный граф гамильтовым не является - в нём вообще нет циклов.

Сделаем из него гамильтонов граф; добавляем рёбра получаем гамильтонов цикл: ...



1.  Вершинная

Наша задача раскрасить вершины графа так, чтобы любые две смежные вершины были раскрашены в разные цветы, при этом число использованных цветов должно быть наименьшим. Это число называется хроматическим числом графа.

Но в нашем случае мы имеем лес, состоящий из деревьев, что делает очевидным то,  что в нашем случае бихроматическое число равно двум - не больше и не меньше. В лесу вообще никогда  нет циклов, в том числе и нечётных. То есть граф является двудольным и бихроматическим. 

Убедимся в этом используя алгоритм поиска в ширину: ...

2.  Рёберная

Наша задача заключается в том, чтобы раскрасить ребра графа так, что любые 2 смежных ребра (т. е. 2 ребра, имеющих общую вершину) были бы окрашены в разный цвет. Для реберно-хроматического числа графа справедлива гораздо более точная оценка чем в случае оценки хроматического:

Так как dmax=5, то реберно-хроматическое число равно либо 5, либо 6 ( либо dmax либо dmax+1 ):

Произведём раскраску: ...



В связи с тем, что декомпозиция исходного графа, который является деревом, не представляется интересной, возьмём для этого произвольный новый граф с пронумерованными вершинами: ... и т.д.