Глава 2. ТЕОРИЯ ГРАФОВ
Определение. Графом называется любая пара , где – множество элементов произвольной природы, называемых вершинами графа; – семейство пар из : .
В множестве допускаются пары типа , а также повторяющиеся пары. Если пары рассматриваются как неупорядоченные, то есть , то граф называется неориентированным и пары из множества называются ребрами. Если пары считаются упорядоченными, то есть то граф называется ориентированным или орграфом и эти пары называются ориентированными ребрами или дугами.
Пример 1. Рассмотрим граф , где , . Условно этот граф можно изобразить так, как показано на рис. 3.
Рис. 3
Определение. Ребро вида называется петлей при вершине . Повторяющиеся в множестве пары называются кратными ребрами.
Иногда под термином «граф» подразумевается граф без кратных ребер и петель, тогда граф с кратными ребрами называется мультиграфом, а граф с кратными ребрами и петлями – псевдографом. Иногда граф без кратных ребер и петель называют простым графом.
|
|
Такое широкое определение графа допускает любую трактовку: множество предприятий с экономическими отношениями, множество людей с психологической совместимостью, система управления с подчинением, технические системы со связями, электрические цепи с источниками и потребителями, транспортные сети. Поэтому язык теории графов получил распространение в химии, физике, лингвистике, экономике, психологии и т.д.
Вершины и называются смежными, если либо пара , либо .
Вершина и ребро инцидентны, если входит в пару .
Ребра и называются смежными, если они инцидентны одной и той же вершине.
В неориентированном графе степенью вершины называется количество инцидентных ей ребер, причем петля учитывается дважды. Если , то вершина называется изолированной, если , то вершина называется висячей.
Так в приведенном примере , , и .
Мы будем рассматривать только конечные графы, то есть множества и будут конечными, будем обозначать их мощности и , соответственно.
Лемма о рукопожатиях. Если , , то .
Доказательство очевидно, каждое ребро в этой сумме участвует ровно 2 раза, так как имеет 2 конца.
Из леммы вытекает, что число вершин с нечетной степенью четно.
Определение. Графы и называются изоморфными, если существует биекция , причем если пара , то пара и наоборот.
Чтобы установить изоморфизм графов достаточно одинаково занумеровать вершины множества и соответствующие им при биекции вершины множества .
Пример 2. Графы на рис. 4 – изоморфны.
Рис. 4
Пример 3. Графы на рис. 5 изоморфны.
Рис. 5
Определение. Подграфом в графе называют граф , в котором .
|
|
Графы можно задавать простым рисунком, или перечислением элементов множеств и , или матрицами смежности, или матрицей инцидентности, или матрицей Кирхгофа.
Матрица смежности вершин для неориентированного графа – это квадратная матрица размером , где ; элемент матрицы если пара , если вершины и соединены ребрам. Эта матрица позволяет задавать неориентированные графы с кратными ребрами и петлями.
Матрица смежности вершин для графа, приведенного на рис. 3, имеет вид
.
Аналогично можно задать матрицу смежности ребер для неориентированного графа, в ней элемент если ребра и смежные. Она используется редко.
Матрица инцидентности употребляется часто и позволяет задавать ориентированные графы. Если граф имеет вершины и ребра , то матрица инцидентности будет иметь размер , и если ребро инцидентно вершине в остальных случаях Если – петля при вершине , тогда. . Если граф ориентированный, то ориентация ребер указывается стрелкой и если ребро вошло в вершину , и если вышло из вершины .
Обратимся к примеру 1, для того чтобы задать матрицу инцидентности, надо пронумеровать ребра графа. Получим соответствующую матрицу инцидентности
Рис. 6 |
Изоморфные графы на рис. 5 имеют одну и ту же матрицу смежности
.
Для изоморфных графов, вершины которых занумерованы произвольным образом, матрицы смежности различны, но они получаются друг из друга одинаковыми перестановками строк и столбцов. То же самое верно для матриц инцидентности.
Пример 4. В примере 3 поменяем нумерацию вершин графа (рис. 7).
Рис. 7
Получим матрицу смежности:
.
Матрицу можно преобразовать в матрицу , поменяв местами вторую и четвертую строчки и столбцы, а затем в полученной матрице поменяв местами четвертую и пятую строки и столбцы.
Матрица Кирхгофа – это квадратная матрица , где и элемент матрицы определяется следующим образом
Сумма элементов в каждой строке и в каждом столбце матрицы равна 0.