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

Основные понятия и определения теории графов Автор: М.Н. Шелест Лекция №1 по дисциплине: «Построение и анализ графовых моделей» Санкт-Петербург, 2018 Граф и его элементы Определение: Граф - это объект состоящий из элементов двух типов: узел (вершина) и ребро. Множество вершин: V = {v1 , v2 , . . . vN } Множество ребер: E = {e1 , e2 , . . . eM } Математическое обозначение графа: G (V, E) Определение: Ребро инцидентно вершине, если это ребро либо начинается, либо заканчивается в этой вершине. Лекция №1: «Построение и анализ графовых моделей» 2 / 17 Граф и его элементы Определение: Степень вершины (ρ (vi )) – это количество ребер инцидентных данной вершине. N – количество вершин, M – количество ребер. N P ρ (vi ) = 2M =⇒ i=1 M= 1 2 N P ρ (vi ) i=1 Теорема: Количество вершин с нечетной степенью есть число четное. Пусть V 0 – множество вершин с четными степенями, V 00 – множество вершин с нечетными степенями, тогда: X X ρ (vi ) + ρ (vj ) = |{z} 2M i: vi ∈V 0 j: vj ∈V 00 четное | {z } | {z } четное четное Лекция №1: «Построение и анализ графовых моделей» 3 / 17 Специальные графы Определение: Нуль-граф (ON ) – это граф, состоящий из изолированных вершин, т.е. из вершин, не соединенных никакими ребрами. ON ∼ G(V, ) : N P G (V, ) ρ (vi ) = 0, M = 0. i=1 Определение: Полный (полносвязный) граф (UN ) – это граф, в котором каждая пара вершин соединена ребром. UN ∼ G(V, max E) : N P ρ (vi ) = N (N − 1) , M = i=1 N (N −1) . 2 G (V, max E) Лекция №1: «Построение и анализ графовых моделей» 4 / 17 Свойства графов Определение: Граф Ḡ называется графом дополнением к графу G, если он образован теми же вершинами и ребрами, которых не хватает графу G, чтобы быть полным. 1 1 5 2 4 3 G(V,E ) E 0 ∩ E 00 = 1 5 2 4 5 3 G(V,maxE) 2 4 3 Ḡ(V,E ) , E 0 ∪ E 00 = max E. Лекция №1: «Построение и анализ графовых моделей» 5 / 17 Свойства графов Определение: Два графа называются изоморфными, если вершинам и ребрам одного графа можно поставить во взаимно однозначное соответсвие вершины и ребра другого графа. 1 G1 «1» ∼ «А» А G2 «2» ∼ «В» 5 2 Д Б «3» ∼ «Б» «4» ∼ «Д» 4 3 Г В «5» ∼ «Г» Определение: Однородный граф – это граф, степени всех вершин которого равны. Лекция №1: «Построение и анализ графовых моделей» 6 / 17 Свойства графов Определение: Плоский (планарный) граф – это граф, для которого существует такой изоморфизм, что ни одна пара ребер в нем не пересекается. 1 2 4 3 2 1 4 3 Теорема Жордана: Если есть замкнутая линия l, не имеющая самопересечений, то для любой точки P , находящейся внутри области, и точки Q, находящейся вне области, невозможно провести соединяющую их линию, чтобы она не пересекала l. Q l Задача о трех домах и трех колодцах: Д Д Д Д Д Д К К К К К К P Лекция №1: «Построение и анализ графовых моделей» 7 / 17 Цепи и циклы Определение: Цепь – это путь из одной вершины в другую, в котором каждое ребро встречается только один раз. Определение: Элементарная дуга – это цепь, в которой каждая вершина встречается только один раз. Определение: Две вершины в графе связаны, если существует соединяющая их цепь. B A C D F E Лекция №1: «Построение и анализ графовых моделей» 8 / 17 Цепи и циклы Определение: Связный граф – это граф, в котором все пары вершин связаны. Определение: Разрез графа – это минимальное количество ребер, которые необходимо удалить, чтобы граф перестал быть связным. Определение: Цикл или кольцо – это цепь, которая начинается или заканчивается в одной и той же вершине. B A C D F E Лекция №1: «Построение и анализ графовых моделей» 9 / 17 Цепи и циклы Определение: Эйлеров цикл – это цикл, содержащий все ребра графа ровно один раз. Для того, чтобы граф содержал эйлеров цикл, необходимо и достаточно, чтобы степени всех вершин графа были четными. I Проверка степеней вершин; I Проходя по ребру, вычеркивать его. Проходить можно по любому ребру, но необходимо не закончить цикл раньше, чем будут пройдены все ребра. 9 B Алгоритм нахождения эйлерова цикла: A D 3 10 6 2 8 F 5 1 7 C Лекция №1: «Построение и анализ графовых моделей» 4 E 10 / 17 Циклы и цепи 4 B Определение: 1 Эйлерова цепь в отличие от эйлерова цикла может начаться в одной вершине и закончиться в другой, но каждое ребро в графе также можно посетить только один раз. A D 7 3 8 F 5 2 9 C 6 E Для того, чтобы в графе существовала эйлерова цепь в графе должно быть только две вершины в с нечетными степенями, причем это должны быть вершины начала и конца. Определение: Гамильтонов цикл – это цикл, в котором каждая вершина графа встречается только один раз. Задача Коммивояжера: Посетить каждый город только один раз и вернуться в точку отправления. Лекция №1: «Построение и анализ графовых моделей» 11 / 17 Деревья ярус 0: ярус 1: ярус 2: ярус 3: Определения: 1 3 4 6 7 2 Дерево – это связный граф, не содержащий циклов. 5 Корень – основная вершина, корневая вершина. 8 Листья – нижние узлы. Вершины принадлежат i-ому ярусу, если расстояние до корневой вершины от них равно i. В любом произвольном дереве, содержащем N вершин, содержится N − 1 ребро. Лекция №1: «Построение и анализ графовых моделей» 12 / 17 Деревья Определение: Цикломатическое число (цикломатический порядок) графа – это наименьшее количество ребер, которые надо удалить из данного связного графа, чтобы на нем не осталось ни одного цикла. B D Определение: Остовное дерево – это дерево, содержащее все вершины исходного графа и только те ребра, которые необходимы для сохранения связности. A F C E Определение: Минимальное остовное дерево – это остовное дерево неориентированного взвешенного графа, сумма весов оставшихся ребер в котором минимальна. Лекция №1: «Построение и анализ графовых моделей» 13 / 17 Алгоритмы поиска минимального остовного дерева Алгоритм Крускала: На каждом шаге выбирается ребро наименьшего веса среди множества ребер, которые не образуют цикл. Алгоритм Прима: На каждом шаге среди ребер, не образующих цикл, производится поиск ребра с минимальным весом, которое соединяет одну из рассмотренных вершин с вершиной из множества не рассмотренных. B G E A C Лекция №1: «Построение и анализ графовых моделей» F 14 / 17 Алгоритмы поиска минимального остовного дерева Определение: ярус 0: ярус 1: ярус 2: Дерево называется q-ичным, если выполняются следующие условия: 1 4 5 ярус 3: 2 6 10 7 11 8 3 1 степень листовых вершин равна единице; 9 2 степень корневой вершины равна q; 3 степень остальных вершин равна q + 1. 12 Максимальное число вершин q-ичного дерева равно: 1 + q + q2 + q3 + . . . + qr = q r+1 −1 q−1 . Определение: Если количество вершин в q-ичном дереве максимально, то такое дерево называется полным. Лекция №1: «Построение и анализ графовых моделей» 15 / 17 Разжатие и сжатие графа B Определение: C H B 3 D F F A C G E E G E F A D C H G E Определение: A G 1 D A Разжатие графа – добавление фиктивных узлов в разрыв ребра. 2 B F Сжатие графа – удаление узлов, если они связаны только с двумя соседями. Теорема Куратовского: Если полное сжатие графа не содержит графа типа «Три дома, три колодца» или графа типа «Пентаграмма», то граф является планарным. Лекция №1: «Построение и анализ графовых моделей» 16 / 17 Компоненты связности Определение: 6 2 Компонент связности – это такое множество вершин графа, в котором каждая пара вершин является связной, и не существует пути в другое множество вершин. 7 8 1 3 5 9 10 4 11 Поиск компонент связности в графе обычно осуществляется алгоритмом поиска в ширину (breadth-first search, BFS) или алгоритмом поиска в глубину (depth-first search, DFS). 3 2 1 4 5 6 8 7 9 11 Лекция №1: «Построение и анализ графовых моделей» 10 17 / 17