"Чистая"
и прикладная математика

Теория графов: основные понятия и задачи

Что такое графы и теория графов?

Классические задачи теории графов

Инцидентность и понятия, связанные с инцидентностью

Ориентированные и неориентированные графы

Частные случаи графов. Виды вершин и рёбер

Маршруты, цепи и циклы в графах

Задачи с графами для закрепления основных понятий

Что такое графы и теория графов?

Теория графов - один из обширнейших разделов дискретной математики, широко применяется в решении экономических и управленческих задач, в программировании, химии, конструировании и изучении электрических цепей, коммуникации, психологии, психологии, социологии, лингвистике, других областях знаний. Теория графов систематически и последовательно изучает свойства графов, о которых можно сказать, что они состоят из множеств точек и множеств линий, отображающих связи между этими точками. Основателем теории графов считается Леонард Эйлер (1707-1882), решивший в 1736 году известную в то время задачу о кёнигсбергских мостах.

Графы строят для того, чтобы отобразить отношения на множествах. Пусть, например, множество A = {a1a2, ... an} - множество людей, а каждый элемент будет отображён в виде точки. Множество B = {b1b2, ... bm} - множество связок (прямых, дуг, отрезков - пока не важно). На множестве A задано отношение знакомства между людьми из этого множества. Строим граф из точек и связок. Связки будут связывать пары людей, знакомых между собой. Естественно, число знакомых у одних людей может отличаться от числа знакомых у других людей, а некоторые вполне могут и не быть ни с кем знакомы (такие элементы будут точками, не соединёнными ни с одной другой). Вот и получился граф!

чертёж к теории графов: построение графа для отображения отношения знакомства между людьми

То, что мы сначала назвали "точками", следует называть вершинами графа, а то, что называли "связками" - рёбрами графа.

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

А теперь строгие математические определения графа.

Определение 1. Графом называется система объектов произвольной природы (вершин) и связок (рёбер), соединяющих некоторые пары этих объектов.

Определение 2. Пусть V – (непустое) множество вершин, элементы vV – вершины. Граф G = G(V) с множеством вершин V есть некоторое cемейство пар вида: e = (ab), где a,bV, указывающих, какие вершины остаются соединёнными. Каждая пара e = (ab) - ребро графа. Множество U - множество рёбер e графа. Вершины a и b – концевые точки ребра e.

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

Классические задачи теории графов

Один из первых опубликованных примеров применения графов - работа о "задаче с Кёнигсбергскими мостами" (1736 г.), автором которой является выдающийся математик 18-го века Леонард Эйлер. В задаче даны река, острова, которые омываются этой рекой, и несколько мостов. Вопрос задачи: возможно ли, выйдя из некоторого пункта, пройти каждый мост только по одному разу и вернуться в начальный пункт? (рисунок ниже)

чертёж к теории графов: задача о кёнигсбергских мостах

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

чертёж к теории графов: задача о кёнигсбергских мостах

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

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

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

Кэли в 1858 г., занимаясь чисто практическими задачами органической химии, открыл важный класс графов, называемых деревьями. Он стремился перечислить изомеры насыщенных углеводородов, с данным числом атомов углерода. Кэли прежде всего сформулировал задачу абстрактно: найти число всех деревьев с p вершинами, каждое из которых имеет вершины со степенями 1 и 4. Ему не удалось сразу решить эту задачу, и он стал изменять её формулировку таким образом, чтобы можно было решить новую задачу о перечислении:

  • корневых деревьев (в которых выделена одна из вершин);
  • всех деревьев;
  • деревьев, у которых степени вершин не превышают 4;
  • деревьев, у которых степени вершин равны 1 и 4 (постановка задачи из химии).

Инцидентность и понятия, связанные с инцидентностью

Для того, чтобы задать граф аналитически, множества V вершин графа и множества U рёбер графа, которые фигурировали в определении, будет недостаточно. Потребуется ещё и множество P троек вида (aub), указывающих какую пару ab элементов множества вершин V соединяет тот или иной элемент u множества рёбер U графа. Элементы множества P называются инциденциями графа. Вот мы и подошли к одному из первых понятий теории графов - инцидентности. Инцидентность - это когда вершина a является либо началом либо концом ребра e. Две вершины называются инцидентными, если у них есть общее ребро.

Понятие инцидентности - одно из главных при создании структур данных для представления графов в памяти ЭВМ.

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

чертёж к теории графов: отображение инцидентности вершин

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

Итак, задаём граф следующими множествами:

множество вершин: V = {abcdef}

множество рёбер: U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}

множество инциденций: P = {(b, 1, a), (b, 2, a), (a, 3, b), (b, 4, b), (b, 5, b), (c, 6, c), (c, 7, c), (b, 8, d), (d, 8, b), (b, 9, d), (b, 10, e), (b, 11, e), (e, 11, b)}


Ориентированные и неориентированные графы

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

Ребро u, соединяющее вершину a с вершиной b (a ≠ b), назовём звеном, если множеству P принадлежать две инциденции: aub и bua.

Пример 2. Найти звенья в графе, представленном на рис А.

Ответ. Звенья данного графа изображены линиями 8 и 11 без указания направления.

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

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

Пример 3. Найти дуги в графе, представленном на рис А.

Ответ. Дуги данного графа представлены направленными линиями (стрелками), соединяющими первую из инцидентных вершин со второй. Вершины 1, 2, 9, 10 - дуги; первая из них соединяет вершину b с вершиной a, но не наоборот. То же самое относится и к другим дугам.

О дуге говорят, что она идёт из вершины b в вершину a. Графы, все рёбра которых являются дугами, называются ориентированными графами или орграфами.

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


Частные случаи графов. Виды вершин и рёбер

Рёбра u, для которых имеются инциденции вида (aua), то есть вершина соединена сама с собой, называются петлями.

Пример 4. Найти петли в графе, представленном на всё том же рис А.

Ответ. В данном графе петли представлены линиями, начинающимися и заканчивающимися на одной и той же вершине. Линии 4 и 5 - петли.

Если граф содержит петли, то это обстоятельство специально оговаривают, добавляя к основной харатеристике графа слова "с петлями", например, "орграф с петлями". Если граф не содержит петель, то добавляют слова "без петель".

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

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

Пример 5. Найти голую вершину в графе, представленном на всё том же рис А.

Ответ. В данном графе голой является вершина f.

Граф, состоящий только из голых вершин, называется пустым.

Изолированной называется вершина графа, которая инцидентна одной или нескольким петлям.

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

Пример 6. В графе, представленном на рис А, найти изолированные вершины, смежные и не смежные вершины, вершины, смежные сами с собой.

Ответ. В данном графе вершина c изолированная. Вершины a и b смежные, а вершины a и d - не смежные, вершина b смежна сама с собой.

Кратными называются рёбра, соединяющие одну и ту же пару вершин.

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

Пример 7. Найти кратные рёбра в графе, представленном на всё том же рис А.

Ответ. В данном графе рёбра 1, 2 и 3 - кратные; кратными являются также 4 и 5, рёбра 8, 9, рёбра 6, 7, а также 10 и 11.

Граф без дуг (то есть неориентированный), без петель и кратных рёбер называется обыкновенным. Обыкновенный граф изображён на рисунке ниже.

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

чертёж к теории графов: пример полного графа

Количество рёбер, инцидентных вершине графа, называется степенью этой вершины графа.

Маршруты, цепи и циклы в графах

Маршрутом в графе называется последовательность вершин и рёбер (v0e1, ..., envn ), такая, что любые две соседние вершины vi и vi+1 соединены ребром ei+1. Если в маршруте v0 = vn, то есть начальная вершина совпадает с конечной, то маршрут называется замкнутым или циклическим, в противном случае маршрут называется открытым. Число рёбер в маршруте называется длиной маршрута

Маршрут, в котором все рёбра различны, называется цепью.

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

Замкнутая цепь с положительной длиной называется циклом. Замкнутая простая цепь с положительной длиной называется простым циклом.

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

теория графов: чертёж для нахождения маршрутов, цепи, цикла

Ответ. В данном графе:

  • например, a1b2a1b7d8c9c8d - маршрут из вершины a в вершину d длины 7;
  • например, b5c6b7d - цепь;
  • например, цепь a1b5c8d - простая, а цепь e3e4e - не простая;
  • например, b5c9c8d7b - цикл длины 4 при вершине b;
  • например, b5c8d7b - простой цикл длины 1 при вершине b.

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

Задачи с графами для закрепления основных понятий

Пример 9. Пусть A - множество чисел 1, 2, 3: A = {1, 2, 3}. Построить граф для отображения отношения "<" ("меньше") на этом множестве.

Решение. Очевидно, что числа 1, 2, 3 следует представить в виде вершин графа. Тогда каждую пару вершин должно соединять одно ребро. До сих пор мы рассматривали не ориентированные графы, то есть такие, рёбра которых не имели направления. Или, как говорят ещё чаще, порядок двух концов ребра не существенен. В самом деле, граф, построенный в самом начале и отображавший отношение знакомства между людьми, не нуждается в направлениях рёбер, так как можно утверждать, что "человек номер 1" знаком с "человеком номер 2" в той же мере, как и "человек номер 2" с "человеком номер 1". В нашем же нынешнем примере одно число меньше другого, но не наоборот. Поэтому соответствующее ребро графа должно иметь направление, показывающее, какое всё же число меньше другого. То есть, порядок концов ребра существенен. Такой граф (с рёбрами, имеющими направление) называется ориентированным графом или орграфом.

Итак, в нашем множестве A число 1 меньше числа 2 и числа 3, а число 2 меньше числа 3. Этот факт отображаем рёбрами, имеющими направление, что показывается стрелками. Получаем следующий граф:

чертёж к теории графов: построение графа для отображения отношения меньше

Пример 10. Пусть A - множество чисел 2, 4, 6, 14: A = {2, 4, 6, 14}. Постоить граф для отображения отношения "делится нацело на" на этом множестве.

Решение. В этом примере часть рёбер будут иметь направление, а некоторые не будут. Перечислим отношения на множестве: 4 делится нацело на 2, 6 делится нацело на 2, 14 делится нацело на 2, и ещё каждое число из этого множества делится нацело на само себя. Это отношение, то есть когда число делится нацело на само себя, будем отображать в виде рёбер, которые соединяют вершину саму с собой. Такие рёбра называются петлями. В данном случае нет необходимости давать направление петле. Таким образом, в нашем примере три обычных направленных ребра и четыре петли. Получаем следующий граф:

Пример 11. Пусть даны множества A = {α, β, γ} и B = {a, b, c}. Построить граф для отображения отношения "декартово произведение множеств".

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

чертёж к теории графов: пример двудольного графа

Пример 12. В агентстве по недвижимости работают менеджеры Игорь, Сергей и Пётр. Обслуживаются объекты О1, О2, О3, О4, О5, О6, О7, О8. Построить граф для отображения отношений "Игорь работает с объектами О4, О7", "Сергей работает с объектами О1, О2, О3, О5, О6", "Пётр работает с объектом О8".

Решение. Граф, отображающий данные отношения, будет так же двудольным, так как менеджер не работает с менеджером и объект не работает с объектом. Однако, в отличии от предыдущего примера, граф будет ориентированным. В самом деле, например, Игорь работает с объектом О4, но не объект О4 работает с Игорем. Часто, когда такое свойство отношений очевидно, необходимость давать рёбрам направления может показаться "математической тупостью". Но всё же, и это вытекает из строгого характера математики, если отношение носит односторонний характер, то давать направления рёбрам нужно. В приложениях отношений эта строгость окупается, например, в программах, предназначенных для планирования, где тоже применяются графы и маршрут по вершинам и рёбрам должен проходить строго в заданном направлении. Итак, получаем следующий ориентированный двудольный граф:

чертёж к теории графов: пример двудольного ориентированного графа

И вновь к примерам с числами.

Пример 13. Пусть задано множество C = {2, 3, 5, 6, 15, 18}. Построить граф, реализующий отношение, определяющее все пары чисел a и b из множества C, у которых при делении второго элемента на первый получаем частное, которое является целым числом больше 1.

Решение. Граф, отображающий данные отношения, будет ориентированным, так как в условии есть упоминание о втором и первом элементе, то есть, ребро будет направлено от первого элемента ко второму. Из этого однозначно понятно, какой элемент является перым, а какой вторым. Ещё добавим терминологии: ориентированные рёбра принято называть дугами. В нашем графе будет 7 дуг: e1 = (3, 15), e2 = (3, 18), e3 = (5, 15), e4 = (3, 6), e5 = (2, 18), e6 = (6, 18), e7 = (2, 6). В этом примере рёбра (дуги) графа просто пронумерованы, но порядковые номера - не единственное, что можно приписать дуге. Дуге можно приписать также весы означающие, например, стоимость пересылки груза из одного пункта в другой. Но с весами дуг мы познакомимся позже и подробнее. Итак, получаем следующий ориентированный граф:

чертёж к теории графов: пример ориентированного графа

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

Пример 14. На кусочке шахматной доски размером 3 Х 3 размещены два белых коня и два чёрных коня так, как показано на рисунке ниже.

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

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

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

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

Пример 15. Задача о волке, козе и капусте. На одном берегу реки находятся человек (Ч), лодка, волк (В), коза (Кз) и капуста (Кп). В лодке одновременно могут находиться человек и не более одного из перевозимых объектов. Человек должен перевезти на другой берег все объекты, соблюдая условие: нельзя оставлять без присмотра волка вместе с козой и козу вместе с капустой.

Решение. В конструируемом графе вершины - конфигурации, а рёбра - отношение "связь одним плаваньем лодки" между конфигурациями. Конфигурация означает расположение объектов на первоначальном берегу и на противоположном берегу. Каждая конфигурация отображается в виде (A|B), где A - объекты, находящиеся на первоначальном берегу, а B - объекты, находящиеся на противоположном берегу. Первоначальная конфигурация, таким образом, - (ЧВКпКз|). Например, после переправки на другой берег козы конфигурация будет (ВКп|ЧКз). Конечная конфигурация всегда (|ЧВКпКз). Теперь можем построить граф, зная уже, что означают вершины и рёбра:

Разместим вершины графа так, чтобы рёбра не пересекались, а соседними были вершины, которые связаны отношением на графе. Тогда увидеть отношения будет намного проще (для увеличения рисунка щёлкните по нему левой кнопкой мыши):

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

Весь блок "Теория графов"