Основные понятия и определения графа и его элементов

Лекция 7. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ. ОСНОВНЫЕ ПОНЯТИЯ

Вопросы для контроля знаний и подведения итога прочитанной лекции

1. Что такое генеральная совокупность и выборка?

2. Дайте статистическое распределение выборки.

3. Как строятся полигон и гистограмма?

4. Какие методы расчета есть для генеральной и выборочной средних?

5. Как оценивают генеральную и выборочную дисперсии?

6. Какие оценки параметра называются состоятельными, несмещенными и эффективными?

Цель: Изучить основные понятия теории графов

План:

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

2. Деревья. Лес. Бинарные деревья

3. Способы задания графа. Изоморфные графы

4. Сети. Сетевые модели представления информации

5. Применение графов и сетей

6. Вопросы для контроля знаний и подведения итога прочитанной лекции

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

Так о великих вещах помогают составить понятье

Малые вещи, пути намечая для их постижения.

Лукреций

Впервые понятие «граф» ввел в 1936 г. венгерский математик Денни Кёниг. Но первая работа по теории графов принадлежала;«перу великого Леонарда Эйлера и была написана еще в 1736 г. с помощью графов изображаются схемы различных дорог, линии воздушных сообщений, газопроводов, теплотрасс, электросетей, а также микросхемы, дискретные многошаговые процессы, системы различных бинарных отношений, химические структурные формулы и другие диаграммы и схемы. Применяются графы для решения задач химии, экономики, электротехники и автоматики. 'Также они широко используются в информатике и строительстве. Без графов сложно анализировать классификации в различных науках.

Графом G = (V, X) называется пара двух конечных множеств: множество точек и множество линий X, соединяющих некоторые пары точек. В терминах декартова произведения (подразд. 1.5) подмножество множества V´V: XÌV´V.

Рис. 2.1. Примеры графов: а — со смежными вершинами; 6 — полный; в – со смежными ребрами; г — с петлей

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

Пусть дан граф G = (V, X), где v = [V, W,...} — конечное непустое множество его вершин, а Х(V, W) — его ребра. Если ребро графа G соединяет две его вершины V и W (т.е. < V, W > ÎX), то говорят, что это ребро им инцидентно. Две вершины графа называются смежными, если существует инцидентное им ребро: на рис. 2.1, а смежными являются вершины А и В, А и С. Если граф G имеет ребро Х(V, W), у которого начало и конец совпадают, то это ребро называется петлей. На рис. 2.1, г петля — q(С, С). Два ребра называются смежными, если они имеют общую вершину. На рис. 2.1, в смежными являются, например, ребра х₁ и х₂ с общей вершиной С.

Граф G(V, X) может иметь ребра с одинаковыми парами вида Х(V, W). Такие ребра называются кратными, или параллельными. На рис. 2.1, а кратными являются, например, ребра х₁(А, В), х₂(А, В). Вершинам А и В инцидентны ребра х₁ х₂, х₃. Количество одинаковых пар вида Х(V, W) называется кратностью ребра (V, W). На рис. 2.1, а ребро АС имеет кратность, равную 3, а ребро АВ — кратность, равную 2. Число ребер, инцидентных вершине А, называется степенью этой вершины и обозначается deg(A) (от англ. degree — степень). Если вершине инцидентна петля, она дает вклад встепень, равный двум, так как оба конца приходят в эту вершину.

На рис. 2.1, в вершина А имеет степень, равную 1, вершина С — 4, вершина D — 2. Записывается это в виде: deg (А) = 1, deg (С) = 4, deg (D) = 2. Граф G ₄ (рис. 2.1, г) содержит пять вершин V= {А, В, С,, Е} и шесть ребер Х={p,q,r,s,t,u}.

Вершина графа, имеющая степень, равную нулю, называется изолированной. Граф, состоящий из изолированных вершин, называется нуль-графом. Для нуль-графа Х= Æ. Вершина графа, имеющая степень, равную 1, называется висячей. На рис. 2.1, г вершина Е — изолированная: deg (Е) = 0, а вершины А, В, Е, G,H на рис. 2.1, в — висячие.

Теорема 2.1. В графе G(V,Х) сумма степеней всех его вершин — число четное, равное удвоенному числу ребер графа: ,

где п = ïVï — число вершин; т = ïХï — число ребер графа.

Вершина называется четной (нечетной) если ее степень четное (нечетное) число.

На рис. 2.1, в deg (D) = 2, deg (F) = 3, значит, у графа G₃ вершина D является четной, а F — нечетной. В теории графов доказана следующая теорема.

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

Следствие. Невозможно начертить граф с нечетным числом нечетных вершин.

Граф G называется полным, если любые две его различные вершины соединены одним и только одним ребром. Полным является граф G₂ на рис. 2.1, б. Таким образом, полный граф определяется только своими вершинами. Пусть число вершин полного графа п. Тогда степень любой вершины, очевидно, равна deg (V) = п - 1, а число ребер равно числу сочетаний из п по 2, т. е. т = . Число ребер также можно найти по теореме 2.1: m = .

Дополнением графа G(V,Х)) называется граф (V, ) с теми же вершинами V, что и граф G, и имеющий те и только те ребра , которые необходимо добавить к графу G, чтобы он стал полным. Очевидно, что граф с кратными ребрами не имеет дополнения. Например, дополнением графа G ₅ до графа G ₂ на рис. 2.1, б является граф (рис. 2.2).

Как отмечалось в подразд. 1.3, дополнением универсального множества является пустое, и наоборот. Поскольку граф и его дополнение отличаются только ребрами (множества Х, )и дополнение графов сводится к дополнению множества X, то частным случаем этого свойства будет следующее правило: дополнением полного графа будет нуль-граф, и наоборот.

Рис. 2.2. Дополнение G 5 графа G5 до графа G2, изображенного на рис. 2.1, б	Рис. 2.3. Ориентированный граф

Если все пары (V _i, V_j) во множестве X являются упорядоченными, т.е. кортежами длины 2, то граф называется ориентированным, орграфом, или направленным. Поскольку сразу может быть не известно, о каком графе идет речь, в этой главе мы будем употреблять круглые скобки для обозначения ребра вместо угловых, как это должно было быть для кортежей. В них будет помещаться соответствующая пара вершин. В таком случае ребра принято изображать стрелками (рис. 2.3). Началом ребра называется вершина, указанная в кортеже первой, концом — вторая вершина этой пары (графически она указана стрелкой). Ребра ориентированного графа имеют определенные фиксированные начало и конец и называются дугами. Очевидно, дуги (V ₁, V₃) и (V ₃, V₁), если они обе существуют, различны: (V ₁, V₃) ¹ (V ₃, V₁).

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

Степень входа вершины V будем обозначать deg ₊(V), а степень выхода - deg _(V)- На рис. 2.3 deg ₊(V₁) = 1, deg ₊(V₂) = 1, deg ₊(V₃) = = 2, deg _-(V₁) = 1, deg _-(V₂) = 2, deg _-(V₃) = 1.

Дуги орграфа называются кратными, если они имеют одинаковые начальные и конечные вершины, т.е. одинаковые направления. Например, кратны дуги u(V ₂, V₃) и t(V ₂, V₃) на рис. 2.3.

Последовательность попарно инцидентных вершин V _i1, V_i2,..., V _ik неориентированного графа, т.е. последовательность ребер неориентированного графа, в которой вторая вершина предыдущего ребра совпадает с первой вершиной следующего, называется маршрутом. Число ребер маршрута называется длиной маршрута. Например, на рис. 2.1, в НСDFD — маршрут длиной 4. Обозначение: \ НСDFD \ = 4. Очевидно, что если V _i1, V_i2,..., V _ikс — маршрут длины k - 1, то и V _ik, V _ik-1, … _, V_i2, V _i1также будет являться маршрутом длины k - 1. Маршрут принято задавать как последовательность ребер, поскольку это более удобно при наличии кратных ребер. Если начальная вершина маршрута совпадает с конечной, то такой маршрут называется замкнутым или циклом. В графе G ₄ (рис. 2.1, г) (t,s,p,r), (u,s,p,) — циклы длиной 4, (r,t, q s,u) — цикл длиной 5, (t,s,u,r,t,s,p,r) — 8-цикл, (р,и) — 2-цикл, петля (q) — 1-цикл.

Расстоянием между двумя вершинами называется минимальная длина из всех возможных маршрутов между этими вершинами при условии, что существует хотя бы один такой маршрут. Обозначается как d(V₁,V₂) (от лат. distantio — расстояние) d(V₁,V₂) = min| V₁,…,V₂ |.

Поскольку рассматриваются конечные графы, минимум можно найти всегда. Очевидно, что d(V₁,V₂) = d(V₂,V₁). Формально можно ввести расстояние d(V ^’,V ^’). = 0 между любой вершиной и ей же самой, что соответствует нулевому маршруту, у которого начало и конец в одной вершине.

В маршруте одно и то же ребро может встретиться несколько раз. Если ребро встретилось только один раз, то маршрут называется цепью. Например, в графе G ₄ (рис. 2.1, г) (t,s, р) — 3-цепь. Если (x _1, x₂,... x _k-1,, x _k) — k -цикл, то любая циклическая перестановка, например (_, x₂,... x_k-1,, x _k, x ₁), также будет k:-циклом, поскольку сведется лишь к выбору начальной вершины. Частным случаем этого утверждения будет следующее: если k -цикл (x _1, x₂,... x _k-1,, x _k) является цепью, то для любой циклической подстановки sÎ S_k последовательность (x _{s(1) ,,} x _s(2) ,..., x _s(k)) также будет k -циклом и цепью.

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

• направление каждой дуги должно совпадать с направлением пути;

• ни одно ребро пути не должно встречаться дважды.

Другими словами, путь — упорядоченная последовательность ребер ориентированного графа, в которой конец предыдущего ребра совпадает с началом следующего и все ребра единственны. На рис. 2.3 (u,r,s,t) — 4-путь, (r, и) — 2-путь, (s, r, t, s) путем не является. Тогда цикл в орграфе — путь, у которого совпадают начало и конец. На рис. 2.3 (r,s,t) и (и, s,r) — 3-циклы. Для циклов орграфа также справедлива теорема о циклических подстановках. Цепь, путь и цикл в графе называются простыми, если они проходят через любую из вершин не более одного раза. Неориентированный граф называется связным, если между любыми двумя его вершинами есть маршрут. Для связного графа ориентация дуг не обязательна. Так, граф G₂ (рис. 2.1, б) является связным, а граф G₄ (рис. 2.1, г) — несвязным. Также можно ввести понятие связности для вершин графа: две вершины называются связными, если существует маршрут между ними. Понятно, что связность между вершинами является бинарным отношением. Это отношение будет отношением эквивалентности. Действительно, отноше­ние связности обладает известными свойствами (см. подразд. 1.6), т. е. оно:

рефлективно — каждая вершина (включая изолированные) связна сама с собой;

симметрично — любой маршрут (V,..., V") можно представить в обратном порядке: (V"',..., V ');

транзитивно — если вершина V соединена с вершиной V ' маршрутом М₁(Х ₁ ..., Х _р ), а вершина V ' соединена с вершиной V '' маршрутом М₂(Х _{р +1},..., Х_п), то вершина V соединена с вершиной V" маршрутом М₃(Х₁..., Х_р, Х_р+1,..., Х_n), в котором сначала идут все ребра маршрута М₁, а затем все ребра маршрута М₂.

Граф G можно разбить на непересекающиеся подмножества Х_i по признаку связности. Вершины одного множества являются связными между собой, а вершины различных множеств — несвязны. Тогда все подграфы V_i (классы эквивалентности) графа G называют связными компонентами, или компонентами связности. Связный граф имеет одну компоненту связности.

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

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

Ребро (V, W) связного графа G называется мостом, если после его удаления G станет несвязным и распадется на два связных графа G ' и G ". На рис. 2.4 мост (СЕ) разделил связный граф G ₇ на два различных связных графа: G ' с вершинами (А,В, С,D) и G " с вершинами (Е, F, G,Н,I). Также мостом является ребро ЕС.

Рис. 2.4. Граф G ₇ с мостами BC и CE

Теорема 2.4. Ребро графа является мостом тогда и только тогда, когда не принадлежит ни одному циклу.

Какие графы можно считать различными, а какие не различаются?

Графы G' и G" называются изоморфными, если существует взаимно-однозначное соответствие между их ребрами и вершинами, причем соответствующие ребра соединяют соответствующие вершины. Поскольку в данном издании исследуются конечные множества, такая биекция должна быть подстановкой. Между названием вершины и ее номером различия нет. Смежность двух вершин есть бинарное отношение, поэтому изоморфизм графов можно рассматривать как изоморфизм множеств их вершин (см. подразд. 1.4 и 1.6), на котором введено отношение смежности. Итак, графы G ₁ (V ₁, Х₂) и G₂(V ₂, Х₂) называются изоморфными, если | V ₁| = | V ₂| = п и существует подстановка sÎ S _n, такая, что V₂ = s (V ₁ ), а Х₂ = { s (V_i); s (V _j)) ï (V_i, V _j)Î Х ₁ }. Иными словами, можно так переобозначить; вершины первого графа, что в новых обозначениях вершины и ребра будут совпадать со вторым графом, причем кратным ребрам первого G '₈ должны соответствовать кратные ребра второго G ''₈ такой же кратности (рис. 2.5).

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

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

Граф G называется планарным (плоским), если существует изоморфный ему граф G', в изображении которого на плоскости ребра пересекаются только в вершинах. Иными словами, у планарного графа никакие два ребра не имеют общих точек, кроме общих вершин. На рис. 2.1 графы G₁ и G ₃ являются планарными, а G ₂ — нет. Областью назовем подмножество плоскости, пересекающееся с планарным графом только по некоторому проcтому циклу графа, являющемуся границей области. Поскольку рассматриваются конечные графы, то плоский граф всегда является ограниченным подмножеством плоскости. Пусть М — планарный граф с внутренними областями. Тогда дополнение М, т. е. М' = К²\М также может являться областью. Например, граф О₉ (рис. 2.6, а) выделяет в плоскости следующие области: А\ с границей д; А% с границей (о, 5, I)', А₃с границей (д, 5, и, г, {); А^с границей (р, и); А₅ с границей (о, р, г). Множество А_ъ на рис. 2.6, б областью не является, так как пересечение Л₃П С₁₀ содержит точку (2, не принадлежащую никакому циклу.

Рис. 2.5. Изоморфные графы	Рис. 2.6. Графы: а — G 9 (с областями А1— A 5); б — G 10 (с областями А1,A 2 ,, А4, A 5)

Теорема 2.5 (Эйлера). Связный плоский граф с п вершинами и т ребрами разбивает плоскость на r областей (включая внешнюю), причем

п - т + r= 2.

Задача 17 «О трех колодцах». Проложить дорожки от трех до­мов к каждому из трех колодцев так, чтобы никакие две дорожки не пересекались (рис. 2.7).

Граф называется двудольным, если его вершины разбиты на два непересекающихся подмножества: V= V ₁È V ₂, а ребра связывают вершины только из разных классов (не обязательно все пары). Если каждая вершина множества V ₁связана ребром с каждой вершиной множества V ₂, то двудольный граф называется полным двудольным и обозначается К_т,n, где т = | V ₁|, n = | V ₂|.

Рис. 2.7. Иллюстрация к задаче «О трех колодцах»	Рис. 2.8. Планарные графы: а — первоначальный; б — изображенный иначе

Примером двудольного полного графа К_3,3, является граф к задаче 17, которую также называют «Три дома — три колодца», показывая этим два непересекающихся множества вершин графа.

На (рис. 2.8, а) граф G является планарным, так как его можно изобразить иначе (G' на рис. 2.8, б). При таком изображении плоскость разбивается на области S₁, S₂, S₃, S₄, которые могут быть раскрашены в разные цвета. Видно, что п = 4, т = 6, r = 4, и справедлива формула Эйлера п-т + r=4-6 + 4 = 2.

Рис. 2.9. Изображение эйлерова графа	Рис. 2.10. Изображение гамильтоновых путей

Эйлеровым путем (циклом) графа G называется путь (цикл), который содержит все ребра графа только один раз. Граф, обладающий эйлероовым циклом, называется эйлеровым. Плоские эйлеровы графы можно изобразить «одним росчерком пера», причем процесс изобжения начинается и заканчивается в одной вершине. Такой граф называют также уникурсальным.

Теорема 2.6. Граф G является эйлеровым тогда и только тогда, когда G — связный граф, имеющий все четные вершины.

На рис. 2.9 изображен пример эйлерова графа. Граф G₉ на рис. 2.6, а не будет эйлеровым, так как не все его вершины являютс я четными.

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

Например, в графе G путь (V ₃, V ₄, V ₁, V ₂, V ₅) является гамильтоновым, а путь (V ₂, V ₃, V ₄, V ₁ V ₂, V ₅) не является гамильтоновым (рис. 2.10).

Задача 18 «О кенигсбергских мостах» (Эйлера). Необходимо обойти все 7 мостов так, чтобы на каждом побывать только один раз и вернуться к началу пути (рис. 2.11, а).

Граф к задаче о мостах изображен на рис. 2.11, б.

Задача Эйлера «О кенигсбергских мостах». Историческим поводом для создания математической науки, получившей впоследствии название «Теория графов», явилось решение в 1736 г. Л.Эйлером задачи о кенигсбергских мостах. В XVIII в. город Кенигсберг располагался на двух берегах реки Преголи, имеющей два острова, соединенных с берегами и между собой семью мостами. Жители города на практике решали задачу: можно ли пройти по всем семи мостам так, чтобы на каждом из них побывать по одному разу и вернуться к началу пути.

Рис. 2.11. Иллюстрации к задаче «О кенигсбергских мостах»: а — условие; б — граф.

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

Сформулируем задачу на языке теории графов: в произвольном неориентированном плоском графе G четырьмя красками раскрасить вершины так, чтобы никакие две смежные вершины не были раскрашены одним цветом. Оказывается, условие задачи выполнимо для пяти красок. Даже доказано, что такая раскраска возможна для всех плоских графов с числом вершин, не превосходящим 38. Но проблема четырех красок остается нерешенной с 1878 г., когда английский математик Кэли привел ее формулировку на заседании Английского королевского научного общества.

Задача «О трех домах и трех колодцах». Условие этой задачи нам известно: «Проложить дорожки от трех домов к каждому из трех колодцев так, чтобы никакие две дорожки не пересекались». Эта задача была решена Куратовским в 1930 г.

Дата добавления: 2014-11-29