Занятие 12. Графы: определения и способы хранения

1. Графы: первые определения

Графы — это специальная математическая абстракция, которая позволяет обсуждать и анализировать широкий круг вещей в реальном мире. Это такая же абстракция, как, например, числа. Числа естественно возникают при подсчёте яблок у Пети, массы сахара в чайной ложке и температуре воздуха за окном. Изучая числа, вы сталкиваетесь с новыми определениями: вам объясняют, что называется квадратным корнем числа, что такое делители числа. Далее, про числа вам рассказывают в школе разные теоремы: например, формулу квадрата суммы двух чисел, теорему о единственности разложения числа на простые множители. Наконец, на программировании вы изучаете алгоритмы, связанные с числами: алгоритм Евклида нахождения НОД, алгоритм проверки числа на простоту. Всё это ждёт нас и при изучении графов.

Начнём с выяснения, зачем же нам нужны графы, какие вещи в реальном мире они позволяют изучать. Посмотрим на карту метрополитена города Киева:

Основное, что мы видим на ней — это станции и перегоны между ними.

Теперь взглянем на участок Москвы с автомобильными дорогами (скриншот сделан с сайта Яндекс.Карты).

Можно описывать сеть дорог как набор перекрёстков, некоторые из которых соединены участками дорог.

Далее, обратим внимание на генеалогическое древо славянской языковой группы.

На этой картинке имеется ряд языков, на которых говорили или говорят некоторые народы Европы. Учёные-лингвисты давали на такой схеме общего предка нескольким языкам, если они считали, что эти несколько языков родственны, т.е. когда-то в прошлом были одним языком, а потом накопили достаточно различий и стали отдельными языками.

Наконец, посмотрим на пример цепи питания в биологии.

Что общего у всех этих картинок? Главное, что на них изображено — это объекты и связи между ними. В теории графов все такие картинки называются графами. Графы состоят из вершин и рёбер. Так, в графе киевского метрополитена станции считаются вершинами, а перегоны между ними — рёбрами. В графе цепи питания биологические виды являются вершинами, и направленное ребро проведено от одного вида к другому тогда, когда первый вид является пищей для второго.

Итак, графом называется набор вершин и набор рёбер. Каждое ребро соединяет две вершины.

Степенью вершины называется количество рёбер, концом которых она является. Например, в графе метрополитенов большинство станций имеют степень 2, а конечные станции имеют степень 1. В графе славянской языковой группы вершина «западнославянский язык» имеет степень 4.

На рисунке выше вершина A имеет степень 3, вершина B имеет степень 4. Вершина H имеет степень 0 и называется изолированной вершиной.

2. Виды графов и пути в графах

Для представления разных объектов и связей между ними используются разные виды графов. Например, графы бывают ориентированные и неориентированные. Ориентированные графы — это графы, в котором у каждого ребра есть начало и конец. Такие рёбра рисуют стрелками. В наших примерах граф цепи питания ориентированный, а граф метрополитена — неориентированные.

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

Путём в графе называется любая последовательность вершин, в которой каждые две соседние вершины соединены ребром. На рисунке выше A → C → B → G — это путь из вершины A в вершину G. Есть и более короткий путь из A в G: путь A → B → G. Длиной пути называется количество рёбер в нём. Таким образом, кратчайший путь из A в G имеет длину 2.

Циклом в графе называют путь, у которого начальная и конечная вершина совпадают. На рисунке выше путь A → C → B → D → A является циклом.

Если вы внимательно посмотрите на определение пути и цикла, то увидите, что путём так же можно считать последовательность A → D → B → D → B, а последовательность F → E → F удовлетворяет определению цикла. Чтобы исключить такие патологические ситуации из рассмотрения, обычно вводят понятия простого пути и простого цикла. Простой путь — это путь, в котором нет повторяющихся рёбер. Простой цикл это цикл, который является простым путём.

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

  1. между любыми двумя вершинами набора существует путь;
  2. набор нельзя расширить, добавив в него ещё хотя бы одну вершину, чтобы при этом осталось верным свойство 1.
Всякий неориентированный граф разбивается на свои компоненты связности. На рисунке выше имеются три компоненты связности: {A, B, C, D, G}, {E, F} и {H}. Граф, у которого только одна компонента связности, называется связным. Граф, у которого более одной компоненты связности, называется несвязным. На рисунке выше изображён несвязный граф.

В ориентированном графе путём называется любая последовательность вершин, в которой соседние вершины соединены ребром, и это ребро идёт «слева направо» (в нужную сторону). Например, на рисунке ниже A → B → C → D является путём, а A → D → C → B — не является (потому что в графе нет рёбер A → D и C → B).

В ориентированном графе некоторые понятия, которые мы ввели для неориентированных графов, имеют свои аналоги. Например, наряду с понятием «степень вершины», в ориентированных графах используются понятия полустепень захода (количество рёбер, входящих в вершину) и полустепень исхода (количество рёбер, исходящих из вершины). На рисунке выше вершина D имеет полустепень захода 1 и полустепень исхода 3.

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

Между вершинами A и B, а также между вершинами C и D проведены кратные рёбра. Заметим, что между вершинами E и F кратных рёбер нет, поскольку ориентированные рёбра считаются кратными, только если у них совпадают начала и концы с учётом ориентации. Рёбра, исходящие из вершин G и H, называются петлями. Про некоторые графы специально говорят «графы без петель и кратных рёбер», чтобы подчеркнуть, что в них не встречаются ситуации, аналогичные изображённым выше.

3. Деревья

На практике часто встречаются графы, которые обладают какими-нибудь особенностями строения. Один из часто встречающихся видов графов — это деревья. Дерево — это связный неориентированный граф без петель и кратных рёбер, в котором нет циклов. Типичный пример дерева изображён на рисунке ниже.

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

Ещё одно удивительное свойство деревьев — это связь между количеством вершин и количеством рёбер. Договоримся обозначать буквой V количество вершин (от англ. vertex «вершина»), а буквой E — количество рёбер (от англ. edge «ребро»). Например, у дерева на рисунке выше V = 11, E = 10. Мы видим, что для графа на рисунке E = V − 1.

Чтобы понять, всегда ли это будет верно, рассмотрим висячие вершины. Висячей вершиной называется вершина степени 1. На рисунке выше висячими являются вершины A, C, F, G, H, J и K. Заметим, что в дереве, в котором есть хотя бы две вершины, всегда есть хотя бы одна висячая вершина. Действительно, выберем произвольную вершину дерева и пойдём из неё гулять по рёбрам дерева в произвольном направлении, не возвращаясь назад. Поскольку циклов в дереве нет, то с каждым шагом мы будем посещать всё новые и новые вершины и в какой-то момент придём в вершину, из которой никуда пойти нельзя. Эта вершина и будет висячей.

Правда ли, что если в дереве есть хотя бы две вершины, то в нём есть хотя бы две висячие вершины? А правда ли, что если в дереве есть хотя бы три вершины, то в нём есть хотя бы три висячие вершины?

Теорема. В любом дереве E = V − 1.

Доказательство. Как мы выяснили, если в дереве хотя бы две вершины, то в нём есть хотя бы одна висячая вершина. Выберем её и удалим из графа её и ребро, за которое она присоединена к графу. При этом количество вершин и рёбер уменьшится на единицу. С новым графом проделаем ту же операцию. В конце концов, когда мы удалим всё, что можно, мы получим граф из одной вершины. Для него V = 1, E = 0, т.е. E = V − 1. Значит, и в исходном дереве выполнялось E = V − 1. ▮

4. Как хранить граф в программах

Для представления графов в памяти компьютера используется несколько способов. Пусть вершины графов, которые мы рассматриваем, занумерованы, начиная с нуля. Рассмотрим следующий граф:

Первый способ, которым его можно хранить, — это структура данных «список рёбер». Мы заводим список пар чисел. Каждая пара соответствует одному ребру, ребро представляется номерами двух его вершин. 
num_vertices = 6
edges_list = [[0, 1],  # эта пара описывает ребро между вершинами 0 и 1
              [0, 2],
              [0, 4],
              [1, 2],
              [1, 3],
              [1, 4],
             ]
Заметим, что мы должны хранить в какой-нибудь переменной общее количество вершин в графе. Это нужно делать, поскольку информация об изолированных вершинах в списке рёбер отсутствует.

Второй способ, которым можно хранить этот граф, — это структура данных «матрица смежности». Матрица смежности — это квадратная таблица, в которой на пересечении строки i и столбца j стоит 1, если в графе есть ребро из вершины i в вершину j, и стоит 0, если такого ребра нет. 

adjacency_matrix = [[0, 1, 1, 0, 1, 0],  # единица в столбце 1 кодирует ребро из 0 в 1
                    [1, 0, 1, 1, 1, 0],
                    [1, 1, 0, 0, 0, 0],
                    [0, 1, 0, 0, 0, 0],
                    [1, 1, 0, 0, 0, 0],
                    [0, 0, 0, 0, 0, 0],
                   ]
num_vertices = len(adjacency_matrix)
Заметим, что матрица смежности неориентированного графа всегда симметрична относительно главной диагонали. Главная диагональ в матрице идёт из левого верхнего угла в правый нижний.

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

adjacency_list = [[1, 2, 4],  # здесь перечислены соседи вершины 0
                  [0, 2, 3, 4],
                  [0, 1],
                  [1],
                  [0, 1],
                  [],
                 ]
num_vertices = len(adjacency_list)
Для хранения ориентированных графов применяются те же структуры данных, с разумными поправками:
  • в списке рёбер ребро хранится в виде [начало, конец];
  • в матрице смежности ребро из i в j означает adjacency_matrix[i][j] == 1, и если обратного ребра в графе нет, то будет верным равенство adjacency_matrix[j][i] == 0;
  • в списках смежности для каждой вершины хранится, в какие вершины из неё исходят рёбра.

Внешний контест с задачами