Элементы теории графов

Лекция 3 Элементы теории графов Среди разнообразных задач дискретной оптимизации выделяются задачи оптимизации на графах. Во-первых, графами моделируются многие разнообразные реальные системы, в силу чего задачи оптимизации таких систем представляются именно как задачи оптимизации на графах. Во-вторых, специфические свойства и геометрическая наглядность многих объектов, связанных с графами – путей, циклов, остовных деревьев, разрезов, потоков и пр. – позволяет предложить эффективные методы выбора из них объектов, оптимальных в том или ином смысле. В третьих, многие общие и частные задачи дискретной оптимизации, в которых нет никакого упоминания о графах, тем не менее естественно представляются как задачи оптимизации на графах. Рассмотрим основные понятия. 1. Понятие и определение графа 2. Внутренне и внешне устойчивые множества вершин 3. Пути в графах 4. Связность и компоненты связности 5. Эйлеровы циклы 6. Двудольные графы В лекции рассматриваются графы – объекты, позволяющие просто представлять, точно формулировать и эффективно решать многие теоретические и прикладные задачи. Даются содержательное и формальное определения графа (как в ориентированном, так и неориентированном случаях). Определяются базовые понятия и термины, связанные с графами. Все понятия, связанные с взвешенными графами, т.е. с графами, вершинам и/или рёбрам которых сопоставлены некоторые числа – стоимости, длины и т.д., будут рассмотрены далее. 1. Понятие и определения графа Во многих случаях жизни привычка толкает нас рисовать на бумаге точки, изображающие населенные пункты, агрегаты, людей, химические вещества и т.д., и соединять эти точки линиями или стрелками, указывающими на связи между соответствующими объектами. Такие схемы встречаются всюду под разными названиями: карты дорог, технологические схемы предприятий, диаграммы организаций, электрические цепи, сети коммуникаций, блок-схемы алгоритмов, генеалогические деревья и пр. Хотя такого рода объекты изучались достаточно давно (начиная с Эйлера), немецкий математик Д. Кёниг был первым, кто предложил называть такие схемы «графами» и систематически изучать их свойства (в 1936 году). Граф характеризует связи между объектами; условно эти объекты изображаются точками, а связи между ними – линиями, соединяющими соответствующие точки. При этом положение точек, наклон и длина линий совершенно не имеют значения (в отличие, например, от изображений в геометрии); важно лишь то, какие именно пары точек соединены, а какие – нет. Для удобства будем обозначать вершины натуральными числами (вообще говоря, их можно обозначать любыми символами). Пример 1. На рис.1 приведен пример трёх графов. На первый взгляд эти графы различны. Однако на самом деле во всех трёх случаях изображен один и тот же граф. Действительно, во всех трех изображениях соединены между собой те же самые пары точек: {1, 2}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {2, 5}, {3, 4}, {4, 5}; никакие другие пары точек не соединены ■ Рис.1 В одних случаях при описании связей между объектами «направление» связи не имеет значения. Соответствующие точки в графе соединяются линией без стрелки (как на рис.1); граф в этом случае называется неориентированным. В других случаях важно не только то, что объекты связаны, но и то, как именно «направлена» эта связь. Соответствующие точки в графе соединяются линией со стрелкой; граф в этом случае называется ориентированным. С помощью неориентированных графов удобно представлять, например, карты дорог; технологические схемы естественно описывать с помощью ориентированных графов. Пример ориентированного графа (так называемая «сеть питания») показан на рис.2. 1.1. Формальное определение графов. Нам понадобятся введённые в разделе 3.5 понятия функции типа A→B, инъективной функции, множеств отправления, прибытия, определения и значения функции, а также введённое в разделе 3.1 понятия кортежа (пары и тройки). Рис.2 1.1.1. Определение неориентированных графов. Обозначим через X1-2 множество всех одно- и двухэлементных подмножеств множества X. Дадим теперь необходимые формальные определения. Неориентированным графом G называется тройка V, E, F, где V – множество вершин графа, E – множество его рёбер, F – всюду определённая функция типа E→V1-2 (т.е. функция, у которой область определения совпадает с областью отправления). Это определение может показаться сложным и запутанным, особенно в сравнении с интуитивно ясным представлением о графе, данном в примере 1. Остановимся на этом подробнее. Пример 2. Рассмотрим граф, показанный на рис.3. В этом графе множество рёбер E = {a, b, c, d, e, f, g}; множество вершин V = {1, 2, 3, 4}; V1-2 = {{1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}}. Рёбра a и b соединяют одни и те же вершины 1 и 3; рёбра c и d соединяют одни и те же вершины 1 и 4; ребро e соединяет вершины 2 и 3; ребро f соединяет вершины 1 и 2; наконец, ребро g соединяет вершины 2 и 4. Именно такого рода соответствия формализуются с помощью функции F. В данном случае F(a) = F(b) = {1, 3}, F(c) = F(d) = {1, 4}, F(f) = {1, 2}, F(e) = {1, 3}, F(g) = {2, 4}. (1) Рёбра, соединяющие одну и ту же пару вершин, называются кратными. В рассматриваемом случае кратными являются рёбра a и b, а также c и d. Заметим, что концы определены для всех рёбер, что и означает, что функция F всюду определена. Другими словами, никаких «болтающихся» концов у рёбер нет ■ В общем случае можно сказать, что значение функции F на произвольном ребре p, т.е. одно- или двухэлементное множество вершин, как раз представляет собой множество концов данного ребра p (сравните рис.3 и соотношения (1) и убедитесь в этом!). В примере 2 все эти множества были двухэлементными, т.е. рёбра, у которых оба конца совпадают, в графе на рис.3 отсутствуют. Однако в общем случае такие рёбра могут присутствовать. Пример 3. Рассмотрим граф, показанный на рис.4. В этом графе F(a) = {1}, F(b) = {1, 2}. Рёбра, у которых концы совпадают (с вершиной A), называются петлями при вершинах (вершине A). Вообще говоря, петель при одной и той же вершине (т.е. кратных петель) может быть несколько, как и рёбер, соединяющих одну и ту же пару разных вершин ■ Рис.3 Рис.4 Во многих случаях разным рёбрам графа соответствуют разные пары вершин (если они не являются петлями) и разные вершины (если они являются петлями). В этих случаях функция F является инъекцией (см. раздел 3-5), а соответствующий граф называется простым. Напомним, что инъективной функцией, или инъекцией, называется функция F, такая, что [x ≠ y] → [F(x) ≠F(y)] (2) (определение импликации P → Q см. в разделе 1.2). Поскольку каждое ребро простого графа однозначно определяется своими концами, то такое ребро можно однозначно задать двухэлементным или одноэлементным (для петли) множеством его концов. Таким образом, можно дать следующее формальное определение. Неориентированным простым графом G называется пара V, E, где V – множество вершин графа, E V1-2 – множество его рёбер. Здесь одноэлементное множество из V, т.е. множество вида {i}, означает ребро – петлю при вершине i, а двухэлементное множество {i, j} означает ребро с концами i и j. Заметим также, что иногда в литературе простые графы называются графами, а графы, содержащие кратные рёбра – мультиграфами. Пример 4. Рассмотрим граф, показанный на рис.4. Этот граф является простым. Поэтому его можно задать парой множеств V, E, где V = {1, 2} – множество вершин графа, E = {{1}, {1, 2}} – множество его рёбер ■ Пример 5. Граф, показанный на рис.1, является простым графом без петель. Он задаётся парой множеств V, E, где V = {1, 2, 3, 4, 5} – множество его вершин, E = {{1, 2}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {2, 5}, {3, 4}, {4, 5}} – множество его рёбер ■ Поскольку простой граф – частный случай графа, то введённое выше задание графа в виде тройки V, E, F является более общим и может быть использовано во всех случаях, в том числе и для простых графов. В то же время задание парой V, E, которое применимо ко всем простым парам, не может использоваться в общем случае: если несколько рёбер имеют общие концы i и j, то их, конечно, нельзя задать одним и тем же двухэлементным множеством {i, j}. Следует сказать, что задание парой проще, чем задание тройкой. Поэтому во всех случаях, когда это возможно, т.е. для простых графов, будем использовать задание парой V, E. Резюмируем рассмотренные примеры 1 – 5. Граф на рис.1 задаётся парой V, E, где V = {1, 2, 3, 4, 5}, E = {{1, 2}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {2, 5}, {3, 4}, {4, 5}}. Граф на рис.3 задаётся тройкой V, E, F, гдеV = {1, 2, 3, 4}, E ={a, b, c, d, e, f, g}, F(a) = F(b) = {1, 3},F(c) = F(d) = {1, 4}, F(f) = {1, 2}, F(e) = {1, 3}, F(g) = {2, 4}. Граф на рис.4 может быть задан как парой V, E, где V = {1, 2}, E = {{1}, {1, 2}}, так и тройкой V, E, F, где V = {1, 2}, E ={a, b}, F(a) = {1}, F(b) = {1, 2}. В связи с введёнными способами задания графов (напомним, что пока рассматриваются только неориентированные графы) предлагаются следующие виды стандартных заданий: 1) по заданному формальному описанию (в виде тройки или пары) нарисовать граф; 2) по заданному изображению дать формальное описание графа в виде пары V, E(если граф простой) или тройки V, E, F (в противном случае). Если номера вершин и/или имена рёбер на рисунке не указаны, дать их самостоятельно. Конечно, существует много других способов формального задания графов, один из которых описан далее, в разделе 4.1. В основном выбор формального задания графа (структуры данных) определяется эффективностью алгоритма, при программной реализации которого этот вид задания используется. Подробнее эти вопросы рассматриваются в других курсах (например, в курсе «Структуры и алгоритмы обработки данных»). 1.1.2. Определение ориентированных графов. Оно во многом схоже с определением неориентированных графов. Ориентированным графом G называется тройка V, A, F, где V – множество вершин графа, А – множество его дуг, F – всюду определённая функция типа А→V2 (напомним, что через V2 обозначается прямое произведение (см. раздел 1-3.2) множества вер-шин V на себя или V×V, т.е. множество всех упорядоченных пар x, y, где x, yV). В отличие от двухэлементных множеств {x, y}, в которых по самому смыслу слова «двухэлементный» x и y не совпадают, в паре x, y компоненты могут совпадать. Это определение близко по смыслу к определению неориентированных графов. Именно, F(a) = i, j означает, что дуга a выходит из вершины i и входит в вершину j; если же i = j, то это означает, что данная дуга является петлёй при вершине i. Как и в неориентированном случае, если функция F инъективна, то соответствующий граф называется простым; при этом для каждой пары вершин i, j существует не более одной дуги с началом i и концом j. Поэтому здесь также можно задавать любую дугу упорядоченной парой i, j, состоящей из её начала i и конца j, и представлять граф G в виде пары V, A, где множество дуг AV2. Обратим внимание на то, что дуги i, j и j, i являются разными. Для сокращения записи иногда (если это не вызовет недоразумений) неориентированные графы будем называть просто графами, а ориентированные – орграфами. Пример 6. Граф на рис.2 является простым орграфом без петель. Занумеруем его вершины так: Лисы – 1; Насекомые – 2; Трава – 3; Олени – 4; Птицы – 5. Тогда G = V, A, где V = {1, 2, 3, 4, 5}, А = {1, 2, 1, 5, 2, 3, 4, 3, 5, 2, 5, 3} ■ 2. Внутренне- и внешне устойчивые множества вершин Дадим определения сразу для неориентированного и ориентированного случаев, учитывая, что эти определения очень похожи (отличия будем указывать в скобках). Две различные вершины, которые соединены ребром (дугой), т.е. являющиеся концами одного и того же ребра (дуги), называются смежными. В противном случае две вершины не смежны. Множество X вершин графа G, любые две из которых не смежны, называется внутренне устойчивым, а максимально возможное число элементов внутренне устойчивого множества − числом внутренней устойчивости графа G (обозначается α(G)). Сразу поясним это не очень простое понятие. Прежде всего, любое множество вершин, состоящее из одной вершины, является по определению внутренне устойчивым как в неориентированном, так и в ориентированном случае. Действительно, определение внутренней устойчивости множества вершин X, как и почти все математические определения, является импликацией. Его можно переформулировать так: «Если любые две разные вершины множества X не смежны, то множество X называется внутренне устойчивым» или, пользуясь определёнными в главе 1-4 кванторами, короче (aX)(bX)[(a ≠b)→(a не смежна с b)]. (3) Но если множество X состоит из одной вершины, то посылка a ≠b импликации (3) всегда ложна, поскольку a и b – две разные вершины из множества X. Напомним, что по определению импликации (см. раздел 1-2.1.4), импликация с ложной посылкой всегда истинна «в силу ложности посылки». Но это и означает истиннось импликации (3), что и означает внутреннюю устойчивость любого одноэлемнтного множества. Утверждение 1. Любое подмножество внутренне устойчивого множества внутренне устойчиво Действительно, по определению, во внутренне устойчивом множестве никакие две вершины не соединены ребром. Значит, этим же свойством обладает и любое его подмножество ■ Внутренне устойчивое множество вершин называется максимальным по включению, если оно не содержится ни в каком другом внутренне устойчивом множестве. Утверждение 1 позволяет при поиске всех внутренне устойчивых множеств ограничиться поиском только максимальных по включению внутренне устойчивых множеств. Действительно, всякое внутренне устойчивое множество либо само является максимальным по включению, либо содержится в некотором максимальном по включению внутренне устойчивом множестве. (Заметим, что таких множеств может быть несколько). Поэтому семейство всех максимальных по включению внутренне устойчивых множеств определяет все внутренне устойчивые множества: множество является внутренне устойчивым, если оно содержится хотя бы в одном максимальном по включению внутренне устойчивом множестве. Пример 7. Проиллюстрируем понятия внутренней устойчивости множества вершин в неориентированном графе. Для этого рассмотрим граф, показанный на рис.5а. На рис.5б – 5е показаны все максимальные по включению внутренне устойчивые множества в данном графе. На каждом из этих рисунков видно, что все выделенные большими кружками вершины не соединены непосредственно друг с другом рёбрами. Ясно также, что при добавлении любой вершины все эти множества перестают быть внутренне устойчивыми – появляются рёбра. Обратим внимание на то, что максимальные по включению внутренне устойчивые множества могут содержать различное число вершин – три на рис.5б – 5г и два на рис.5д и 5е. Множество, показанное на рис.5ж, является внутренне устойчивым, но не максимальным по включению. Оно содержится в множестве, показанном на рис.5б. Наконец, множество, показанное на рис.5з, не является внутренне устойчивым. Входящие в него вершины 5 и 6 соединены ребром. Поскольку максимальное число вершин во внутренне устойчивом множестве равно 3, то число внутренней устойчивости α(G) = 3. Рис.5а. Исходный граф Рис.5б. Максимальное по включению внутренне устойчивое множество {1,3,4} Рис.5в. Максимальное по включению внутренне устойчивое множество {1,3,5} Рис.5г. Максимальное по включению внутренне устойчивое множество {1,3,6} Рис.5д. Максимальное по включению внутренне устойчивое множество {2,5} Рис.5е. Максимальное по включению внутренне устойчивое множество {2,6} Рис.5ж. Внутренне устойчивое множество {1,4}, не максимальное по включению Рис.5з. Множество вершин {2,5,6}, не являющееся внутренне устойчивым Можно проверить, что любое множество, содержащее 4 вершины, не будет внутренне устойчивым. Действительно, любое внутренне устойчивое множество не может содержать никаких двух вершин из подмножества {4,5,6}, так как они все попарно смежны (соединены рёбрами). Значит, в него может входить не более одной вершины из множества {4,5,6}. Но так как в нём должно быть 4 вершины, а всего есть 6 вершин, то в него должны входить все вершины из множества {1,2,3}. А так как вершины 1 и 2 смежны, то такое множество не может быть внутренне устойчивым. В силу того же утверждения 1 бóльшие множества вершин также не могут быть внутренне устойчивыми ■ В произвольном графе с небольшим числом вершин максимальные по включению внутренне устойчивые множества могут быть найдены простым перебором всех различных подмножеств, начиная с множества всех вершин. Однако самый простой и эффективный подход – внимательно посмотреть на граф собственными глазами (и подумать собственной головой). Конечно, в графах, содержащих порядка 15 и более вершин, такой просмотр практически нереален. Формальные алгоритмы решения данной задачи в силу своей сложности здесь не рассматриваются. Введём дальнейшие понятия. Множество X вершин графа G называется внешне устойчивым, если любая вершина из VX, т.е. вершина, не принадлежащая X, смежна хотя бы с одной вершиной из X (является концом некоторой дуги, начало которой принадлежит множеству вершин X, в ориентированном случае). Минимально возможное число элементов внешне устойчивого множества называется числом внешней устойчивости графа G (обозначается β(G)). Обратим внимание на то, что связность вершин внутри множества X не оказывает никакого влияния на данное свойство. Это значит, что добавление или удаление любого ребра (дуги) между вершинами из X не повлияет ни на наличие свойства внешней устойчивости у множества X, ни на его отсутствие. Обратим внимание, что в определении не требуется, чтобы какая-нибудь вершина из X была бы смежной со всеми вершинами из VX. Достаточно, если любая вершина из VX смежна хотя бы с какой-нибудь вершиной из X. Для разных «внешних» вершин (т.е. из VX) смежные с ними «внутренние» вершины (т.е. из X) могут (но не обязаны!) быть различными. Заметим, что само множество всех вершин V является внешне устойчивым в силу ложности посылки. Действительно, при X = V имеем VX = , т.е. вершин, не принадлежащих X, прос-то не существует. Как и определение внутренне устойчивого множества, определение внешне устойчивого множества является импликацией: (aVX)→(bX)(a смежна с b), (4) которая всегда верна при ложной посылке (aVX). Имеет место простое Утверждение 2. Любое множество, содержащее внешне устойчивое множества вершин, также внешне устойчиво. Действительно, пусть внешне устойчивое множество XY. Для всякой вершины zVY верно zVX. Так как X – внешне устойчивое множество, то, по определению, z смежна с некоторой вершиной wX (является концом дуги с началом w). А в силу включения XY имеем wY. Таким образом, начав с произвольной вершины zVY, установили, что она смежна с некоторой вершиной wY (является концом дуги с началом w), что, по определению, означает внешнюю устойчивость Y ■ Внешне устойчивое множество называется минимальным по включению, если оно не содержит ни одного другого внешне устойчивого множества. В силу утверждения 2, для нахождения всех внешне устойчивых множеств достаточно найти только минимальные внешне устойчивые множества. Все остальные являются произвольными множествами, содержащими хотя бы одно минимальное по включению внешне устойчивое множество. Проиллюстрируем теперь это понятие на том же графе рис.5а. Пример 8. На рис.6а – 6е показаны все минимальные по включению внешне устойчивые множества в данном графе. На каждом из этих рисунков видно, что любая вершина, показанная чёрным кружком (как в исходном графе) соединена хотя бы с одной вершиной из внешне устойчивого множества, выделенных квадратами. Ясно также, что при удалении любой вершины из внешне устойчивого множества все эти множества перестают быть внешне устойчивыми – появляются вершины, не соединённые ни с одной из оставшихся вершин. Обратим внимание на то, что минимальные по включению внешне устойчивые множества могут содержать различное число вершин – две на рис.6а – 6в и три на рис.6г – 6е. Множество, показанное на рис.6ж, является внешне устойчивым, но не минимальным по включению. Оно содержит множества, показанные на рис.6б и 6в. Наконец, множество, показанное на рис.6з, не является внешне устойчивым. Вершина 3 не соединена ребром ни с вершиной 1, ни с вершиной 4, что противоречит определению внешне устойчивого множества. Поскольку минимальное число вершин во внешне устойчивом множестве равно 2, то число внешней устойчивости β(G) = 2. Рис.6а. Минимальное по включению внутренне устойчивое множество {2,4} Рис.6б. Минимальное по включению внутренне устойчивое множество {2,5} Рис.6в. Минимальное по включению внутренне устойчивое множество {2,6} Рис.6г. Минимальное по включению внутренне устойчивое множество {1,3,4} Рис.6д. Минимальное по включению внутренне устойчивое множество {1,3,5} Рис.6е. Минимальное по включению внутренне устойчивое множество {1,3,6} Рис.6ж. Внешне устойчивое множество {2,5,6}, не минимальное по включению Рис.6з. Множество вершин {1,4}, не являющееся внешне устойчивым Видно непосредственно на рисунке, что любое множество, содержащее одну вершину, не будет внешне устойчивым – просто потому, что в исходном графе нет ни одной вершины, соединённой со всеми остальными ■ Как и для внутренне устойчивых множеств, формальные алгоритмы решения данной задачи в силу своей сложности здесь не рассматриваются. Множество X вершин графа G, одновременно внутренне и внешне устойчивое, называется ядром графа G. Напомним, что определения внутренне устойчивого множества вершин в неориентрованном и ориентированном случаях совпадают. Совпадают и определения ядра. Отличаются только определения внешне устойчивого множества: в ориентированном случае требуется, чтобы дуга, соединяющая множества X и V X, имела направление от X к V X. Из определений внутренней и внешней устойчивости непосредственно следует, что: - любая изолированная вершина графа может быть добавлена к любому не содержащему её внутренне устойчивому множеству и это расширенное множество также будет внутренне устойчивым; - любое внешне устойчивое множество обязано содержать любую изолированную вершину. Из утверждений 1 и 2 непосредственно следует Утверждение 3. Множество вершин Z является ядром графа G тогда и только тогда, когда существуют минимальное по включению внешне устойчивое множество X и максимальное по включению внутренне устойчивое множество Y, такие, что XZY. (5)■ Если уже известны все минимальные по включению внешне устойчивые множества X1, …, Xs и все максимальные по включению внутренне устойчивые множества Y1, …, Yt, то утверждение 3 позволяет предложить следующий Алгоритм нахождения всех ядер графа. 1. Находим все такие пары индексов ái, jñ, такие, что XiYj. (6) 2. Для каждой такой пары индексов находим все множества Z, удовлетворяющие двойному включению XiZYj. (7) 3. Из всех множеств Z, найденных на шагах 1 и 2, выделяем все различные множества. Они и являются всеми ядрами графа ■ Алгоритм применим как в неориентрованном, так и в ориентированном случаях. Если включения (6) ни при каких i, j не выполняются, то это означает, что в данном случае ядра не существуют. Заметим также, что сами списки X1, …, Xs и Y1, …, Yt никогда не являются пустыми, поскольку в любом графе и орграфе любое одноэлементное множество является внутренне устойчивым, а множество всех вершин – внешне устойчивым, в силу ложности посылки. Пример 9. Рассмотрим снова граф на рис.5а. Максимальными по включению внутренне устойчивыми множествами являются множества Y1={1,3,4}, Y2={1,3,5}, Y3={1,3,6}, Y4={2,5}, Y5 ={2,6} (см. рис. 5). Минмальными по включению внешне устойчивыми множествами являются множества X1={2, 4}, X2={2,5}, X3={2,6}, X4={1,3,4}, X5={1,3,5}, X6={1,3,6} (см. рис.6). По алгоритму нахождения ядер рассмотрим все пары множеств áXi, Yjñ, удовлетворяющие включению (6). Таковыми являются следующие пары: áX2, Y4ñ, áX3, Y5ñ, áX4, Y1ñ, áX5, Y2ñ, áX6, Y3ñ. Для всех этих пяти пар включения являются равенствами, т.е. Xi = Yj. Поэтому расположенные «между ними» (см. (7)) ядра Z совпадают с Xi = Yj. В данном случае получаем список ядер {2,5}, {2,6}, {1,3,4}, {1,3,5}, {1,3,6} (шаг 3 не потребовался, поскольку все эти множества различны). Таким образом, в данном случае множество ядер совпадает с множеством максимальных по включению внутренне устойчивых множеств. Такое совпадение не является общим правилом, однако важная связь между этими множествами в случае неоиентированных графом действительно присутствует. Эти вопросы будут рассмотрены немного далее ■ Пример 10. На рис.7 показан орграф из примера 6 (сеть питания) с пронумерованными вершинами 1 – 5. В этом орграфе внутренне устойчивыми множествами являются все 1-элементные множества {1}, {2}, {3}, {4}, {5} и 2-элементные множества {1,3}, {1,4}, {2,4}, {4,5}. Других внутренне устойчивых множеств в данном орграфе нет. Максимальными по включению являются только эти 2-элементные множества. Одноэлементных внешне устойчивых множеств в данном случае нет (так как нет ни одной вершины, откуда дуги ведут во все остальные). Единственным 2-элементным внешне устойчивым множеством вершин является {1, 4} (так как дуги 1, 5, 1, 2 и 4, 3 ведут из {1, 4} в 5, 2 и 3, т.е. во все остальные вершины, в соответствии с определением). Поэтому множество {1, 4} является минимальным по включению внешне устойчивым множеством. Далее, пусть X –любое внешне устойчивое множество в данном орграфе. Предположим, что вершина 1 не входит в X. Тогда, по определению для ориентированных графов, должна быть вершина в X, из которой выходит дуга с концом в вершине 1. Но поскольку в вершину 1 ни одна дуга не входит (см. рис.7), то сделанное предположение неверно. Поэтому вершина 1 входит в любое внешне устойчивое множество X. Принадлежность вершины 4 любому внешне устойчивому множеству вершин устанавливается точно также. Таким образом, множество вершин {1, 4} входит в любое внешне устойчивое множество. Следовательно, {1, 4} является единственным минимальным по включению внешне устойчивым множеством вершин. Сравнивая по алгоритму список максимальных по включению внутренне устойчивых множеств {1,3}, {1,4}, {2,4}, {4,5} и список минимальных по включению внешне устойчивых множеств вершин, состоящий из единственного множества {1,4}, сразу получаем, что единственным ядром является множество вершин {1,4} ■ Пример 11. Рассмотрим простой орграф без петель, показанный на рис.8. Единственными внутренне устойчивыми множествами вершин являются три одноэлементных множества {1}, {2}, {3}. Они же, естественно, максимальны по включению (так как бóльших внутренне устойчивых множеств нет). Найдём все минимальные по включению внешне устойчивые множества вершин. Как уже упоминалось выше, множество всех вершин является внешне устойчивым. Далее, 2-элементное множество {1,2} является внешне устойчивым, поскольку есть дуга 2,3 в единственную не входящую в {1,2} вершину 3. Точно также, внешне устойчивыми множествами являются {2,3} и {1,3}. Далее, 1-элементное множество {1} не является внешне устойчивым, потому что в графе нет дуги 1,3, что противоречит определению. Аналогично, 1-элементные множества {2} и {3} также не являются внешне устойчивыми. Таким образом, имеется список минимальных по включению внешне устойчивых множеств {1,2}, {2,3}, {1,3} и список максимальных по включению внутренне устойчивых множеств {1}, {2}, {3}. Условия (6) XiYj не выполняются уже потому, что все Xi состоят из двух элементов, а все Yj – из одного элемента. В силу утверждения 3 в данном случае ядра отсутсутствуют, так как включения (5) не могут иметь места ■ Рис.7 Рис.8 Примеры 10 и 11 показывают, что в ориентированных графах ядра могут быть, а могут и не быть. Возможно ли отсутствие ядер в неориентированных графах? Полный ответ на этот вопрос даёт Утверждение 4. В неориентированном графе любое максимальное по включению внутренне устойчивое множество является и внешне устойчивым, т.е. является ядром. Действительно, предположим, что максимальное по включению внутренне устойчивое множество вершин A не является внешне устойчивым. По определению, это означает, что существует вершина yVA)., не смежная ни с одной вершиной xA. Но тогда множество A{y} не содержит ни одного ребра, поскольку без вершины y, т.е. в самом множестве A, рёбер нет по определению внутренней устойчивости, а добавление y также не добавило рёбер по построению. Это означает, что множество A{y} внутренне устойчиво. Но тогда множество A, будучи внутренне устойчивым, не будем максимальным по включению, поскольку содержится в бóльшем внутренне устойчивом множестве A{y}, что противоречит предположению о максимальности A ■ Утверждение 4 даёт гарантию существования ядер в любых неориентированных графах. Значительно более сложный вопрос об условиях существования и единственности ядер в ориентированных графах здесь не рассматривается. 3. Пути в графах Как и в разделе 2, будем давать определения сразу для неориентированного и ориентированного случая, указывая отличия в скобках. Наиболее общим понятием является понятие пути (орпути). Путём (орпутём) в графе (орграфе) называется чередующаяся последовательность μ вершин и рёбер (дуг), начинающаяся и кончающаяся в вершинах: μ = v0, b1, v1, b2, ..., vk-1, bk,vk, (8) такая, что вершины vi и vi+1 соединены ребром (дугой) bk. Вершина v0 называется началом пути (орпути) μ, вершина vk – концом пути (орпути) μ, а число k, равное числу рёбер (дуг), входящих в путь (орпуть) – его длиной. Говорят также, что путь μ соединяет вершины v0 и vk (орпуть μ ведёт из v0 в vk). Обратным путём для пути μ называется путь μ–1 = vk, bk, vk-1, bk-1, ..., v1, b1, v0. Другими словами, путь μ–1 состоит из тех же самых вершин и рёбер, но проходимых в обратном порядке. Обратим внимание, что обратный путь определён только в неориентированном случае. Цепью (орцепью) называется путь (орпуть), в котором все рёбра (дуги) различны. Простой цепью (орцепью) называется цепь (орцепь), в которой все вершины различны. Путь (орпуть), в котором начало и конец совпадают, называется циклическим путём (орпутём). Циклический путь, являющийся цепью (орцепью), называется циклом (орциклом). Цикл (орцикл), в котором все вершины, кроме начала и конца, различны и не совпадают с началом, называется простым циклом (орциклом). Говорят, что не циклический путь ν содержится в не циклическом пути μ, если последовательность ν или последовательность ν–1 является подпоследовательностью последовательности μ. В ориентированном случае остаётся только часть этого определения: не циклический орпуть ν содержится в не циклическом орпути μ, если последовательность ν является подпоследовательностью последовательности μ. Для циклических путей последнее определение требуется модифицировать, учитывая то, что такой путь можно «обходить», начиная с любой вершины, отчего он, конечно же, не изменится. Поэтому можно дать такие четыре определения: 1) не циклический путь ν содержится в циклическом пути μ, если последовательность μ можно циклически перенумеровать так, что последовательность ν или последовательность ν–1 станет подпоследовательностью этой перенумерованной последовательности μ; 2) не циклический орпуть ν содержится в циклическом орпути μ, если последовательность μ можно циклически перенумеровать так, что последовательность ν станет подпоследовательностью этой перенумерованной последовательности μ; 3) циклический путь ν содержится в пути μ, если последовательность ν или последовательность ν–1 можно циклически перенумеровать так, что эта перенумерованная последовательность ν станет подпоследовательностью последовательности μ; 4) циклический орпуть ν содержится в орпути μ, если последовательность ν можно циклически перенумеровать так, что эта перенумерованная последовательность ν станет подпоследовательностью последовательности μ. Эти на первый взгляд сложные понятия разъясняются далее (см. примеры 17 – 21). Все вышеприведённые в данном разделе понятия относятся к произвольным графам и орграфам (см. раздел 1.1). В случае простых графов и орграфов понятие пути (орпути) упрощается: под путём (орпутём) понимается последовательность вершин μ = v0,v1, ..., vk-1,vk, (9) такая, что множество вершин {vi , vi+1} определяет ребро графа (петлю), если vi и vi+1 совпадают (пара вершин vi , vi+1 определяет дугу орграфа (петлю, если vi и vi+1 совпадают)). Напомним, что в простых графах (орграфах) пара вершин однозначно определяет ребро (дугу), в то время как в графах общего вида таких рёбер (дуг) может быть несколько (см. рис.3). Соответственно упрощаются все остальные приведённые выше определения – достаточно указывать только последовательности вершин. Приведём примеры, иллюстрирующие и разъясняющие введённые понятия. Пример 12. В графе, показанном на рис.9, обратным к пути μ = 1, f, 4, d, 2, c, 4, g, 3 является путь μ–1= 3, g, 4, c, 2, d, 4, f, 1. Обратным к циклическому пути μ = 1, f, 4, d, 2, e, 3, b, 1 является циклический путь μ–1 = 1, b, 3, e, 2, d, 4, f, 1 (проверьте!) ■ Пример 13. В графе, показанном на рис.10, обратным к простому пути μ = 2, 1, 4, 3 является простой путь μ–1 = 3, 4, 1, 2. Обратным к циклическому пути μ–1 = 2, 4, 1, 3, 4, 2 является циклический путь μ–1 = 2, 4, 3, 1, 4, 2 ■ Рис.9 Рис.10 Пример 14. В графе, показанном на рис.11 последовательность μ = 1, d, 3, e, 2, b, 1, a, 2, b, 1, c, 3 является путём с началом в вершине 1 и концом в вершине 3. Его длина, т.е. число входящих в него рёбер, равно 6. Этот путь не является цепью, так как не все его рёбра различны (ребро b встречается два раза). В этом же графе последовательность ν = 1, d, 3, e, 2, b, 1, c, 3 является цепью с началом в вершине 1 и концом в вершине 3. Эта цепь не является простой, так как в ней не все вершины различны (вершины 1 и 3 встречаются по два раза). Последовательность λ = 1, d, 3 является простой цепью. Последовательность λ* = 1, c, 3 также является простой цепью, отличной от простой цепи λ = 1, d, 3 (см. рис.11). Заметим, что все четыре рассмотренных в примере пути μ, ν, λ, λ* соединяют одну и ту же пару вершин 1 и 3 ■ Пример 15. Граф, показанный на рис.12 является простым графом, поэтому для задания путей можно пользоваться упрощёнными последовательностями, состоящими только из вершин. Последовательность μ = D, C, G, E, C, B, G, E, F является путём с началом в вершине D и концом в вершине F; его длина равна 8. Путь μ не является цепью, так как ребро {G, E} входит в него дважды. Последовательность ν = D, C, G, E, C, B, F является цепью, так как все её рёбра не повторяются (проверьте!), но она не является простой цепью, так как вершина C встречается в ней два раза. Последовательность λ = D, C, B, F является простой цепью, поскольку все её вершины различны. Заметим, что все три рассмотренные пути – μ, ν, λ – соединяют одну и ту же пару вершин D и F ■ Рис.11 Рис.12 Замечания в конце примеров 14 и 15 приводят к достаточно простому умозаключению, сформулированному в следующем утверждении. Утверждение 5. Для всякого пути (орпути), соединяющего две разные вершины, существует содержащаяся в нём цепь (орцепь), соединяющая те же две вершины. Для всякой цепи (орцепи), соединяющей две вершины, существует содержащаяся в ней простая цепь (орцепь), соединяющая те же две вершины ■ Заметим, что существующая в силу утверждения 5 цепь может совпадать с содержащим её путём (если сам путь уже является цепью); существующая в силу утверждения 5 простая цепь может совпадать с содержащей её цепью (если сама эта цепь уже является простой цепью). Пример 16. В графе, показанном на рис.13, последовательность μ = 1, a, 2, b, 1, a, 2 является путём. Этот путь не является цепью, поскольку он проходит два раза по ребру a. Двумя содержащимися в этом пути цепями являются только цепи ν = 1, a, 2 и ν* = 1, b, 2. Обе эти цепи уже являются простыми, и поэтому любая содержащаяся в одной из них простая цепь совпадает с содержащей цепью ■ Заметим также, что во всех рассмотренных в примерах 14 − 16 путях начальная и конечная вершины всегда различны, т.е. ни один из них не является циклическим путём. Пример 17. Рассмотрим простой граф, показанный на рис.14. Не циклический путь μ = 6, 2, 5 содержится в циклическом пути ν = 2, 5, 3, 6, 2, хотя последовательность μ не является подпоследовательностью последовательности ν. Действительно, если тот же самый циклический путь ν начать с вершины 6, т.е. записать в виде ν = 6, 2, 5, 3 ,6, то после такой перенумерации последовательность μ становится подпоследовательностью последовательности ν. Рас-смотрим теперь не циклический путь μ = 4, 1, 5 и циклический путь ν = 1, 4, 2, 5, 1. Последовательность 4, 1, 5 не является подпоследовательностью ни самой последовательности ν, ни любой её циклической перестановки: 4, 2, 5, 1, 4, 2, 5, 1, 4, 2, 5, 1, 4, 2, 5. Однако обратная последовательность μ= 5, 1, 4 содержится в циклически переставленной ν = 4, 2, 5, 1, 4. Значит, в силу введённых определений, путь μ = 4, 1, 5 содержится в циклическом пути ν ■ Рис.13 Рис.14 Пример 18. В графе, показанном на рис.11, последовательность μ = 1, d, 3, е, 2, е, 3, с, 1, b, 2, a, 1 является циклическим путём, но не является циклом, поскольку ребро е входит в него дважды. Содержащийся в пути μ путь ν = 1, d, 3, с, 1, b, 2, a, 1 является циклом, но не является простым циклом, так начальная и конечная вершина 1 входит в него 3 раза, вместо двух, требуемых определением. Наконец, содержащийся в пути ν путь λ = 1, d, 3, с, 1 является простым циклом ■ Пример 19. В графе, показанном на рис.12, последовательность μ = E, C, G,B, A, F, B, G, E является циклическим путём, но не является циклом, поскольку ребро {G,B} входит в него дважды. Содержащийся в пути μ путь ν = E, C, B, A, F, B, G, E является циклом, но не является простым циклом, так вершина B входит в него 2 раза. Наконец, содержащийся в пути ν путь λ = E, C, B, G, E является простым циклом ■ Имеет место утверждение, аналогичное утверждению 5 для не циклических путей. Утверждение 6. Для всякого циклического пути (орпути) есть содержащийся в нём цикл (орцикл). Для всякого цикла (орцикла) есть содержащийся в нём простой цикл (орцикл) ■ Пример 20. В орграфе, показанном на рис.15, последовательность μ = 1, b, 2, a, 1, d, 3, c, 1 является циклическим орпутём, который является орциклом. Этот орцикл содержит два простых цикла: ν1 = 1, b, 2, a, 1 и ν2 = 1, d, 3, c, 1. Кроме них, в данном орграфе есть простой орцикл 1, d, 3, e, 2, a, 1 ■ Пример 21. В орграфе, показанном на рис.16, имеется два орцикла: 1, 2, 3, 4, 5, 6, 1 и 7, 7. Они оба являются простыми орциклами ■ Рис.15 Рис.16 Введём ещё одно важное для дальнейшего понятие. Граф (орграф) называется ациклическим, если он не содержит циклов (орциклов). Рассмотрим подробнее ациклические орграфы. В ациклическом орграфе по самому определению отсутствуют орциклы и, следовательно, все орпути являются простыми. Однако для ациклических орграфов верен и более специальный факт, в каком-то смысле описывающий их структуру. Имеет место Утверждение 7. Пусть G(V, A) – простой ациклический орграф с множеством вершин V и множеством дуг A. Тогда множество вершин V разбивается на непересекающиеся подмножества V1, …, Vm, такие, что для любой дуги (p, q) графа G начало p содержится в множестве Vi c бóльшим номером, чем конец q. Доказательство этого утверждения, по сути, является алгоритмом построения указанных подмножеств. Поскольку граф ациклический, то в нём найдётся хотя бы одна вершина, из которой не выходят дуги. Обозначим множество всех таких вершин через V1. Удалим из графа G все вершины из V1 и все ведущие в них дуги. Оставшийся граф также будет ациклическим. Множество его вершин, из которых не выходят дуги, обозначим через V2. Продолжая этот процесс, получим разбиение с требуемыми свойствами (последний оставшийся граф Gm не может содержать дуг, иначе на нём процесс не мог бы окончиться) ■ Это утверждение будет использоваться несколько раз в различных главах пособия. Перед завершением этого раздела определим ещё одно важное «путевое» понятие. Маршрутом в графе (орграфе) называется чередующаяся последовательность μ вершин и рёбер (дуг), начинающаяся и кончающаяся в вершинах v0 и vk: μ = v0, b1, v1, b2, ..., vk–1, bk, vk, такая, что вер-шины vi и vi+1 соединены ребром (вершина vi соединена дугой с вершиной vi+1 или вершина vi+1 соединена дугой с вершиной vi). Вершина v0 называется началом маршрута μ, вершина vk – концом маршрута μ, а число k, равное числу рёбер (дуг), входящих в маршрут – его длиной. Говорят также, что маршрут μ соединяет вершины v0 и vk. Обратным маршрутом для маршрута μ называется маршрут μ–1 = vk, bk, vk-1, bk-1, ..., v1, b1, v0. Другими словами, маршрут μ–1 состоит из тех же самых вершин и рёбер, но проходимых в обратном порядке. Обратим внимание, что обратный маршрут, в отличие от обратного пути, определён как для графов, так и для орграфов. Дуга (vi, vi+1) называется прямой дугой маршрута μ, дуга (vi+1, vi) – обратной дугой маршрута μ. Из приведённого определения следует, что для неориентированных графов понятия пути и маршрута совпадают. Но для орграфов это понятия является новым. Можно сказать, что маршрут – это путь, который не принимает во внимание ориентации дуг. При произвольном изменении ориентаций в дугах орграфа каждый маршрут останется тем же самым маршрутом. 4. Связность и компоненты связности Вершина j графа (орграфа) называется достижимой из вершины i, если существует путь (орпуть) с началом в i и концом в j. Множество K вершин графа (орграфа) называется компонентой связности (сильной связности), если любые две вершины из K взаимно достижимы, и при этом множество K является максимальным по включению множеством, обладающим данным свойством (это означает, что при добавлении к K хотя бы одной новой вершины свойство взаимной достижимости теряется). Заметим, что множество, состоящее из одной вершины, является связным (в орграфе – сильно связным) в «силу ложности посылки», но далеко не всегда является компонентой связности (сильной связности), поскольку не обязано быть максимальным по включению. Заметим также, что множество всех вершин графа (орграфа) также не обязано быть компонентой связности (сильной связности). Если же граф (орграф) состоит из единственной компоненты, то он называется связным (сильно связным). Пример 22. Рассмотрим граф, показанный на рис.17. У него есть три компоненты связности: {A, B, C, D}, {E, F, G, H, I, J}, {R}■ Пример 23. Рассмотрим орграф, показанный на рис.18. В нём вершины 1 и 3 взаимно достижимы (с помощью дуг a и b), поэтому они по определению входят в одну и ту же компоненту сильной связности. Каждая из вершин 2 и 4 образует отдельную компоненту сильной связности, поскольку из 3 нельзя перейти в 4, а из 4 нельзя перейти в 2. Таким образом, у данного графа имеется три компоненты сильной связности: {1,3}, {2} и {4}■ Наличие нескольких кратных рёбер и любого числа петель, естественно, никак не сказывается на компонентах связности ни в неориентированном, ни в ориентированном случае. Поэтому в обоих случаях для нахождения компонент связности можно преобразовать граф к простому графу без петель, оставив по одному ребру (дуге) среди нескольких кратных и удалив все петли. Рис.17 Рис.18 Пример 24. Граф, показанный на рис.19a, не является простым и содержит петлю при вершине. После удаления кратной дуги и петли (а также введения нумерации вершин) получается простой граф, показанный на рис.19b, в котором, как и в исходном графе, имеется одна компонента связности. Рис.19a Рис.19b Пример 25. Орграф, показанный на рис.18, не является простым, поскольку дуги c и d кратны. После удаления одной из кратных дуг получается простой орграф, показанный на рис. 20. В нём, как и в исходном орграфе, содержатся те же компоненты сильной связности: {1,3}, {2} и {4}. Заметим, что дуги a и b в графе рис.18 не являются кратными, в отличие от дуг c и d ■ Рис.20 Компоненты связности (сильной связности) в небольших графах, показанных на всех предыдущих рисунках, находятся непосредственно (как говорят, «глазами»). Надо сказать, что «глазами» искались внутренне и внешне устойчивые множества вершин (см. примеры 7 и 8). Однако ведущую роль в решении прикладных задач дискретного характера играют алгоритмы. В этом разделе излагается алгоритм нахождения компонент связности неориентированных графов. Учитывая суть задания, можно обойтись простыми графами без петель. Аналогичный алгоритм для орграфов здесь не излагается. Прежде, чем перейти к формальным конструкциям, рассмотрим следующий Пример 26. На рисунке 21 показан граф, содержащий 300 вершин и около 1200 рёбер. Число компонент связности в нём равно двум. Однако даже в данном, сравнительно простом, случае проверить это «глазами», мягко говоря, затруднительно ■ 4.1. Алгоритм нахождения компонент связности простых неориентированных графов. Когда речь заходит о каких бы то ни было алгоритмах, первым – и часто определяющим –вопросом является вопрос о формальном представлении рассматриваемых объектов или, как часто говорят, о выборе соответствующей структуры данных. В разделе 1.1 было дано формальное представление простых неориентированных графов в виде пары V, E, где V = {1, 2, …, n} – множество вершин графа, EV1-2, где V1-2 – множество всех 1- и 2-элементных подмножеств множества вершин V. Двухэлементное множество {x, y}, принадлежащее E, интерпретируется как ребро с концами x и y. Однако в данном случае, как и во многих других, более адекватной структурой данных является следующая. Граф задаётся в виде массива, i-ый элемент которого соответствует вершине i. Сам же i-ый элемент является массивом, состоящим из номеров всех вершин, смежных с вер- Рис.21 шиной i. В рамках такой структуры удобно просматривать все вершины, смежные с данной, чем и оправдано их применение. Такое представление графов назовём массивом смежных вершин. Для орграфов аналогичное представление определяется как массив, i-ый элемент которого является массивом номеров всех вершин, в которые ведёт дуга из вершины i. Пример 27. Для графа, показанного на рис.5а, массив смежных вершин имеет следующий вид:  2, 1,3,4, 2, 2,5,6, 4,6, 4,5 ■ Пример 28. Для графа, показанного на рис.22 (полученным из графа на рис.17 перенуме-рацией вершин), указанное представление имеет следующий вид: 2,3,4, 1,3, 1,2,4, 1,3, 6, 8,9, 5,7,10, 6,8, 5,7, 5, 6, Λ . Обратите внимание на последний (11-ый) массив: поскольку вершина 11 изолирована, кортеж смежных с ней вершин пуст, а пустые кортежи обозначаются знаком Λ (см. раздел 3-1) ■ Пример 29. Для орграфа, показанного на рис.23, указанное представление имеет следующий вид:  3,4, 1,4, 2,4, Λ . На 4-ой позиции стоит пустой кортеж, так как из вершины 4 не выходит ни одна дуга ■ Далее рассматривается основной материал данного раздела. Предлагается алгоритм, по массиву смежных вершин определяющий компоненты связности графа. Суть его такова. Определим массив M длины n (через n обозначено число вершин графа). Присвоение i-ой вершине метки а означает формальную операцию присвоения M[i] = а. Начинаем с любой вершины (для определённости, с первой). Присваиваем ей метку –1. Пусть некоторое множество вершин имеет метки –1 и +1. Возьмём любую вершину x с меткой –1 (если таковая найдётся) и у всех вершин, смежных с ней и ещё не имеющих метку, Рис.22 Рис.23 поставим метку –1. После этого, независимо от того, была ли помечена хотя бы одна вершина, у вершины x заменим метку -–1 на +1. Если же ни одной вершины с меткой -–1 не найдётся, то все вершины с меткой +1 образуют 1-ую компоненту связности. Если больше непомеченных вершин нет, то граф состоит из одной компоненты связности. Если есть хоть одна непомеченная вершина y, то пометим её меткой –2 и повторим весь процесс с заменой 1 на 2. Далее, если ещё остались непомеченные вершины, пометим любую из них меткой –3, и т.д, вплоть до того, когда все вершины становятся помеченными. При этом все вершины с одной и той же меткой i образуют i-ую компоненту связности. Пример 30. Применим описанный алгоритм для графа из примера 28 (рис.22). Для него массив смежных вершин таков:  2,3,4, 1,3, 1,2,4, 1,3, 6,8,9, 5,7,10, 6,8, 5,7, 5, 6, Λ . 1. Инициализация. В данном случае число вершин равно 11. Поэтому определим массив M длины 11 и положим M[1] = –1. 2. В соответствии с алгоритмом положим M[2] = –1, M[3] = –1, M[4] = –1. 3. Поскольку помечены все вершины из списка смежных с вершиной 1 вершин 2, 3, 4, то положим M[1] = 1. 4. Возьмём следующую вершину 2 с меткой –1. Смежные с ней вершины 1, 3 уже помечены. В соответствии с алгоритмом положим M[2] = 1. 5. Возьмём следующую вершину 3 с меткой –1. Смежные с ней вершины 1, 2, 4 уже помечены. В соответствии с алгоритмом положим M[3] = 1. 6. Возьмём следующую вершину 4 с меткой –1. Смежные с ней вершины 1, 3 уже помечены. В соответствии с алгоритмом положим M[4] = 1. 7. Поскольку более вершин с меткой –1 нет (M[1] = M[2] = M[3] = M[4] = 1), то выбираем следующую непомеченную вершину 5 и присваиваем ей метку M[5] = –2. 8. В соответствии с алгоритмом для смежных с вершиной 5 вершин 6, 8, 9 положим M[6] = –2, M[8] = –2, M[9] = –2. 9. Поскольку помечены все вершины из списка смежных с вершиной 5 вершин 6, 8, 9, то положим M[5] = 2. 10. Возьмём следующую вершину 6 с меткой –2. Смежными с ней вершинами является 5 (уже помеченная), а также 7 и 10 (ещё непомеченные). В соответствии с алгоритмом положим M[7] = –2, M[10] = –2. 11. В соответствии с алгоритмом положим M[6] = 2. 12. Возьмём следующую вершину 7 с меткой –2. Смежными с ней вершинами является 6 и 8 (уже помеченные). В соответствии с алгоритмом положим M[7] = 2. 13. Возьмём следующую вершину 8 с меткой –2. Смежными с ней вершинами является 5 и 7 (уже помеченные). В соответствии с алгоритмом положим M[8] = 2. 14. Возьмём следующую вершину 9 с меткой –2. Смежной с ней вершинами является только 5 (уже помеченная). В соответствии с алгоритмом положим M[9] = 2. 15. Возьмём следующую вершину 10 с меткой –2. Смежной с ней вершинами является только 6 (уже помеченная). В соответствии с алгоритмом положим M[10] = 2. 16. Поскольку вершин с меткой –2 нет (M[5] = M[6] = M[7] = M[8] = M[9] = M[10] = 2), то выбираем следующую непомеченную вершину 11 и присваиваем ей метку M[11] = –3. 17. В соответствии с алгоритмом просматриваем все вершины, смежные с 11. Поскольку вершин, смежных с 11, не существует, то меняем метку M[11]: M[11] = 3. 18. Поскольку более вершин с меткой –3 не существует, то в соответствии с алгоритмом ищем непомеченную вершину. Так как таковых не имеется, то алгоритм останавливается. После остановки имеем следующий массив M: M = 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3. Это и означает, что 1-ую компоненту связности образуют вершины 1, 2, 3, 4; 2-ую компоненту связности – вершины 5, 6, 7, 8, 9, 10; 3-ью компоненту связности – изолированная вершина 11 ■ Число вершин, смежных вершине неориентированного графа, называется степенью данной вершины. 5. Эйлеровы циклы 5.1. Кёнигсбергские мосты. Не каждому городу выпадает честь быть отмеченным в такой точной науке, как классическая математика. Кёнигсберг же благодаря своим мостам и великому учёному-математику XVIII-го века Леонарду Эйлеру вошёл в число математических знаменитостей. Живя в Кёнигсберге, прогуливаясь по его набережным, Эйлер обратил внимание на оригинальное расположение семи мостов города. Причиной этому было причудливое течение рукавов Прегеля, соединенных протокой, охватывающих с севера и юга остров Кнайпхоф, а затем сливающихся вместе (рис.25). Эти мосты назывались так: 1. Kramer-Brucke (Лавочный мост) 2. GruneBrucke (Зелёный мост) 3. Kottel-Brucke (Потроховый мост) 4. Schmiede-Brucke (Кузнечный мост) 5. Holz-Brucke (Деревянный мост) 6. Hohe-Brucke (Высокий мост) 7. Honig-Brucke (Медовый мост) В 1736 Эйлер решил задачу, известную с тех пор как задача о кенигсбергских мостах: можно ли пройти по всем этим мостам и при этом вернуться в исходную точку так, чтобы по каждому мосту пройти только один раз. На рис.26 изображена условная схема семи мостов Кёнигсберга (заметим, что сейчас осталось только два из них). Упростим схему, показанную на рис.26. Для этого представим каждый из четырёх участков суши одной точкой, а каждый из мостов – линией, соединяющей соответствующие точки. В результате получаем граф, показанный на рис.3. Обратим внимание на то, что данный граф не Рис.26 является простым (см. пример 2). Нетрудно понять, что исходная задача стала значительно более обозримой. В уже введённых терминах (см. раздел 4) вопрос ставится так: существует ли в графе на рис.3 цикл, проходящий по всем рёбрам? Напомним, что однократность прохождения каждого ребра включена в определение цикла в разделе 4. Эйлер дал общий ответ на поставленный вопрос в следующем виде. Теорема. Для того чтобы данный связный граф имел цикл, проходящий по всем рёбрам, необходимо и достаточно, чтобы степени всех вершин графа были чётными (степень вершины определена в самом конце предыдущего раздела 4). Для того чтобы данный связный граф имел цепь между вершинами А и В, проходящую по всем рёбрам, необходимо и достаточно, чтобы степени всех вершин, кроме А и В, были чётными, а степени этих вершин были нечётными ■ Поскольку в графе на рис.3 степени некоторых вершин нечётны, то, следовательно, требуемого цикла не существует. В честь Эйлера циклы в неориентированных графах, проходящие по всем рёбрам, были названы эйлеровыми циклами, как и соответствующие цепи. 5.2. Алгоритм Флёри. Теорема Эйлера сама по себе является теоремой существования: в ней не говорится о том, как построить эйлеров цикл. Эффективный алгоритм был предложен французским математиком Флёри в 1873 году – почти через 150 лет после открытия Эйлера. Для его изложения нам понадобится важное понятие перешейка в графе. Перешеек – это ребро, удаление которого разделяет связную компоненту графа на две несвязные части. Пример 31. Найдём все перешейки в графе, показанном на рис.27a. Граф состоит только из одной компоненты связности, так что надо найти каждое ребро, удаление которого делает граф несвязным. Ребро {3,5} является перешейком; его удаление делает граф несвязным, как показано на рис. 27b. Ребро {7,8} также является перешейком; его удаление делает граф несвязным, как показано на рис.27c; при этом вершина 8 образует отдельную компоненту связности. Удаление ребра {6,7} не приводит к разделению графа, как показано на рис.27d; то же самое относится к удалению любого ребра (кроме {3,5}и {7,8}). Алгоритмтм Флёри. 1. Начинаем с любой вершины. Проходим вдоль любого ребра до другой вершины. Запоминаем это ребро как начало цикла и удаляем его из графа. 2. Пусть мы достигли некоторой вершины. Выбираем любое выходящее из неё ребро, с одним условием: не выбираем перешеек, если есть другая возможность. Проходим вдоль выбранного ребра до другой вершины. Добавляем это ребро в цикл и удаляем его из графа. 3. Выполняем шаг 2 до тех пор, пока не удалим все рёбра из графа ■ Рис.27 Пример 32. Применималгоритм Флёри к графу, показанному на рис.28a. Прежде всего проверяем, что граф связен и степени всех вершин чётны. По теореме Эйлера из этого следует, что эйлеров цикл в таком графе должен быть. Рис.28 Начинаем процесс с вершины 3. Из 3 можно двигаться либо в 2, либо в 5. Пойдём по направлению к 5, удалив ребро {3,5} (на рисунке 28b указаны номера удаляемых рёбер в порядке их удаления). Таким образом, началом искомого цикла является ребро {3,5}. Далее можно двигаться в вершины 4, 6 или 7. Поскольку ни одно из рёбер {5,4}, {5,6} и {5,7} в графе после удаления ребра {3,5} не является перешейком, то можно выбрать в качестве 2-го ребра цикла любое из этих трёх рёбер. Выбираем ребро {5,7}. На рис.28b это ребро имеет номер 2, а начало искомого цикла выглядит так: 3→5→7. Далее, из вершины 7 можно перейти в вершины 1, 4 или 6. Однако ребро {7,1} является перешейком в графе, полученном удалением рёбер {3,5} и {5,7} (см. рис.28b). Так как есть другие возможности ({7,4} и {7,6}), в соответствии с алгоритмом Флёри выберем одну из них. Выбрав {7,6}, продлеваем строящийся цикл этим самым ребром {7,6} и получаем 3→5→7→6; удаляемые рёбра и модифицированный граф показаны на рис.28b. Заметим, что выбор пере-шейка {7,1} в графе, показанном на рис.28b, и его последующее удаление привели бы к невозможности когда-либо пройти по рёбрам {7,4} и {7,6}. Это поясняет условие на шаге 2 алгоритма Флёри. Граф, оставшийся после удаления первых трёх рёбер искомого цикла – {3,5}, {5,7} и {7,6} – показан на рис.28с. Из очередной вершины 6 в графе рис.28с выходит только одно ребро {6,5}, которое является перешейком в этом графе. В соответствии с алгоритмом Флёри, мы должны двигаться далее по этому ребру {6,5}, несмотря на то, что {6,5} является перешейком, так как других возможностей нет. Далее все последующие рёбра определяются также совершенно однозначно (см. рис.28с). В результате получаем эйлеров цикл 3→5→7→6→5→4→7→ 1→2→3. В него по одному разу входят все 9 рёбер рассматриваемого графа. Полная последовательность удаляемых по порядку рёбер представлена на рис.28d ■ 6. Двудольные графы В заключение данной главы рассмотрим один специальный класс простых неориентированных графов – так называемые двудольные графы. Они широко используются в приложениях. Граф называется двудольным, если множество его вершин можно разбить на два непустых подмножества (доли), так что любое его ребро соединяет две вершины из разных долей (эквивалентно: концы любого ребра принадлежат разным долям). Из этого определения следует, что двудольный граф не содержит петель. Множество рёбер двудольного графа, которые не имеют общих вершин, называется паросочетанием. Паросочетание, содержащее максимальное число рёбер, называется максимальным паросочетанием. Алгоритмы поиска максимальных (а также некоторых других) паросочетаний рассмотрены в главе 9 и разделе 13-1. Пример 33. Двудольный граф показан на рис.29. Множество X = {{1,7}, {3,11}, {5,10}}, состоящее из трёх рёбер является паросочетанием, поскольку входящие в него рёбра не имеют общих концов. Множество Y = { {4,7}, {1,8}, {3,9}, {5,10}, {6,11} }, состоящее из пяти рёбер, также является паросочетанием. Его максимальность следует из того, что «нижняя» доля содержит 5 вершин, в силу чего паросочетания, состоящего более чем из 5 рёбер, просто не существует – если бы оно было, то по крайней мере два его ребра были бы инцидентны одной вершине, что противоречит определению паросочетания ■ Рис.29. Двудольный граф Задания Задание 1. По заданному формальному описанию нарисовать граф (см. примеры 1 – 5). 1. G = V, E, F, где V = {1, 2, 3, 4}, E ={a, b, c, d, e, f, g, h}, F(a) = F(b) = {1, 3}, F(c) = F(d) = {2, 4}, F(e) = {2, 3}, F(f) = {1, 4}, F(g) = {3, 4}, F(h) = {1, 2}. 2. G = V, E, где V = {1, 2, 3, 4}, E = {{1, 2}, {2, 3}, {3, 4}, {1, 4}, {2, 4}}. 3. G = V, E, F, где V = {1, 2, 3}, E ={a, b, c, d, e, f}, F(a) = F(b) = {1, 2}, F(c) = F(d) = {1, 3}, F(e) = F(f) = {2, 3}. 4.G = V, E, F, где V = {1, 2, 3}, E ={a, b, c, d, e}, F(a) = F(b) = {1, 2}, F(c) = F(d) = {1, 3}, F(e) = {2, 3}. 5. G = V, E, где V = {1, 2, 3, 4}, E = {{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}}. 6. G = V, E, гдеV = {1, 2, 3, 4, 5, 6}, E = {{2}, {6}, {1, 4}, {1, 5}, {1, 6}, {2, 5}, {3, 6}}. 7. G = V, E, F, где V = {1, 2, 3, 4}, E ={a, b, c}, F(a) = F(b) = {1, 2}, F(c) = {3, 4}. 8. G = V, E, где V = {1, 2, 3, 4, 5, 6, 7}, E = {{7}, {1, 2}, {2, 3}, {3, 4}, {5, 6}, {1, 6}}. 9. G = V, E, где V= {1, 2, 3, 4, 5}, E = {{5}, {1, 2}, {2, 3}, {3, 4}, {4, 5}, {1, 5}}. 10. G = V, E, F, где V = {1, 2, 3}, E ={a, b, c, d, e}, F(a) = F(b) = {1, 2}, F(c) = {1, 3}, F(d) = {2, 3}, F(e) = {3}. 11. G = V, E, F, где V = {1, 2}, E ={a, b, c}, F(a) = F(b) = F(c) = {1, 2}. 12. G = V, E, где V = {1, 2, 3, 4}, E = {{1, 2}, {2, 3}, {3, 4}, {1, 4}, {2, 4}, {1, 3}}. 13. G = V, E, где V = {1, 2, 3, 4, 5, 6}, E = {{1, 4}, {1, 5}, {1, 6}, {2, 4}, {2, 5}, {2, 6}, {3, 4}, {3, 5}, {3, 6}}. 14. G = V, E, F, где V = {1, 2, 3, 4}, E ={a, b, c, d}, F(a) = F(b) = {1, 3}, F(c) = {1, 4}, F(d) = {2, 3}. 15. G = V, E, F, где V = {1, 2, 3, 4}, E ={a, b, c, d, e}, F(a) = {1, 4}, F(b) = {1, 2}, F(c) = {3, 4}, F(d) = F(e) = {2, 3} ■ Варианты неориентированных графов для заданий 2, 4, 6, 8, 10, 12 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 Варианты ориентированных графов для заданий 3, 5, 7, 9, 11, 13 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 Задание 2. Представить заданный граф парами V, E или тройками V, E, F (см. примеры 2 – 5). При необходимости дать имена рёбрам и вершинам ■ Задание 3. Представить заданный орграф парами V, А или тройками V, А, F (см. пример 6). При необходимости дать имена дугам и вершинам ■ Задание 4. В заданном графе найти все максимальные по включению внутренне устойчивые множества вершин, все минимальные по включению внешне устойчивые множества вершин и все ядра (см. примеры 7 – 9) ■ Задание 5. В заданном орграфе найти все максимальные по включению внутренне устойчивые множества вершин, все минимальные по включению внешне устойчивые множества вершин и все ядра (если они есть). Если ядер нет, то указать на это и объяснить, в чём дело (см. примеры 10 и 11) ■ Задание 6. В данном графе найти: 1) путь, не являющийся цепью; 2) содержащуюся в найденном в 1) пути цепь, не являющуюся простой, соединяющую те же самые вершины; 3)содержащуюся в найденной в 2) цепи простую цепь, соединяющую те же самые вершины. Если некоторые искомые объекты не существуют (как в примере 16), то объяснить это (см. примеры 14 – 17) ■ Задание 7. В данном орграфе найти: 1) орпуть, не являющийся орцепью; 2) не содержащуюся в найденном в 1) орпути орцепь, не являющуюся простой; 3) не содержащуюся в найденной в 2) орцепи простую орцепь. Если некоторые искомые объекты не существуют , то объяснить это (см. примеры 20 и 21)■ Задание 8. В данном графе найти: 1) циклический путь, не являющийся циклом; 2) содержащийся в найденном в 1) пути цикл, не являющийся простым; 3) содержащийся в найденном в 2) цикле простой цикл. (см. примеры 18 – 19) ■ Если некоторые искомые объекты не существуют, то объяснить это ■ Задание 9. В данном орграфе найти: 1) циклический орпуть, не являющийся орциклом; 2) содержащийся в найденном в 1) орпути орцикл, не являющийся простым; 3) содержащийся в найденном в 2) орцикле простой орцикл. Если некоторые искомые объекты не существуют, то объяснить это (см. примеры 20 и 21) ■ Задание 10. В данном графе «найти глазами» компоненты связности (см. примеры 22 и 24) ■ Задание 11. В данном орграфе «найти глазами» компоненты сильной связности (см. примеры 23 и 25) ■ Задание 12. Привести данный граф, если он содержат кратные рёбра и / или петли, к простому графу без петель. В качестве ответа нарисовать пару «исходный – изменённый граф». Если исходный граф не содержал кратных рёбер и петель, то эту часть задания не выполнять. Описать изменённый (или исходный) граф парой V, E как это делалось в примерах 4 и 5. ■ Задание 13. Привести данный орграф, если он содержат кратные дуги и / или петли, к простому орграфу без петель. В качестве ответа нарисовать пару «исходный – изменённый орграф». Если исходный орграф не содержал кратных рёбер и петель, то эту часть задания не выполнять. Описать изменённый (или исходный) орграф парой V, А как это делалось в примере 6 ■ Задание 14. Граф, полученный в результате выполнения задания 12, представить в виде массива смежных вершин (см. примеры 27 – 29) ■ Задание 15. Орграф, полученный в результате выполнения задания 13, представить в виде массива смежных вершин (см. примеры 27 – 29) ■ Задание 16. Для графа, рассмотренного в задании 14, найти указанным в примере 30 алгоритмом компоненты связности ■ Задание 16. В данном неориентированном графе, найти эйлеров цикл, пользуясь алгоритмом Флёри. Решение должно быть представлено, как в примере 32. Это означает, что должны быть подробно показаны все шаги и должны быть отмечены все встречаемые перешейки, вплоть до ситуации, когда дальнейшие рёбра определяются совершенно однозначно ■ Варианты графов для задания 16 показаны на следующем рисунке.