Элементы теории графов: основные понятия и определения. Способы представления графов и деревьев. Примеры применения деревьев в программировании.

Содержание

• Содержание
• Чуть–чуть истории
• Графы: определения и примеры
  • Неориентированные графы
• Примечания

Чуть–чуть истории

Теория графов — довольно молодая наука (по сравнению, скажем, с геометрией). В 1736 году Санкт–Петербургская академия наук опубликовала труд Леонарда Эйлера, где рассматривалась задача о кенигсбергских¹ мостах («Можно ли, пройдя все городские мосты ровно по одному разу, вернуться в исходную точку?»). Это была первая работа по будущей теории графов.

Особенно приятно то, что в данном случае Россия — родина пусть и не новой породы слонов, но зато нового научного направления!

Графы: определения и примеры

Итак, перейдём к изложению некоторых понятий современной теории графов.

Неориентированные графы

Граф — это двойка <V, E>, где V — непустое множество вершин, а Е — множество рёбер, соединяющих эти вершины попарно². Две вершины, связанные между собой ребром, равноправны, и именно поэтому такие графы называются неориентированными: нет никакой разницы между «началом» и «концом» ребра.

Таблица 11.1. Примеры неориентированных графов

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

Например, три графа на рис. 11.1 совпадают, а два графа на рис. 11.2 — различны.

Рис. 11.1.  Три способа изображения одного графа

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

Ребро е и вершина v называются инцидентными друг другу, если вершина v является одним из концов ребра е.

Рис. 11.2.  Пример двух разных графов

Рис. 11.3.  Псевдограф

Любому ребру инцидентно ровно две вершины, а вот вершине может быть инцидентно произвольное количество рёбер, это количество и определяет степень вершины. Изолированная вершина вообще не имеет инцидентных ей рёбер (её степень равна 0).

Две вершины называются смежными, если они являются разными концами одного ребра (иными словами, эти вершины инцидентны одному ребру). Аналогично, два ребра называются смежными, если они инцидентны одной вершине.

Путь в графе — это последовательность вершин (без повторений), в которой любые две соседние вершины смежны. Например, в графе, изображённом на рис. 11.1, есть два различных пути из вершины a в вершину с: adbc и abc.

Вершина v достижима из вершины u, если существует путь, начинающийся в u и заканчивающийся в v.

Граф называется связным, если все его вершины взаимно достижимы.

Компонента связности — это максимальный связный подграф. В общем случае граф может состоять из произвольного количества компонент связности. Заметим, что любая изолированная вершина является отдельной компонентой связности. На рис. 11.4 изображён граф, состоящий из четырёх компонент связности: [abhk], [gd], [c] и [f].

Длина пути — количество рёбер, из которых этот путь состоит. Например, длина уже упомянутых путей adbc и abc (см. рис. 11.1) — 3 и 2 соответственно.

Рис. 11.4.  Несвязный граф

Говорят, что вершина v принадлежит k–му уровню относительно вершины u, если существует путь из u в v длиной ровно k рёбер. Одна и та же вершина может относиться к разным уровням. Например, в графе, изображённом на рис. 11.1, относительно вершины a существует 4 уровня:

• 0) a;
• 1) b, d;
• 2) b, d, c (пути adb, abd, abc);
• 3) c (путь adbc).

Расстояние между вершинами u и v — это длина кратчайшего пути от u до v. Из этого определения видно, что расстояние между вершинами a и c в графе на рис. 11.1 равно 2.

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

Эйлеров граф — это граф, в котором существует путь или цикл, содержащий все рёбра графа (вершины могут повторяться). Именно такие графы положительно решают упомянутую в начале лекции задачу о кенигсбергских мостах. Например, граф на рис. 11.5 является Эйлеровым: искомым путём в нем будет dbacfbcd.

Рис. 11.5.  Граф Эйлера

Гамильтонов граф — это граф, в котором существует путь или цикл (без повторений), содержащий все вершины графа (см. рис. 11.5; искомый цикл: abdfca).

Примечания

1. ^ Ныне — Калининград.
2. ^ Более корректно: Е — это множество двухэлементных подмножеств (неупорядоченных пар) множества V, называемых рёбрами. Из такого определения видно, что любые две вершины могут быть соединены не более, чем одним ребром.