Содержит: методы задания графа( графически, списком, матрицей инцинденции, матрицей смежности), идентификация графа (его описание: планарный или нет, связен/несвязен и т.п.), характеристики графа(сумма всех рёбер, цикломатическое число графа и т.п.), эйлеровость, гамильтовость, правильная раскраска графа (вершинная и рёберная), топологическая декомпозиция графа.
Фрагменты:
1. Задание графа.
а) Графически: (изменим исходный граф, передвинув узлы так, что бы визуальное представление стало легче и проименуем все дуги и вершины)
Является орграфом, так как в нём имеются только дуги, имеющие направление (нет ни одного ребра).
Это неполный орграф, так как не любые две вершины соединены парами дуг в каждом направлении.
Это не мультиграф, потому что нет ни одного повторения элементов во множестве дуг.
Не псевдограф, так как не имеется ни одной петли (дуги, у которой начальная и конечная вершины совпадают).
Исходный граф (на рисунке 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 ):
Произведём раскраску: ...
Топологическая декомпозиция графа
В связи с тем, что декомпозиция исходного графа, который является деревом, не представляется интересной, возьмём для этого произвольный новый граф с пронумерованными вершинами: ... и т.д.
