Алгоритмы решения некоторых теоретико-графовых задач

Автор-составитель данной статьи не ставил перед собой задачу строго и формально изложить основы теории графов. Читатели, интересующиеся ее математической стороной, могут обратиться к [1-3, 6]. В этой статье понятия теории графов излагаются с прикладной, можно сказать - программистской точки зрения. Основное внимание уделяется алгоритмам решения типичных задач на графах. В то же время, наряду с неформальным изложением, используются относительно строгие определения, теоремы и доказательства. Надеюсь, что этот текст поможет читателю получить представление о полезности теории графов при решении практических задач.

Алгоритмы, о которых рассказывается в статье, были собраны из различных источников, в числе которых стоит отметить [4-5]. Многие алгоритмы реализованы составителем в объектно-ориентированной библиотеке AGraph, написанной на языке Object Pascal.

Основные определения
Изоморфизм, гомеоморфизм
Пути и циклы
Деревья
Цикломатическое число и фундаментальные циклы
Планарные графы (привести другие критерии планарности)
Раскраски графов (добавить простые оценки!)
Графы с атрибутами
Независимые множества и покрытия

Кратчайшие пути
Кратчайшее остовное дерево
Эйлеровы пути и циклы. Задача почтальона
Гамильтоновы циклы. Задача коммивояжера
Поиск оптимальной вершинной раскраски
Распознавание изоморфизма графов

Граф (graph) - пара G=(V,E), где V - множество объектов произвольной природы, называемых вершинами (vertices, nodes), а E - семейство пар ei=(vi1, vi2), vij О V, называемых ребрами (edges). В общем случае множество V и/или семейство E могут содержать бесконечное число элементов, но мы будем рассматривать только конечные графы, т.е. графы, у которых как V, так и E конечны.

В приведенном определении графа E не случайно названо семейством пар, а не множеством. Дело в том, что элементы E могут быть неуникальны, т.е. возможны кратные ребра. Существует другое, более корректное определение: граф определяется как тройка G=(V,E, j ), где V - множество вершин, E - множество ребер, а j = j (v,u,e) - трехместный предикат (булевская функция от трех переменных), возвращающая True тогда и только тогда, когда ребро e инцидентно вершинам v и u. Однако такие "строгости" в нашем изложении являются чрезмерными.

Если порядок элементов, входящих в ei, имеет значение, то граф называется ориентированным (directed graph), сокращенно - орграф (digraph), иначе - неориентированным (undirected graph). Ребра орграфа называются дугами (arcs). В дальнейшем будем считать, что термин "граф", применяемый без уточнений "ориентированный" или "неориентированный", обозначает неориентированный граф.

G Если e=(v,u), то вершины v и u называются концами ребра. При этом говорят, что ребро e является смежным (инцидентным) каждой из вершин v и u. Вершины v и u также называются смежными (инцидентными). В общем случае, допускаются ребра вида e=(v,v); такие ребра называются петлями.

Степень вершины графа - это число ребер, инцидентных данной вершине, причем петли учитываются дважды. Поскольку каждое ребро инцидентно двум вершинам, сумма степеней всех вершин графа равна удвоенному количеству ребер: Sum(deg(vi), i=1..|V|)=2 Ч |E|.

Граф, не содержащий петель и кратных ребер, называется обыкновенным, или простым графом (simple graph). Во многих публикациях используется другая терминология: под графом понимается простой граф, граф с кратными ребрами называют мультиграфом, с петлями - псевдографом.

Некоторые классы графов получили особые наименования. Граф с любым количеством вершин, не содержащий ребер, называется пустым. Обыкновенный граф с n вершинами, любая пара вершин которого соединена ребром, называется полным и обозначается Kn (очевидно, что в полном графе n(n-1)/2 ребер).

Граф, вершины которого можно разбить на непересекающиеся подмножества V1 и V2 так, что никакие две вершины, принадлежащие одному и тому же подмножеству, не смежны, называется двудольным (или бихроматическим, или графом Кенига) и обозначается Bmn (m=|V1|, n=|V2|, m+n=|V|). Полный двудольный граф - такой двудольный граф, что каждая вершина множества V1 связана со всеми вершинами множества V2, и наоборот; обозначение - Kmn. Замечание: полный двудольный граф Bmn не является полным (за исключением B11=K2).

Подграфом, или частью графа G=(V,E) называется такой граф G'=(V',E'), что V' Н V и две несмежные вершины в G не смежны в G'. Полным подграфом называется подграф, любая пара вершин которого смежна.

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

G2), если между графами существует взаимно-однозначное отображение j : G1 < G2 (V1 < V2, E1 < E2), которое сохраняет соответствие между ребрами (дугами) графов, т.е. для любого ребра (дуги) e=(v,u) верно: e'= j (v,u)=( j (v), j (u)) (e О E1, e' О E2). Отображение j называется изоморфным отображением.

Иными словами, изоморфные графы различаются только обозначением вершин.

Изоморфные графы. Одно из изоморфных отображений: (0,0), (1,3), (2,5), (3,6), (4,7), (5,2), (6,1), (7,4), (8,9), (9,8).

Характеристики графов, инвариантные относительно изоморфизмов графов (т.е. принимающие одинаковые значения на изоморфных графах), называются инвариантами графов.

Подразделением ребра (v1,v2) графа называется операция добавления в граф вершины v' и замены этого ребра на два смежных ребра (v1,v') и (v',v2): V'=V+

📎📎📎📎📎📎📎📎📎📎