Ирина Эланс

Автор который поможет с любыми образовательными и учебными заданиями

Понятие графа

Граф представляет собой непустое множество точек и множество отрезков, оба конца которых принадлежат заданному множеству точек. Обозначать граф будем буквой Г. При изображении графов на рисунках или схемах отрезки могут быть прямолинейными или криволинейными; длины отрезков и расположение точек произвольны. Все три фигуры на рисунке 1.9 изображают один и тот же граф.

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

Вершины, которые не принадлежат ни одному ребру, называются изолированными. Граф, изображенный на рисунке 1.12, имеет одну изолированную вершину, а в графе, изображенным на рисунке 1.13, все три вершины изолированные.

Обозначать вершины будем обычно заглавными буквами русского или латинского алфавитов (А, В, С, …, X, Y,…) и иногда числами. Ребра графа будем обозначать парами вершин, например (А, В) и т.п., или малыми буквами русского или латинского алфавитов (a, b, c, …, x, y, …).

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

Некоторые основные понятия теории графов

Граф называется полным, если каждые две различные вершины его соединения одним и только одним ребром (рис. 1.11).

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

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

Вершины в графе могут отличаться друг от друга тем, сколькими ребрам они принадлежат.

Степенью вершины называется число ребер графа, которым принадлежит эта вершина. Вершина называется нечетной, если ее степень – число нечетное. Вершина называется четной, если ее степень – число четное.

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

Теорема 1: В графе Г сумма степеней всех его вершин – число четное, равное удвоенному числу ребер графа.

Теорема 2: Число нечетных вершин любого графа четно.

Теорема 3: Во всяком графе с n вершинами, где n≥2, всегда найдется по меньшей мере две вершины с одинаковыми степенями.

Теорема 4: Если в графе с n вершинами (n>2) в точности две вершины имеют одинаковую степень, то в этом графе всегда найдется либо в точности одна вершина степени 0, либо в точности одна вершина степени n – 1.

Путь в графе. Цикл. Деревья.

Как пройти по ребрам на рисунке 1.23 из А1 в А5? Все три последовательности ребер, следуя которым можно попасть из А1 в А5:

(А1; А4); (А4; А5).
(А1; А2); (А2; А4); (А4; А5).
(А1; А4); (А4; А2); (А2; А1); (А1; А4); (А4; А5).

В одних - ребра повторяются, в других – не повторяются. Можно указать маршрут от А1 до А5 содержащий все вершины графа. Таков, например, маршрут: (А1; А2); (А2; А4); (А4; А3); (А3; А1); (А1; А4); (А4; А5). Но не всякую последовательность ребер, ведущую из А1 в А5 называют путем из А1 в А5.

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

Вершина А1 – начало пути, вершина Аn – конец.

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

Путь от А1 до Аn называется простым, если он не проходит ни через одну из вершин графа более одного раза.

Циклом называется путь, в котором совпадают его начальная и конечная вершины.

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

Длиной пути называется число ребер этого пути.

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

От вершины А1 до вершины А6 графа на рисунке 1.28 можно пройти четырьмя путями; один из них – длины 1, второй – длины 2 и два пути длиной 6.

Теорема: Если у графа все простые циклы четной длины, то граф не имеет ни одного цикла нечетной длины.

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

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

Две вершины А и В графа называются связными, если в графе существует путь с концами А и В.

Две вершины называются несвязными, если в графе не существует ни одного пути, связывающего их.

Граф называется связным, если каждые две вершины его связные.

Граф называется несвязным, если хотя бы две вершины его несвязные.

Теорема: Связный граф представляет собой простой цикл тогда и только тогда, когда каждая его вершина имеет степень 2.

Прямая теорема: Если Г – связный граф и степень каждой его вершины равна 2, тогда Г – простой цикл.

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

Обратная теорема: Если граф Г – простой цикл, тогда степень каждой его вершины равна двум.

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

Покажем, что в простом цикле не может быть вершины, степень которой не равна двум.

Если какая-то вершина в графе имеет степень меньше двух, то она не не принадлежит никакому простому циклу (рис. 1.33).

Если какая-то вершина имеет степень больше двух, то никакой простой цикл (по определению) не может содержать все ребра, которым принадлежит эта вершина (1.34).

Деревом называется всякий связный граф, не имеющий циклов (рис. 1.42).

Для каждой пары вершин дерева существует единственный соединяющий их путь.

Удобно считать, что граф, состоящий из одной изолированной вершины, тоже является деревом.

Вершина дерева, степень которой равна единице, называется висячей вершиной.

Представление о плоском графе

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

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

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

Ребро (А, В) на рисунке 2.9 является мостом, соединяющим циклы. Такие мосты будем называть перегородками.

Две грани будем называть соседними, если их границы имеют хотя бы одно общее ребро.

Формула Эйлера

Для всякого плоского представления связного плоского графа без перегородок число вершин (в), число ребер (р) и число граней с учетом бесконечности (г) связаны соотношением: в – р + г = 2.

Пусть граф Г – связный плоский граф без перегородок. Определим значение алгебраической суммы в-р+г для его произвольного плоского представления. Преобразуем данный граф в дерево, содержащее все его вершины. Для этого удалим некоторые ребра графа Г, разрывая поочередно все его простые циклы, причем так, чтобы граф оставался связным и без перегородок.

Заметим, что при таком удалении одного ребра число граней уменьшится на 1, так как при этом либо пропадает один простой цикл, либо два простых цикла преобразуется в один. Следовательно, значение разности р-г при этом остается неизменным. На рисунке 2.12 ребра, которые удаляем, выделяем штриховой линией.

В полученном дереве обозначим число вершин – вд, число ребер – р_д, число граней – г_д. Справедливо равенство: р-г=р_д-г_д. В дереве одна грань, т. е. р-г=р_д-1. Вспомним, что операция удаления ребе из графа не меняет число его вершин, т. е. в = в_д. При этом, в дереве в_д-р_д=1. Отсюда в – р_д=1, т. е. р_д=в-1, а потому в-р+г=2

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

Эйлеров цикл

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

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

Попробуйте обвести изображения графов на рисунке 2.25, не отрывая карандаша от бумаги и не проходя уже по обведенному ребру вторично.

Задание по обведению ребер удается выполнить для графов на рисунках 2.25(а, б, г, д). Графы на рисунках 2.25 (в, е) нарисовать без отрывания карандаша от бумаги или не проходя дважды по ребрам не удастся. Для удобства введем специальные понятия.

Эйлеровым путем в графе называется путь, содержащий все ребра графа.

Эйлеровым циклом в графе называется цикл, содержащий все ребра гафа.

Граф, обладающий эйлеровым циклом, называется эйлеровым графом.

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

Теорема: Если граф Г обладает эйлеровым циклом, то он связный и все его вершины четные.

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

Теорема: Если граф Г связный и все его вершины четные, то он обладает эйлеровым циклом.

Доказательство: Если начать путь из произвольной вершины графа Г, то найдется цикл, содержащий все ребра графа. Пусть А – произвольная вершина графа Г (рис. 2.26). Из А начнем путь l по одному из ребе и продолжим его, проходя каждый раз по новому ребру.

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

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

Так как В – четная, то число ребер, которым принадлежит В и которые не вошли в путь l, тоже четно. Начнем новый путь s из В и используем только ребра, не принадлежащие l. Этот пусть кончится в В (на рисунке путь s обозначен сплошными стрелками. Объединим теперь оба цикла: из А пройдем по пути l к вершине В, затем по циклу s и, вернувшись в В, пройдем по оставшейся части пути l обратно в А.

Если снова найдутся ребра, которые не вошли в путь, то найдем новые циклы. Число ребе и вершин конечно, процесс закончится.

Итак, приведен алгоритм, позволяющий отыскать эйлеров цикл, и показано, что он применим во всех случаях, допускаемых условиями теоремы.

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

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

Теорема: Если граф Г обладает эйлеровым путем с концами А и В (А не совпадает с В), то граф Г связный и А и В – единственные нечетные его вершины.

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

Верно и обратное.

Теорема: Если граф Г связный и А и В единственные и нечетные вершины его, то граф Г обладает эйлеровым путем с концами А и В.

Доказательство: Вершины А и В могут быть соединены ребром в графе (рис. 2.27), а могут быть и не соединены (рис. 2.28).

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

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

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

Теорема: Если связный граф имеет 2k нечетных вершин, то найдется семейство из k путей, которые в совокупности содержат все ребра графа в точности по одному разу.

Доказательство: Половину нечетных вершин обозначим А₁, А₂, …, А_k, другую – В₁, В₂, …, В_k (рис 2.29). Если вершины А_l и В_l (1 ≤ l ≤ k) соединены ребром, то удалим из графа Г ребро (А_l, В_l). Если вершины А_l и В_lне соединены ребром, то добавим к Г ребро (А_l,В_l). Все вершины нового графа будут четными, то есть в новой графе найдется эйлеров цикл. При восстановлении графа Г цикл разобьется на k отдельных путей, содержащих все ребра графа.

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

Теорема: Если граф Г связный, то можно построить цикличный маршрут, содержащий все ребра графа в точности два раза, по одному в каждом направлении.

Доказательство: Дадим точное правило построения такого пути, предложенное Тарри.

Из произвольной вершины А пройдем вдоль какого-нибудь ребра (А, В), отметив его стрелкой, указывающей направление пути (рис. 2.37). Из В пройдем к третьей вершине, снова отметив стрелкой направление прибытия и так далее. Ребро, по которому впервые прибываем в вершину, будем отмечать стрелкой. Выходя из вершины, выбирают дальнейший путь: либо ребро, еще не проходили ни разу, либо ребро, по которому прибыли в эту вершину. Договариваемся, что ребро, по которому впервые попали в вершину, будем использовать для выхода только тогда, когда оно остается единственным выходом из этой вершины.

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

На рисунке 2.37 дан связный граф Г, на котором по правилу Тарри построен искомый цикл; для удобства стрелки пронумерованы.

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

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

Гамильтонов цикл