Графы. История теории графов. Определения. Смежности и инцидентность

3. Графы 2 3.1. Основные понятия 2 3.1.1. История теории графов 2 3.1.2. Определения 3 3.1.3. Смежности и инцидентность 4 3.1.4. Изоморфизм графов 5 3.2. Представление графов в ЭВМ 6 3.2.1. Требования к представлению графов 6 3.2.2. Матрица смежности 7 3.2.3. Матрица инциденций 7 3.3. Геометрическая реализация графов 8 3.4. Маршруты, цепи, циклы 8 3.4.1. Определения 8 3.4.2. Эйлеровы графы 9 3.4.3. Гамильтоновы графы 10 3.5. Заключение 12 1. Графы Среди дисциплин и методов дискретной математики теория графов и особенно алгоритмы на графах находят наиболее широкое примене­ние в программировании. Дело в том, что тео­рия графов предоставляет очень удобный язык для описания программных (да и многих других) моделей. Этот тезис можно пояснить следующей аналогией. Понятие отношения также можно полностью выразить через понятие множества. Однако независимое определение понятия отношения удобнее - введение специальных терминов и обозначений упрощает изложение теории и делает ее более понятной. То же относится и к теории графов. Стройная система специальных терминов и обозначений тео­рии графов позволяют просто и доступно описывать сложные и тонкие вещи. Особенно важно наличие наглядной графической интерпретации понятия графа. Само название «граф» подразумевает наличие графической ин­терпретации. Картинки позволяют сразу «усмотреть» суть дела на интуитивном уровне, дополняя и украшая утомительные рациональные текстовые доказатель­ства и сложные формулы. 1.1. Основные понятия 1.1.1. История теории графов Теория графов многократно переоткрывалась разными авторами при решении различных прикладных задач. 1. Задача о Кенигсбергских мостах. Обойти все четыре части суши, пройдя по каждому мосту один раз, и вернуться в исходную точку (рис. 3.1). Эта задача была решена Эйлером в 1736 году. Рис. 3.1. Иллюстрация к задаче о Кенигсбергских мостах 2. Задача о трех домах и трех колодцах. Имеется три дома и три колодца. Про­вести от каждого дома к каждому колодцу тропинку так, чтобы тропинки не пересекались (рис. 3.2). Эта задача была решена Куратовским в 1930 году. Рис. 3.2. Иллюстрация к задаче о трех домах и трех колодцах Предметом первых задач теории графов были различные конфигурации, состоящие из точек и соединяющих их линий. При этом несущественно: являются ли эти линии прямыми или кривыми, длинными или короткими, тонкими или толстыми; важно только то, какие точки они соединяют. Т.о. граф – это абстрактное математическое понятие. 1.1.2. Определения Графом G(V,E) называется совокупность двух множеств - непустого множества V (множества вершин) и множества Е неупорядоченных пар различных элемен­тов множества V (Е - множество ребер). G(V,E): , EVxV. Число вершин графа G обозначим р, а число ребер – q. р(G) = |V| q(G) = |E|. Часто рассматриваются следующие родственные графам объекты. 1. Если элементами множества Е являются упорядоченные пары, то граф назы­вается ориентированным (или орграфом). В этом случае элементы множества V называются узлами, а элементы множества - дугами (G(V, )). 2. Если элементом множества Е может быть пара одинаковых (не различных) элементов V, то такой элемент множества Е называется петлей, а граф назы­вается графом с петлями (или псевдографом). 3. Если Е является не множеством, а набором, содержащим несколько одинако­вых элементов, то эти элементы называются кратными ребрами, а граф назы­вается мультиграфом. Далее выражение: граф G(V,E) означает неориентированный граф без петель и кратных ребер. Обычно граф изображают диаграммой: вершины - точками (или кружками), ребра - линиями. Примеры. 1. . . Т.о. это неориентированный граф с петлей и кратными ребрами. Рис. 3.3. Неориентированный граф с петлей и кратными ребрами. 2. . . Т.о. это ориентированный граф с петлей и кратными ребрами. Рис. 3.4. Ориентированный граф с петлей и кратными ребрами. 3. . , т.о. Рис. 3.5. Неориентированный граф с петлей. 1.1.3. Смежность и инцидентность Пусть v1, v2 - вершины, е = (v1, v2) - соединяющее их ребро. Тогда вершина v1 и ребро е инцидентны, вершина v2 и ребро е также инцидентны. Два ребра, инцидентные одной вершине, называются смежными; две вершины, инцидентные одному ребру, также называются смежными. Степенью вершины v графа G(V,E) называется число ребер, инцидентных данной вершине. Обозначение: . Вершина, имеющая степень 0 называется изолированной, имеющая степень 1 – висячей. Пример. Для графа, изображенного на рис. 3.5: вершина 3 – изолированная, вершины 1 и 4 - висячие. Пример. Для графа, изображенного на рис. 3.3. Ребро e1 инцидентно вершинам v1 и v2. Вершина v1 инцидентна ребрам e1 и e2. Ребра e1 и e2 – смежны. Вершины v1 и v2 – смежны. . p(G)=3, q(G)=5. Т.о. можно заметить, что . Теорема Эйлера: . Доказательство данной теоремы вытекает из того, что каждое ребро дает двойной вклад в сумму степеней вершин. 1.1.4. Изоморфизм графов Говорят, что два графа G1(V1,E1) и G2(V2,E2) изоморфны (обозначается G1~ G2), если существует биекция h: V1 V2, сохраняющая смежность. Графы рассматриваются с точностью до изоморфизма. Пример Три внешне различные диаграммы, приведенные на рис. 3.6, являются диаграм­мами одного и того же графа К3,3. Рис. 3.6. Диаграммы изоморфных графов Числовая характеристика, одинаковая для всех изоморфных графов, называется инвариантом графа. Так, p(G) и q(G) - инварианты графа G. Не известно никакого набора инвариантов, определяющих граф с точностью до изоморфизма. Рис. 3.8. Диаграммы неизоморфных графов с совпадающими инвариантами 1.2. Представление графов в ЭВМ Следует подчеркнуть, что конструирование структур данных для пред­ставления в программе объектов математической модели - это основа искус­ства практического программирования. Мы приводим два различных базовых представления графов. Выбор наилучшего представления определяется требова­ниями конкретной задачи. Более того, при решении конкретных задач исполь­зуются, как правило, некоторые комбинации или модификации указанных пред­ставлений, общее число которых необозримо. Но все они, так или иначе, основаны на тех базовых идеях, которые описаны в этом разделе. 1.2.1. Требования к представлению графов Известны различные способы представления графов в памяти компьютера, кото­рые различаются объемом занимаемой памяти и скоростью выполнения опера­ций над графами. Представление выбирается, исходя из потребностей конкрет­ной задачи. Далее приведены два из наиболее часто используемых представле­ния. Указанные представления пригодны для графов и орграфов, а после некоторой модифи­кации также и для псевдографов, мультиграфов. Представления иллюстрируются на конкретных примерах графа G и орграфа D, диаграммы которых представлены на рис. 7.10. Рис. 3.9. Диаграммы графа (слева) и орграфа (справа), используемых в качестве примеров 1.2.2. Матрица смежности Представление графа с помощью квадратной булевской матрицы отражающей смежность вершин, называется матрицей смежности, где Пример 1.2.3. Матрица инциденций Представление графа с помощью матрицы Н: array [l..p, l..q] of 0..1 (для оргра­фов Н: array [l..p, l..q] of -1..1), отражающей инцидентность вершин и ребер, называется матрицей инциденций, где для неориентированного графа: а для ориентированного графа Пример 1.3. Геометрическая реализация графов Фигура F называется геометрической реализацией графа G(V,E), если существует взаимно однозначное соответствие между точками фигуры F и вершинами графа, между кривыми фигуры и ребрами, такое, что соответствующие кривые и ребра соединяют соответствующие точки и вершины. Правильная укладка – это реализация графа, при которой разным вершинам соответствуют разные точки, а кривые, соответствующие ребрам, не проходят через точки (исключая концевые) и не пере ссекаются. Теорема: каждый конечный граф допускает правильную укладку в трехмерном пространстве. Граф называет планарным, если он допускает правильную укладку на плоскости. Теорема (доказано в топологии): граф планарен, если он не имеет подграфов, изоморфных графам K5 и K3,3. 1.4. Маршруты, цепи, циклы 1.4.1. Определения Маршрутом в графе G(V,E) называется чередующаяся последовательность вершин и ребер v1, e1, v2, e2, ... ,vk ,ek,vk+1, в которой любые два соседних элемента инцидентны. Это определение подходит также для псевдо-, мульти- и орграфов. Для «обычного» графа достаточно указать только последовательность вершин или только последовательность ребер. Если v1=vk+1, то маршрут замкнут, иначе открыт. Если все ребра различны, то маршрут называется цепью. Если все вершины цепи различны, то цепь называется простой. Замкнутая цепь называется циклом; замкнутая простая цепь называется простым циклом. Число циклов в графе G обозначается z(G) (является инвариантом). Граф без циклов называется ациклическим. Для орграфов цепь называется путем, а цикл - контуром. Пример В графе, диаграмма которого приведена на рис. 3.10: 1. v1,v3,v1,v4 - маршрут, но не цепь; 2. v1, v3, v5, v2, v3, v4 - цепь, но не простая цепь; 3. v1, v4, v3, v2, v5 - простая цепь; 4. v1, v3, v5, v2, v3, v4, v1- цикл, но не простой цикл; 5. v1,v3,v4 - простой цикл. Рис. 3.10. Маршруты, цепи, циклы Две вершины графа называются связанными, если существует маршрут, соединяющий эти вершины. Граф называется связным, если любая пара его вершин связанна. Граф называется деревом, если он связен и не содержит циклов. 1.4.2. Эйлеровы графы Вернемся к историческому примеру о Кенигсбергских мостах. В каком случае в графе можно найти цикл, в котором каждое ребро участвует ровно один раз? Цикл, содержащий каждое ребро ровно один раз, называется эйлеровым. Граф, содержащий эйлеровый цикл, называется эйлеровым графом. Теорема (критерий эйлеровости графа): конечный граф G(V,E) является эйлеровым, тогда и только тогда, когда он связен и степени всех его вершин – четны. Цепь, содержащая каждое ребро ровно один раз, называется эйлеровой. Граф, содержащий эйлерову цепь, называется полуэйлеровым графом. Теорема (критерий полуйлеровости графа): конечный граф G(V,E) является полуэйлеровым, тогда и только тогда, когда он связен и точно две го вершины имеют нечетную степень. 1.4.3. Гамильтоновы графы Кроме эйлеровых графов рассматриваются также гамильтоновы графы. Название «гамильтонов цикл» произошло от задачи «Кругосветное путешествие», придуманной Гамильтоном в позапрошлом веке: нужно обойти все вершины графа, диаграмма которого показана на рис. 3.11 (в исходной формулировке это были названия столиц различных стран), по одному разу и вернуться в исходную точку. Этот граф представляет собой укладку додекаэдра. Рис. 3.11. Задача «Кругосветное путешествие» Если граф имеет простой цикл, содержащий все вершины графа (по одному ра­зу), то такой цикл называется гамильтоновым циклом, а граф называется гамильтоновым графом. Гамильтонов цикл не обязательно содержит все ребра графа. Ясно, что гамиль­тоновым может быть только связный граф. Теорема (Дирак). Если в графе G(V, E) для любой вершины v выполняется: (v) р/2, то граф G является гамильтоновым. Рассмотрим следующую задачу, известную как задача коммивояжера. Имеется р городов, расстояния между которыми известны. Коммивояжер должен посетить все р городов по одному разу, вернувшись в тот, с которого начал. Требуется найти такой маршрут движения, при котором суммарное пройденное расстояние будет минимальным. Очевидно, что задача коммивояжера - это задача отыскания кратчайшего гамильтонова цикла в полном графе. Можно предложить следующую простую схему решения задачи коммивояжера: сгенерировать все р! возможных перестановок вершин полного графа, подсчи­тать для каждой перестановки длину маршрута и выбрать из них кратчайший. Очевидно, такое вычисление потребует огромного количества шагов. Как известно, р! с ростом р растет быстрее, чем любой полином от р, и даже быстрее, чем 2Р. Таким образом, решение задачи коммивояжера описанным методом полного перебора оказывается практически неосуществимым даже для сравнительно небольших р. Более того, известно, что задача коммиво­яжера принадлежит к числу так называемых NP-полных задач. Вкратце суть проблемы NP-полноты сводится следующему. В различных областях дискретной матема­тики, комбинаторики, логики и т. п. известно множество задач, принадлежащих к числу наиболее фундаментальных, для которых, несмотря на все усилия, не удалось найти алгоритмов решения, имеющих полиномиальную трудоемкость. Более того, если бы удалось отыскать эффективный алгоритм решения хотя бы одной из этих задач, то из этого немедленно следовало бы существование эффек­тивных алгоритмов для всех остальных задач данного класса. На этом основано общепринятое мнение, что таких алгоритмов не существует. Полезно сопоставить задачи отыскания эйлеровых и гамилыоновых циклов, рассмотрен­ные в этом и предыдущем разделах. Внешне формулировки этих задач очень похожи, однако они оказываются принципиально различными с точки зрения практического при­менения. Уже давно Эйлером получено просто проверяемое необходимое и достаточное условие существования в графе эйлерова цикла. Что касается гамильтоновых графов, то для них не известно необходимых и достаточных условий. На основе необходимого и досточного условия существования эйлерова цикла можно построить эффективные алгорит­мы отыскания такого цикла. В то же время задача проверки существования гамильтонова цикла оказывается NP-полной (также как и задача коммивояжера). Известно, что почти нет эйлеровых графов, и эффективный алгоритм отыскания эйлеровых циклов редко оказывается применимым на практике. Теорема: Эйлеровых графов почти нет (E(p) – число эйлеровых графов с p вершинами, G(p) – число всех графов с p вершинами): . С другой стороны, можно показать, что почти все графы гамильтоновы. Теорема: (H(p) – число гамильтоновых графов с p вершинами, G(p) – число всех графов с p вершинами): . Таким образом, задача отыскания гамильтонова цикла или экви­валентная задача коммивояжера являются практически востребованными, но для них не­известен (и, скорее всего, не существует) эффективный алгоритм решения. 1.5. Заключение В качестве моделей графы удобно использовать в тех случаях, когда рассматриваются системы каких-либо объектов, между которыми существуют определенные связи а также в тех случаях, когда изучается структура системы, возможности ее функционирования. В информатике графы используются в следующих разделах: • операционные системы; • алгоритмизация; • структуры данных; • моделирование и др.