6. Алгоритмы на графах и сетях

6.1. Исходные понятия

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

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

Итак, граф G- это пара (V,E), где V - конечное непустое множество узлов, а Е - множество ребер, т.е. пар { v_i, v_j } вершин, называемых смежными, для которых отношение выполняется. В графе, изображенном ниже, например, есть ребра {2,1}, {2,5}, {2,6}, но нет ребер {2,4}, {2,3}:

Говорят, что ребро { v_i, v_j } инцидентно узлам v_i, v_j. Степень р узла равна числу ребер, инцидентных i-му узлу. Число узлов в графе будем далее обозначать n, число ребер в нем - m. Для изображенного выше графа Gn = 6, m = 7.

Подграф графа G содержит некоторое подмножество узлов из V и в с е связующие их ребра. Например, узлы 1, 2, 5 вместе с соеди­няющими их тремя ребрами составляют подграф графа G, а вершины 2,4 - другой подграф, не имеющий ребер.

Маршрут между узлами v₀, v_k - это последовательность узлов v₀, v₁, v₂, ..., v_k, такая, что для любого j = l...k существует ребро { v_j-1, v_j }. Следовательно, маршрут - это также и последовательность ребер, число которых называют длиной маршрута. Цепь - маршрут без по­вторения ребер. В простой цепи все узлы различны. Цепь между узлами v_i, v_j будем обозначать v_i, v_j .

Цикл - это замкнутая цепь, т.е. узел v_k - тот же, что и v₀. Простой цикл - это замкнутая простая цепь, например, цикл 1, 2, 6, 5, 1 или цикл 1, 2, 5, 6, 1 в графе G. Минимальная длина цикла равна 3; например, маршрут 3, 4, 3 не считают циклом.

Граф связен, если для любой пары узлов есть соединяющая их цепь. Несвязный граф состоит из k> 2 компонент связности - максимальных связных подграфов; например, в графе G - две компоненты G' и G". Граф или подграф называют полным, если для любых его узлов v_i, v_j в нем имеется ребро { v_i, v_j } . Например, подграф (компонента) G' - полон. В полном графе m =(n² - n)/2 ребер. Узел, не смежный ни с одним узлом графа, называют изолированным. Назовем полнотой графа отношение 2m/(n² - n); в процентах – 200*m /(n² – n).

Связный граф (подграф) без циклов (ациклический) называют деревом. Если в несвязном графе все компоненты - деревья, его называют лесом. Идея дерева и леса знакома вам по гл.1. В графе-дереве имеется в точности n-1 ребро, т.е. m=n-l. Добавьте в него новое ребро и возникнет цикл. В любом связном графе (подграфе) можно выделить (обычно не единственным образом) дерево, содержащее все узлы графа (подграфа) - каркас или остов. Ребра, не принадлежащие каркасу, называют хордами. Например, в подграфе G' можно выделить каркас, включающий ребра {2, 1}, {2, 5}, {2,6}. При таком каркасе ребра {1, 6}, {1, 5}, {5, 6} будут считаться хордами.

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

m - n + 1, ибо из m ребер n - 1 ребро образует каркас, а про­чие m - n + 1 ребер - хорды.

Задание 6.1.

• Выразите через n и k число ребер в лесе, содержащем k деревьев, и цикломатическое число для графа, в котором k компонент связности (здесь используйте также и m).