Абстрактный граф и его геометрическая реализация

Предисловие

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

В пособии излагаются основополагающие факты теории графов. Рассматриваются классические задачи обхода и раскраски графов, входящие в образовательные стандарты по дискретной математике для студентов педвузов. Особенностью пособия является его практическая направленность: значительное место уделено вопросам задания информации о графах, возникающим при использовании ЭВМ. При этом оценивается степень оптимальности кодирования с точки зрения «сжатия» информации. Соответствующие знания могут быть востребованы студентами при изучении таких дисциплин федерального компонента, как «Теоретические основы информатики», «Программирование» и «Практикум решения задач на ЭВМ», а также некоторых курсов по выбору: «Методы кодирования информации», «Динамические структуры данных», «Введение в математическую кибернетику» и др.

Теория графов имеет многочисленные приложения в различных сферах человеческой деятельности. В пособии рассматривается задачи оптимального размещения информации, излагаемые на профессиональном уровне, позволяя студентам «заглянуть» на передний край науки «Информатика».

Все утверждения – теоремы, леммы и следствия, а также формулы и примеры имеют номера, состоящие из трех чисел. Первое означает номер главы, второе – номер раздела в этой главе, третье – номер утверждения или примера в разделе. Символ ð используется для обозначения конца доказательства. Утверждения набраны курсивом, а  определяемые слова – жирным курсивом. Жирным шифром набраны слова «теорема» и «доказательство». Для выделения заголовков примеров используются прописные буквы.

 

Введение

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

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

Начало теории графов как математической дисциплины было положено Леонардом Эйлером в работе, датированной 1736 годом, в которой была решена задача, называемая в литературе задачей о кёнигсбергских мостах.

Жителям Кёнигсберга хотелось пройти по всем мостам  города по одному разу и вернуться к себе домой. Однако все их попытки оказывались неудачными. Л.Эйлер не только показал, что желаемый обход существующих мостов невозможен, но и сформулировал необходимое и достаточное условие, когда такой обход возможен. При этом использовались, как бы мы теперь сказали, методы теории графов.

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

Большое число популярных головоломок поддаётся формулировке непосредственно в терминах теории графов. При желании много занимательных задач, решаемых с помощью графов можно найти в [1].Такая наглядность и кажущаяся понятность теоретико-графовых конструкций породила (и порой порождает сейчас) весьма поверхностное отношение к возможностям этой теории. Хотя серьезное отношение ко всей массе «увлекательных» задач уже в позапрошлом веке приводило к пониманию, что многие задачи такого рода содержат математическое ядро, важность которого выходит за рамки конкретных задач. Наиболее известная из таких задач – проблема четырёх красок, поставленная Де Морганом в середине 19 века: можно ли любую карту на поверхности земного шара раскрасить только четырьмя цветами (красками) таким образом, чтобы никакие две соседние страны не были раскрашены в один цвет? Эту задачу не удается решить более ста лет, хотя доказательства для случаев 6 и 5 красок были найдены достаточно быстро. В 1976 году было опубликовано сообщение, что американским ученым удалось доказать эту гипотезу, однако их доказательство, основанное на переборе значительного числа так называемых неустранимых конфигураций, очень трудоемко и его невозможно провести без использования ЭВМ. Изначально для этого потребовалось около 1200 часов машинного времени, которое позднее  удалось сократить до 300 часов. Сам текст доказательства занимает сотни страниц. Неоднократно в нем обнаруживались и исправлялись ошибки. Поэтому многие по-прежнему используют слово «гипотеза», когда говорят об этой задаче.

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

Возникновение теории графов как самостоятельной математической дисциплины принято относить к 1936 году, когда вышла в свет монография венгерского математика Д. Кёнига «Теория конечных и бесконечных графов». Там впервые был введён и сам термин «граф». Бурное развитие теории графов началось во второй половине 20 века в связи с практическими запросами математической логики, машинной математики, автоматики, теории информации, теории игр, исследования операций, математической лингвистики  - всего «букета наук», тесно связанных с кибернетикой. В них, в отличие от классического анализа непрерывных величин, на первый план выдвигаются рассуждения и построения дискретно-комбинаторного характера. Попытки подвести теорию графов под какой-либо из сложившихся разделов математики (алгебра, комбинаторная топология, математическая логика) оказались несостоятельными. Аппарат алгебры, правда, удаётся использовать в теории графов не только как вычислительное средство, но и как орудие исследования, однако в изучении графов слишком большую роль играет чисто комбинаторное искусство, недостаточно охваченное алгебраической наукой. После таких неудачных попыток было осознано, что теории графов нужен свой математический аппарат, прочно опирающийся на алгебру и насквозь пронизанный комбинаторикой.

 

 

Глава 1. Основные понятия теории графов

Подграфы и их свойства

Чередующаяся последовательность вершин и рёбер, начинающаяся и заканчивающаяся вершинами, в которой каждое ребро соединяет вершины, одна из которых непосредственно предшествует данному ребру, а другая непосредственно следует за ним, называется маршрутом.

Пример 1.2.1.Пусть граф G (V, E) имеет вид  

                                     

v 2

                                                                                                                                                                     

 

 

Маршрутом  в графе G будет, например, последовательность: v ₁ (v ₁, v ₃) v ₃ (v ₃, v ₁) v ₁ (v ₁, v ₂) v ₂. Длина маршрута – число содержащихся в нем рёбер. Цепь – маршрут, в котором нет повторяющихся ребер. Цепью будет, например, последовательность: v ₂ (v ₂, v ₃) v ₃ (v ₃, v ₄) v ₄ (v ₄, v ₁) v ₁ (v ₁, v ₃) v ₃. Простая цепь – цепь, в которой все вершины различны. В качестве примера простой цепи можно привести последовательность v ₂ (v ₂, v ₃) v ₃ (v ₃, v ₄) v ₄ (v ₄, v ₁) v ₁. Замкнутый маршрут – маршрут, в котором совпадают концевые вершины. Замкнутым будет, например, такой маршрут: v ₁ (v ₁, v ₃) v ₃ (v ₃, v ₂) v ₂ (v ₂, v ₃) v ₃ (v ₃, v ₄) v ₄ (v ₄, v ₁) v ₁. Цикл – цепь, концевые вершины которой совпадают. Простой цикл – простая цепь, концевые вершины которой совпадают. Простым циклом будет, например, последовательность v ₁ (v ₁, v ₃) v ₃ (v ₃, v ₄) v ₄ (v ₄, v ₁) v ₁.

При решении некоторых задач удобно бывает иметь дело с графами, ребра которых задаются упорядоченными парами вершин. Такие графы называются ориентированными (орграфами), а ребра, изображаемые линиями со стрелками, - дугами. Для ориентированных графов будем пользоваться обозначением D (V, X), где X = X (D) – множество дуг графа D.

Пример 1.2.2.Пусть орграф D (V, X) имеет вид:

                                                    

 

                                                                              

 

                                                      

В орграфе аналогично вводятся понятия: ориентированный маршрут, например: v ₁ (v ₁, v ₃) v ₃ (v ₃, v ₄) v ₄ (v ₄, v ₁) v ₁ (v ₁, v ₃) v ₃;   путь - ориентированная цепь, например: v ₁ (v ₁, v ₃) v ₃ (v ₃, v ₄) v ₄ (v ₄, v ₁) v ₁ (v ₁, v ₂) v ₂; простой путь – ориентированная простая цепь, например: v ₁ (v ₁, v ₃) v ₃ (v ₃, v ₄) v ₄.

Из замкнутых ориентированных маршрутов обычно выделяют контур – ориентированный простой цикл, например: v ₁ (v ₁, v ₃) v ₃ (v ₃, v ₄) v ₄ (v ₄, v ₁) v ₁.

Понятие степени вершины для ориентированных графов расчленяется на две составляющих: полустепень исхода – число дуг, начинающихся в данной вершине, и полустепень захода – число дуг, оканчивающихся в данной вершине.

Граф G (V, E) называется связным, если для любой пары его вершин в графе существует хотя бы одна цепь, соединяющая их. В противном случае граф называется несвязным и его можно разбить на компоненты связности. Так, например, граф из примера 1.1.2 содержит 3 компоненты связности. Для орграфов D (V, X) вводится три типа связности. Орграф D (V, X) сильно связен, если для любой пары вершин существует путь, ведущий из первой вершины во вторую, и из второй в первую; односторонне связан, если для любой пары его вершин по крайней мере одна из них достижима из другой; слабо связан, когда связано основание орграфа D – неориентированный граф G, соответствующий D. В противном случае ориентированный граф называется несвязным.

Ребро графа называется мостом (перешейком), если его удаление приводит к увеличению числа компонент связности графа. Рассмотрим класс связных графов, в которых свойство связности экстремально: каждое ребро графа является мостом. Связный граф, в котором каждое ребро является мостом, называется деревом. Другими эквивалентными определениями являются:

· дерево – связный граф, не содержащий циклов (ациклический);

· дерево – связный граф, в котором любая пара вершин соединяется единственной простой цепью;

· дерево – связный граф, в котором число рёбер на единицу меньше числа вершин.

Остовноедерево графа – дерево, содержащее все его вершины.

Пример 1.2.3. Все неизоморфные остовные деревья графа из примера 1.2.1.:

                                                                

                                                                      

                                                

                                                                                              

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

Хроматическое число графа

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

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

Если задача не содержит никаких дополнительных ограничений, то она имеет тривиальное решение: достаточно раскрасить каждую вершину в свой уникальный цвет. Поэтому обычно накладываются ограничения на число используемых цветов.

Граф G называется k -раскрашиваемым, если для построения допустимой раскраски вершин графа G достаточно использования k цветов. Если граф G является k -раскрашиваемым, но не является (k -1)- раскрашиваемым, то он называется k -хроматическим, а само число k называется хроматическим числом. Для хроматического числа графа G будем использовать обозначение c (G). Рассмотрим классы графов, обладающих заданным хроматического числа.

Нетрудно видеть, что класс 1-хроматических графов (с c (G)=1) – класс пустых графов (не содержащих рёбер).

Описание класса 2-хроматических графов дает следующая теорема.

Теорема 2.1.1. Граф G является 2-хроматическим тогда и только тогда, когда он не содержит циклов нечётной длины.

Доказательство. Выделим в графе G основное дерево. Очевидно, что его можно раскрасить допустимым образом в два цвета (например, красить по слоям). При этом вершины дерева, соединяемые цепью чётной длины, будут иметь одинаковые цвета, а вершины, соединяемые цепью нечётной длины, - разные цвета.

Необходимость. Пусть граф G допускает правильную раскраску в два цвета, тогда и любое его остовное дерево будет окрашено в два цвета. Если бы в графе G были циклы нечетной длины, то концевые вершины каждого добавляемого ребра, порождающего цикл нечётной длины, были бы окрашены в один цвет, так как они соединяются в дереве цепью чётной длины, Приходим к противоречию, поскольку нам дано, что граф G допускает правильную раскраску в два цвета.

Достаточность. Если граф G не содержит циклов нечётной длины, то допустимая раскраска любого его островного дерева будет допустимой  раскраской и всего графа G, так как добавляемые к остову рёбра, порождающие циклы четной длины, будут соединять вершины, удаленные в остовном дереве на нечётное расстояние и, следовательно, окрашенные в различные цвета.        ð

В качестве примера 2-хроматичских графов можно привести класс двудольных графов , очевидно, не содержащих циклов нечетной длины.

Для класса 3-хроматичских графов до сих пор не получено описания на уровне необходимого и достаточного условия.

О хроматическом числе произвольного графа G мало, что можно сказать. Ясно, что, с одной стороны, оно не превосходит n - числа вершин графа G, а с другой, не меньше r -числа вершин в максимальном полном подграфе графа G, таким образом, r £ c (G) £ n.

Для получения более содержательных оценок хроматического числа необходимо располагать дополнительной информацией о графе. В качестве примера рассмотрим следующее утверждение.

Теорема 2.1.2. Если наибольшая из степеней вершин графа G равна r, то граф (ρ+1) -раскрашиваемый.

Доказательство проводится индукцией по N - числу вершин графа G.

1. Для N =1 утверждение очевидно, так как ρ=0 и ρ+1=1.

2. Предположим, что утверждение верно и для графов с числом вершин N =2,3, …, n.

3. Рассмотрим произвольный граф G с числом вершин N = n +1, степень каждой из которых не превосходит ρ. Удалим некоторую вершину графа вместе с инцидентными ей рёбрами. В полученном графе будет n вершин, степень каждой из которых не превосходит ρ. По предположению индукции его можно раскрасить (ρ+1) цветом. Вершины, которые были смежны с удаленной вершиной, будут окрашены не более чем в ρ цветов, даже если все они будут разноцветными. При этом ранее удаленную вершину можно раскрасить (ρ+1) -м цветом, получив допустимую раскраску всего графа.                                  ð

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

2.2. Свойства планарных графов

Граф любой карты на поверхности земного шара является планарным, учитывая возможность её стереографической проекции на плоскость. Планарный граф, реализованный на плоскости, называется плоским. Для плоского графа вводится понятие грани  – части плоскости, ограниченной со всех сторон рёбрами и вершинами графа.Обозначим через f   число граней плоского графа. Л.Эйлером была установлена связь между числом вершин, ребер и граней в плоских графах.

Теорема 2.2.1. Для числа вершин, ребер и граней связного плоского графа G справедливо равенство 

                           n + f = m + 2                            (2.2.1)

Доказательство проводится индукцией по M -числу рёбер графа G.

1.Для М=1 возможны 2 случая:

а) одна вершина с петлей: n =1, m =1, f =2;

б) две смежные вершины: n =2, m =1, f =1.

В обоих случаях значения левой и правой частей выражения (2.2.1) совпадают и равны 3.

2. Предположим, что равенство (2.2.1) верно и для любого связного плоского графа с числом ребер M =2,3, …, m.

3. Покажем, что равенство (2.2.1) справедливо для любого связного плоского графа с числом ребер M = m +1. Рассмотрим все возможные способы построения связного плоского графа с числом ребер M = m +1 на основе связного плоского графа с числом ребер M = m. Добавляемое (m +1) -оеребро может быть:

а) петлёй. В этом случае увеличится на 1 число граней f (новая грань расположена внутри петли) и равенство (2.2.1) сохранится.

б) ребром, соединяющим две вершины, принадлежащие границе одной грани. Добавляемое ребро разобьет эту грань на две, т.е. число граней f  увеличится на 1 и равенство (2.2.1) сохранится.

в) ребром, соединяющим некоторую вершину исходного графа с новой вершиной. В этом случае увеличится на 1 число вершин n, число граней f останется неизменным и равенство (2.2.1) сохранится.

Других способов увеличения числа ребер в плоских графах не существует.  ð 

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

Следствие 2.2.1. Если G – простой связный планарный граф с n ≥ 3 вершинами и m рёбрами, то

m ≤ 3 n – 6                                                      (2.2.2)

Доказательство. Рассмотрим плоскую укладку графа G. Введем вспомогательную величину Q (G), равную общему числу рёбер вокруг всех граней графа G. Оценим величину Q (G) сверху и снизу. Так как каждая грань простого плоского графа ограничена не менее чем тремя рёбрами, то Q (G) ³ 3 f.  С другой стороны, каждое ребро может входить в границу не более двух граней, учитываясь в Q (G) не более 2 раз. Следовательно, Q (G)≤2 m. Сопоставляя оба неравенства, получаем соотношение 3 f ≤2 m. После его подстановкив формулу (2.2.1) получаем соотношение (2.2.2).                                                    ð

Если выполняется равенство m =3 n – 6, то такой планарный граф называется максимальным.  Границы всех граней максимального плоского графа содержат по три ребра. Используя свойства максимальных плоских графов, можно доказать, что любой планарный граф допускает плоскую укладку, в которой каждое ребро является отрезком прямой (попробуйте это доказать).

Теорема 2.2.2. В любом простом планарном графе G существует вершина, степень которой не превосходит 5.

Доказательство. Без потери общности можно считать граф плоским, связным и содержащим не менее трёх вершин. Предположим, что степени всех вершин графа больше или равны 6. Нетрудно видеть, что сумма степеней всех вершин графа равна 2 m, поскольку в указанной сумме каждое из m рёбер учитывается дважды. Из предположения следует, что 2 m ³ 6 n, то есть m ³ 3 n. Подставляя это соотношение в (2.2.2), приходим к противоречию 3 n ≤ 3 n -6.    ð

2.3. Раскраска планарных графов

Теорема 2.3.1. Любой планарный граф G с n ≥ 6 вершинами 6-раскра-шиваемый.

Доказательство проводится индукцией по N - числу вершин графа G.

1. Для N =6 утверждение очевидно.

2. Предположим, что утверждение верно и для любого планарного графа с числом вершин N =7,8, …, n.

3. Пусть G – произвольный планарный граф с n +1 вершиной. Не теряя общности, можно считать G простым графом (добавление кратных рёбер не влияет на раскраску). По теореме 2.2.2 граф G  содержит вершину v, степень которой не превосходит 5. Если удалить её вместе с инцидентными рёбрами, то оставшийся граф будет 6-раскрашиваемым по предположению индукции. Требуемая раскраска в 6 цветов для всего графа G получается, если окрасить вершину v цветом, отличным от цветов не более пяти смежных с ней вершин.    ð

Этот результат можно усилить и доказать с помощью более тщательных рассуждений возможность раскраски любого планарного графа в 5 цветов.

Теорема 2.3.2. Любой планарный граф G с n ≥ 5 вершинами 5-раскра-шиваемый.

Доказательство проводится индукцией по N - числу вершин графа G.

1. Для N =5 утверждение очевидно.

2. Предположим, что утверждение верно и для любого планарного графа с числом вершин N =6,7, …, n.

3. Пусть G – произвольный планарный граф с n +1 вершиной. Не теряя общности, можно считать G простым графом (добавление кратных рёбер не влияет на раскраску). По теореме 2.2.2 граф G  содержит вершину v ₀, степень которой не превосходит 5. Если удалить её вместе с инцидентными рёбрами, то оставшийся граф будет 5-раскрашиваемым по предположению индукции.

Если степень вершины v ₀ меньше 5 или если среди вершин, смежных с вершиной v ₀, найдутся, по крайней мере, две с одинаковыми цветами, то для вершины v ₀   среди 5 цветовнайдется свободный цвет без перекраски других вершин.

Осталось рассмотреть случай, когда все вершины ,смежные с вершиной v ₀ имеют разные цвета. Для упрощения обозначений, будем считать, что каждая вершина  окрашена в i - цвет. Пусть в плоской укладке графа G вершины  расположены вокруг вершины v ₀  в порядке её кругового обхода. Выделим в G подграф G _1,3, порожденный вершинами 1-го и 3-го цветов. Вершины v ₁ и v ₃ могут принадлежать, как одной компоненте связности подграфа G _1,3, так и разным компонентам.

Если вершины v ₁ и v ₃ принадлежат разным компонентам связности подграфа G _1,3, то в одной из этих компонент перекрасим вершины 1-го цвета на 3-ий цвет, а вершины 3-го цвета на 1-ый цвет. После этого обе вершины v ₁ и v ₃ станут 1-го цвета или 3-го цвета и для вершины v ₀ найдется свободный цвет среди 5 используемых цветов. Заметим, что указанная перекраска сохранит раскраску всего графа допустимо. Действительно, взаимный обмен 1-го и 3-го цветов не может привести к появлению ребер с одноцветными концевыми вершинами, как для ребер с концевыми вершинами 1-го и 3-го цветов, так и для ребер, одна из концевых вершин которых имеет цвет, отличный от 1-го и 3-го.  

Если вершины v ₁ и v ₃ принадлежат одной компоненте связности подграфа G _1,3, то в плоской укладке графа G можновыделить цикл, содержащий ребра (v ₀, v ₁),…,(v ₃, v ₀), вершины которого (кроме вершины v ₀) окрашены чередующимся способом в 1-й или 3-й цвет. Внутри этого цикла находится вершина v ₂, а вершина v ₄ снаружи. Вершины v ₂ и v ₄ должны принадлежать разным компонентам связности  подграфа G _2,4, поскольку в противном случае в плоской укладке графа G можнобыло бы выделить цикл, содержащий ребра (v ₀, v ₂),…,(v ₄, v ₀), вершины которого (кроме вершины v ₀) окрашены чередующимся способом во 2-й или 4-й цвет. Цвет общей вершины указанных двух циклов v ₀ должен быть равен 1 или 3 (в подграфе G _1,3), но, с другой стороны, он должен быть равен 2 или 4 (в подграфе G _2,4) Пришли к противоречию. Таким образом, к вершинам v ₂ и v ₄ можно будет применить перекраску, рассмотренную в предыдущем абзаце.                                                                                    ð

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

Глава 3. Способы задания графов

3.1. Алгоритмические вопросы

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

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

Алгоритм построения эйлерова цикла

1. Выбрать в графе произвольную вершину а.

2. Выбрать некоторое ребро u, инцидентное вершине а.

3.  Выбранное ребро занести в список ребер эйлерова цикла, перейти по нему к другой вершине, а ребро удалить из графа.

4. Находясь в некоторой вершине x, не выбирать среди инцидентных ребер те, которые соединяют вершину x с начальной вершиной а, если есть другие возможности.

5. Находясь в некоторой вершине x, не выбирать среди инцидентных ребер то, которое является мостом в оставшемся подграфе.

Обоснование алгоритма

1.Покажем, что предписания алгоритма всегда выполнимы.

Предположим, что в ходе реализации алгоритма достигнута некоторая вершина b. Если b ¹ a, то текущий оставшийся подграф связен (ребра-мосты не выбирались) и степени всех его вершин четны, кроме вершин a и b. По следствию 1.3.2. этот подграф содержит эйлерову цепь, соединяющую вершины b и a. Если b = a, то текущий оставшийся подграф будет эйлеровым пока не все ребра, инцидентные вершине a удалены.

2. Покажем, что предписания алгоритма приводят к построению полного эйлерова цикла, т.е., что не останется непройденных ребер.

Учитывая предыдущее, после окончания работы алгоритма все ребра, инцидентные начальной вершине a, должны быть пройдены. Если непройденное ребро имеет общую вершину с ребром, инцидентным вершине a, то это означает, что на некотором этапе выполнения алгоритма было нарушено предписание п.4. Если непройденное ребро не имеет общей вершины с ребром, инцидентным вершине a, то это означает, что на некотором этапе выполнения алгоритма было нарушено предписание п.5.                                                                  ð

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

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

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

Матричные формы

Ограничимся рассмотрением матриц смежности и инцидентности, наиболее часто используемых при задании графов.

Матрицы смежности

Для простого неориентированного графа G (V, E), ê V ê = n матрица смежности A =|| ||,  является бинарной, симметрической с элементами =1 тогда и только тогда, когда вершины с номерам i и j  смежны.

Пример 3.2.1.Матрица смежности графа, изображенного ниже, имеет следующий вид:

 

 

         V ₃                                     1    2   3   4   5

                               1   0    1    0    0    1

V ₂        V ₄                   2  1    0    1    1    0

                                            3  0   1   0  1    0

                                   4  0    1    1    0    1

V ₁                      V ₅                    5   1   0    0   1  0

Из свойств матрицы смежности следует, что для восстановления обыкновенного графа G достаточно задать информацию об элементах, расположенных над (под) главной диагональю. Каждый двоичный элемент требует 1 бит памяти. Всего потребуется n (n -1)/2 бит памяти.

Если граф G содержит петли и кратные ребра, то элементами матрицы смежности A могут быть целые неотрицательные числа, равные числу ребер, соединяющих i и j  вершины. Элементы a_ii главной диагонали равны числу петель на i -ой вершине.

         V ₃                            1    2   3    4    5

                                          1   0    1    0    0    1

V ₂        V ₄            2  1    0   1    2    0

                                            3   0    1    0    1    0

                             4  0    2   1   1    1

V ₁                      V ₅                    5  1    0    0    1    0

Для восстановления графа G,содержащего петли и кратные ребра необходимо добавить к элементам, расположенных над (под) главной диагональю, n элементов главной диагонали. Каждый из n (n +1)/2 элементов может содержать число, не превосходящее m, потребует é log ₂ m ù бит памяти. Всего необходимо n (n +1) é log ₂ m ù /2 бит памяти.

Для ориентированных графов D (V, X) элемент матрицы смежности A равен числу дуг, исходящих из вершины i в вершину j, и матрица A в общем случае не является симметрической.

                V ₃                     1   2  3    4

                                                     1 0    1    0    1

           V ₂                                    V ₄              2 0   0    1   0

                                                                                              3 2    0    0    1

                              V ₁                                     4 0   0    0    0

Отсутствие симметрии в матрице смежности ориентированного графа D (V, X) приводит к необходимости задания элементов как над, так и под главной диагональю, а при наличии дуг-петель - всех элементов матрицы смежности. Если граф D (V, X) простой, то потребуется n (n -1) бит памяти, в противном случае n ² é log ₂ m ù бит.

Матрицы инцидентности

Для простого неориентированного графа G (V, E), ê V ê = n матрица инцидентности B =|| ||, ,  является бинарной с элементами =1 тогда и только тогда когда i -ойвершине инцидентно j -ое ребро.

Пример 3.2.2.Матрица инцидентности графа, изображенного ниже, имеет следующий вид

       V ₃                           1    2   3    4 5 6

  4   5                  1   1 1   0   0 0  0

V ₂     6 V ₄          2  0 1 0 1   0   1

2           3        3  0 0 0 1 1 0

                                 4   0 0 1 0 1 1

V ₁      1 V ₅                      5  1 0 1 0 0 0