Граф является несвязным, если его можно представить в
виде объединения нескольких не пустых подграфов.
Граф связен, если между любыми вершинами существует
маршрут (без уточнения начальной и конечной вершин).
Сильно связный – существует маршрут, но рёбра не
ориентированы.
Цикл – частный случай маршрута.
Регулярные графы – все вершины имеют одну и
ту же степень.
7. Изоморфизм графов.
А) Два графа называются изоморфными, когда можно
установить взаимно однозначное соответствие так, что 2 вершины в первом графе
соединены ребром тогда и только тогда, когда соединены ребром соответствующие
им вершины во втором графе. Любой граф можно описать матрицей смежности; для
того, чтобы узнать изоморфны ли графы – переставляем строку аi
и столбец aj до тех пор, пока не получим идентичную
матрицу.
-
Изоморфные графы
различаются лишь начертанием
B) Рассмотрим 2 графа G1 и G2;
если в матрице смежности G1 можно переставить строки и
соответствующие столбцы, т. о. эта матрица совпала с матрицей смежности G2,
следовательно графы G1 и G2 изоморфны.
находим
степени вершин и разбиваем по классам:
1, 3, 4, 5 – 3-я степень;
2,
6 – 2-я степень.
Если в G1 и G2 в одноименные классы
входит различное число вершин Þ графы не изоморфны.
Циклы.
Граф n, m, p:
n
– число вершин; m – число рёбер; p – компонент связности;
V=m-n+p –
цикломатическое число.
Если V=0, то циклы отсутствуют.
Рассмотрим:
Цикломатическое число – число рёбер, которые
необходимо удалить, чтобы из графа сделать дерево. Цикл – частный случай
маршрута. Цикл однозначно задаётся подмножеством рёбер, вход в цикл. Число
базисных цикл равен цикломатическому числу.
Обычно рассматривают матрицы: столбцы – рёбра, строки
– циклы.
Циклы: (2,3,4,5)
(5,4,7)
(7,8,9)
Для получения циклов суммируем базисные циклы (строки)
содержащие общие единицы.
Матрица суммы mod 2 описывает все простые
циклы.
Разрез – число рёбер, которые необходимо удалить,
чтобы увеличить число компонент связности.
