Основные понятия теории графов

прохождения всех четырех частей суши в задаче о кенигсбергских мостах

(1736)

Из истории теории графов

называемых вершинами, и конечного множества элементов, называемых ребрами.
Граф G=(V, E)

V={v1, v2, v3, v4, v5} ;
E={e1, e2, e3, e4, e5, e6, e7}

вершинами ребра ek.
Ребра с одинаковыми концевыми

вершинами называются параллельными (e1,e4 ).
Петля– замкнутое ребро(e5).
Ребро, принадлежащее вершине, называется инцидентным (ребро e1 инцидентно вершинам v1 и v2).

смежны, если они являются концевыми вершинами некоторого ребра (v1, v4).

Если два ребра имеют общую концевую вершину, они называются смежными (e1, e2).

G

графа G

и параллельных ребер.
Граф G=(V,E) называется полным,

если он простой и каждая пара вершин смежна. 

кратными ребрами называется мультиграф.

множестве P вершин всегда содержит q=p-1 ребер, т.е. минимальное количество

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

Виды графов

прадеревья.
Деревом называется конечный связный неориентированный граф, состоящий, по крайней мере,

из двух вершин и не содержащий циклов. Такой граф не имеет петель и кратных ребер







Ветвями дерева называются ребра графа, входящие в дерево. Хордами дерева называются ребра, входящие в граф, дополнительный к данному дереву. Лагранжевым деревом называется дерево, все ветви которого имеют общую вершину.

Виды графов

называется ориентированный граф G(X) с корнем х0  X, если в каждую

вершину хi  х0 (хi  X) заходит ровно одна дуга, а в корень х0 не заходит ни одна дуга. Прадерево не содержит контуров

Виды графов

неориентированным.

орграфом.
Ребра, имеющие направление, называются дугами.

граф, достаточно для каждого ребра указать двухэлементное множество вершин –

его мы и будем отождествлять с ребром.
{{a,b},{b,c},{a,c},{c,d}}

количеству ребер между рассматриваемыми вершинами.

имеет вид:

имеет вид:

таблица, строки которой соответствуют вершинам графа, а столбцы - ребрам.

Элементы матрицы определяются следующим образом:

ej;
bij= 0, в противном случае

вершину vi ;
1, если ребро ej выходит из вершины vi

;
bij= 2, если ребро ej –петля из вершины vi ;
0, если ej и vi не инцидентны.

G

ребер v0, e1, v1, e2,…,vk-1, ek, vk, которая начинается и

заканчивается на вершинах, причем vi-1 и vi являются концевыми вершинами ребра ei, 1 i  k.

v2, e2, v3, e3, v6, e9, v5, e7, v3, e11,

v6).
Маршрут называется замкнутым, если его концевые вершины совпадают (v1, e1, v2, e2, v3, e7, v5, e3, v2, e4, v4, e5, v1).

G

если ее концевые вершины различны(v1, e1, v2, e2, v3, e8,

v6, e11, v3).
Цепь называется замкнутой, если ее концевые вершины совпадают (v1,e1,v2,e2,v3,e7,v5,e3,v2,e4,v4,e5,v1).

G

(v1, e1, v2, e2, v3).
Цикл – это замкнутая цепь (

простой цикл, если цепь простая) (v1,e1,v2,e3,v5,e6,v4,e5,v1).
Число ребер в пути называется длиной пути. Аналогично определяется длина цикла.

G

равна 2, концевые вершины имеют степень, равную 1.

2. Каждая вершина

цикла имеет степень 2 или другую четную степень. Обращение этого утверждения, а именно то, что ребра подграфа, в котором каждая вершина имеет четную степень, образуют цикл, — неверно.

3. Число вершин в пути на единицу больше числа ребер, тогда как в цикле число ребер равно числу вершин.

в графе G, если в нем существует путь vi—vj. Вершина

связана сама с собой.
Граф называется связным, если в нем существует путь между каждой парой вершин.
Компонента связности – максимальный связный подграф в графе.

G

1 компонента связности: {v1, v2, v3, e1, e2, e3}
2 компонента связности: {v4, v5, v6, e4, e5, e6}
3 компонента связности: {v7, v8, e7}
4 компонента связности: {v9}

т. е. вершин в ее окружении.
Максимальная и минимальная степени вершин

графа G обозначаются символами (G) и (G) соответственно:
(G)= (G)=
Граф G=(V,E) называется регулярным или однородным (степени r), если степени всех его вершин одинаковы. Степенью регулярного графа называется степень его вершин.

– четное число, равное удвоенному числу ребер:


Интерпретация леммы: поскольку в

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

взаимно-однозначное отображение между множествами их вершин и ребер, что соответствующие

ребра графов G1 и G2 инцидентны соответствующим вершинам этих графов.
Если граф G изоморфен геометрическому графу G' в Rn, то G' называется геометрической реализацией графа G в пространстве Rn.

R3

R2

Граф R2 является геометрической реализацией графа R3

e6e3’.
G1 и G2 – изоморфные графы
G1 G2

т.е. оно симметрично, транзитивно и рефлексивно.

вершинам присвоены некоторые метки (например номера 1, 2, …, n).
Абстрактный

(или непомеченный) граф – это класс изоморфных графов.

Помеченные графы:

граф. Отклонением d(xi, xj) его вершины xi от вершины xj

называется длина кратчайшего пути из хi в xj:
d(xi, xj) = min {l[Sk(xi, xj)]}.
Отклонение d(xi, xj) удовлетворяет следующим аксиомам метрического пространства:
d(xi, xj)  0;
d(xi, xj) = 0  xi = xj;
d(xi, xj) + d(xj, xk)  d(xi, xk) – неравенство треугольника и не удовлетворяет четвертой аксиоме, а именно:
d(xi, xj)  d(xj, xi), так как граф ориентирован.
Необходимо отметить, что если xj  G(xi), то d(xi, xj) = .

Характеристики графов

всем xj:

В качестве примера рассмотрим схему первой (1870 г.) сети связи

для почтовых голубей

Характеристики графов

вектор отклоненностей – в таблицах соответственно.

Таблица. Вектор отклонений
Характеристики графов
Таблица. Отклонения

d(xi, xj)

сводится к определению тех или иных характеристик графов, поэтому полезно

знакомство со следующими характеристиками.
Цикломатическое число. Пусть G(X) – неориентированный граф, имеющий n вершин, m ребер и k компонент связности. Цикломатическим числом графа G называется число
µ(G) = m - n + k.
Это число имеет интересный физический смысл: оно равно наибольшему числу базисных (независимых) циклов в графе. При расчете электрических цепей цикломатическим числом можно пользоваться для определения числа независимых контуров.

Граф G(X) называется р-хроматическим, если его вершины можно раскрасить различными

цветами так, чтобы никакие две смежные вершины не были раскрашены одинаково. Наименьшее число р, при котором граф является р‑хроматическим, называется хроматическим числом графа и обозначается γ(G).
Если γ(G) = 2, то граф называется бихроматическим. Необходимым и достаточным условием того, чтобы граф был бихроматическим, является отсутствие в нем циклов нечетной длины.
Хроматическое число играет важную роль при решении задачи наиболее экономичного использования ячеек памяти при программировании. Однако его определение, за исключением γ(G) = 2, представляет собой довольно трудную задачу, требующую применения ЭВМ.

называется внутренне устойчивым, если никакие две вершины из S не

являются смежными, то есть для любого х  S имеет место:
G(x)  S = .
Множество внутренней устойчивости, содержащее наибольшее число элементов, называется наибольшим внутренне устойчивым множеством, а число элементов этого множества называется числом внутренней устойчивости графа G. Наибольшее внутренне устойчивое множество играет важную роль в теории связи.
Множество внешней устойчивости. Множество Т  X графа G(X) называется внешне устойчивым, если любая вершина, не принадлежащая Т, соединена дугами с вершинами из Т, то есть для любого х  Т имеет место: G(x)  Т  .
Множество внешней устойчивости, содержащее наименьшее число элементов, называется наименьшим внешне устойчивым множеством, а число элементов этого множества называется числом внешней устойчивости графа G(X).

решения задач оптимизации на графах
Содержание:
Понятие эйлерова цикла и

графа
Критерии и алгоритмы определения эйлеровых
графов
Применение эйлеровых графов
Гамильтоновы циклы и графы
Методы определения гамильтоновых циклов
Применение гамильтоновых графов
Сравнительный анализ эйлеровых и
гамильтоновых графов

замкнутый маршрут, который включает каждое ребро графа только один раз

(вершины могут повторяться)

Пример

abcdefcghea

Определение эйлерова цикла и графа

добавить еще одно ребро, то можно составить маршрут, включающий каждое

из ребер только один раз, который начинается в одной из вершин и заканчивается в другой
ABCDCBDAB
ABDCDABCB
Такой маршрут представляет собой эйлерову цепь
Граф, содержащий эйлерову цепь, называется полуэйлеровым

Эйлерова цепь

графа. 1

вершины имеют четную степень:

G= эйлеров  vV degv=2n, nN

Если

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

Критерий эйлеровости графа. 2

вычеркиванием пройденного ребра
Запрещается проход по ребру, если его удаление приводит

к разбиению графа на два компонента связности

где требуется определить маршрут, проходящий один раз по каждой из

улиц. Задача состоит в нахождении пути, минимизирующего общую длину, время или стоимость;
инспектирования распределенных систем, где необходима проверка электрических, телефонных, железнодорожных, других линий;
коммунального хозяйства и планирования;
теории игр и в головоломках;
компьютерной инженерии и управления

тестируемой ячейке осуществляется путем построения графовой модели и решения на

ней задачи построения эйлерова цикла
Базовая запоминающая ячейка
Соседство взаимодействующих ячеек пятого порядка
Соседство взаимодействующих ячеек девятого порядка
Смежные ячейки
Будем рассматривать два типа смежных ячеек, расположенных по кресту и по квадрату относительно базовой

Применение эйлеровых графов в задачах КИУ: методы обнаружения отказов в соседствах взаимодействующих ячеек

взаимодействующих ячеек 5-го и 9-го порядков
Смежные образцы –

комбинации состояний
смежных ячеек
Рассматриваются смежные
образцы для соседства
взаимодействующих ячеек
5-го и 9-го порядков

Пассивные смежные
образцы (ПСО)

Активные смежные образцы
(АСО)

при помощи графа, дуги которого соединяют состояния запоминающих ячеек, различающиеся

только в одной позиции.
Формирование всех АСО и ПСО эквивалентно нахождению контура графа, в котором каждая дуга встречается только один раз.
Такие контуры называются эйлеровыми.

Направленный граф для трех запоминающих ячеек

цикл
Цикл называется гамильтоновым, если он содержит каждую вершину только

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

Гамильтонов граф

Негамильтонов граф

кругосветном путешествии, которую рассматривал Уильям Гамильтон: обойти все вершины графа

− столицы различных стран − по одному разу и вернуться в исходный пункт
Для 20 государств задача представляет обход всех вершин додекаэдра
1-2-3-4-5-6-7-8-9-10-11-12-13-14-15-16-17-18-19-20-1

Историческая справка

графа G= составляется матрица переходов М=||mij|| размера kn:
k=max deg_vi ,

viV, n=|V|
mij − i-я вершина vq, если в графе существует дуга из вершины vi в вершину vq. Вершины можно упорядочить произвольно, образовав элементы j-го столбца матрицы М.
К составляемой гамильтоновой цепи добавляется первая вершина в столбце v1 (например, вершина a). Затем к цепи добавляется первая возможная вершина (например, b) в столбце a, затем c – в столбце b и т.д.
Под возможной понимается вершина, еще не принадлежащая гамильтоновой цепи S, добавление которой не приводит к преждевременному замыканию цикла.

v1, a, b, c, ... , vr-1, vr }. Существуют

две причины, препятствующие включению очередной вершины:
В столбце vr нет возможной вершины;
Цепь, определяемая множеством S, имеет длину n-1, т.е. является гамильтоновой, тогда
а) в графе существует замыкающая дуга (vr,v1), следовательно, найден гамильтонов цикл;
б) в графе не существует замыкающей дуги (vr,v1), следовательно, гамильтонов цикл не может быть получен.
В случаях 1 и 2б) следует предпринять возвращение.
Гамильтоновы циклы, найденные к этому моменту, являются всеми гамильтоновыми циклами в графе

матрице переходов строятся гамильтоновы цепи из вершины а
a b

d c e a
a d c b e a

гамильтонова цикла на взвешенном графе известна как задача коммивояжера
Приложения:
задачи упорядочивания

или планирования операций;
составление расписаний;
выполнение операций на ЭВМ;
проектирование электрических и компьютерных сетей;
управление автоматизированными линиями;
тестирование ОЗУ и распределенной памяти;
синтез тестов проверки цифровых систем;
диагностирование неисправностей вычислительных систем и сетей

алгоритмы отыскания эйлеровых циклов
Эйлеровы графы встречаются редко
Эйлеровы графы менее востребованы

Гамильтоновы

графы
Критерии не известны, но достаточные условия существуют
Алгоритмы поиска гамильтонова цикла в графе достаточно трудоемки
Почти все графы, встречающиеся в теории и практике, гамильтоновы
Гамильтоновы графы более востребованы на практике

Сравнительный анализ и связь эйлеровых и гамильтоновых графов