4.2. Характеристики графов
Подграфом GА графа G=<М,Т> называется граф, в который входит лишь часть вершин графа G, образующих множество А, вместе с ребрами (дугами), их соединяющими.
Так, карта шоссейных дорог Пермской области является подграфом графа «Карта шоссейных дорог Российской Федерации» [18].
Частичным графом GD по отношению к графу G называется граф, содержащий только часть ребер (дуг) графа G.
Так, карта главных дорог России – подграф карты шоссейных дорог России [18].
Если две вершины соединены ребром, то говорят, что каждая вершина инцидентна этому ребру, а соответствующие вершины – смежны (две вершины, инцидентные одному ребру – смежны). Два ребра, инцидентные одной вершине, также смежны.
Маршрут – чередующаяся последовательность вершин и ребер, в которой два соседних элемента инцидентны [26].
Если начальная вершина маршрута равна конечной, то маршрут замкнут, иначе открыт.
Если все ребра различны, то маршрут называется цепью.
Если все вершины (а, значит и ребра) различны, то маршрут называется простой цепью.
Замкнутая цепь – цикл.
Граф без циклов называется ациклическим.
В ориентированном графе цепь называется путем, а цикл – контуром.
Степенью вершины х, обозначаемой deg(х), называют число ребер, инцидентных ей. Если degх=1, то вершина х тупиковая, если degх=0, то вершина изолированная.
Если G – неориентированный граф с n вершинами и m ребрами, а degj – степени j-й вершины, то сумма степеней вершин равна удвоенному количеству ребер:
.
Это следует из того, что каждое ребро добавляет единицу к степени каждой из двух вершин, которое оно соединяет, т.е. добавляет 2 к сумме уже имеющихся вершин. Следствием этого факта является то, что в каждом графе число вершин нечетной степени четно. Для ориентированного графа вводятся понятия полустепень исхода и полустепень захода.
Деревья. Лес.
Граф связен, если любые две его вершины можно соединить цепью. Если граф не связен, то его можно разбить на отдельные связные подграфы, которые называются компонентами связности.
Связный граф, не имеющий циклов (ациклический), называется деревом (рис. 17).
Рис. 17. Граф-дерево
Деревом может быть задано отношение подчинения в трудовом коллективе, в государстве.
Простейшее дерево состоит из двух вершин, соединенных ребром. Каждый раз, когда добавляется еще одно ребро, в конце его прибавляется также и вершина. Следовательно, дерево с n вершинами имеет n-1 ребро.
В теории графов доказывается, что число различных деревьев, которые можно построить на m вершинах, равно mm-2. Много деревьев – это лес.
Цикломатическое число.
Пусть G – неориентированный связный граф, имеющий n вершин и m ребер.
Цикломатическим числом связного графа G с n вершинами и m ребрами называется число
n(G)=m-n+1.
Это число имеет интересный физический смысл: оно равно наибольшему числу независимых циклов в графе [18]. При расчете электрических цепей цикломатическое число используется для определения числа независимых контуров.
Рассмотрим примеры подсчета числа независимых циклов.
В графе, состоящем из одной вершины и одного ребра, один цикл (рис. 18а).
В графе, состоящем из одной вершины и трех ребер, три цикла (рис. 18б).
В графе, состоящем из двух вершин и двух ребер, один цикл (рис. 18в).
В графе, состоящем из двух вершин и пяти ребер, четыре цикла (рис. 18г).
В графе, состоящем из трех вершин и трех ребер, один цикл (рис. 18д).
В графе, состоящем из трех вершин и четырех ребер, два цикла (рис. 18е).
В графе, состоящем из четырех вершин и четырех ребер, один цикл (рис. 18ж).
В графе, состоящем из четырех вершин и пяти ребер, два цикла (рис. 18з).
В графе, состоящем из четырех вершин и шести ребер, три цикла (рис. 18и).
Цикломатическое число дерева равно нулю.
Рис. 18. Примеры циклов в графах
11 Операции над графами.
Полный граф – это граф, в котором все вершины связаны друг с другом. Очевидно, что это аналог универсума в теории множеств. Поэтому, можно ввести операцию дополнения графа до полного, например, в матрице смежности неориентированного графа заменяются нули на единицы и наоборот, исключая главную диагональ.
Вводятся также операции объединения графов, когда объединяются множества вершин и заданных на них отношений; соединение графов, когда находится пересечение указанных множеств.
Используются и такие операции, как удаление вершины, удаление ребра, добавление вершины, добавление ребра.
В настоящее время в ЭВМ графы чаще всего задаются списками смежности и массивом указателей на эти списки [26].
Задачи на графах могут быть решены, например, системой компьютерной математики Matematica (3,4) фирмы Wolfram Research,Inc. – пакет расширения «Дискретная математика» (DiscreteMath) – представление графов, создание графов, свойства графов, алгоритмическая теория графов.