45f9d30a

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


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

Таблица 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).



Содержание раздела