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

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

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

     Теория  графов многократно «открывалась»  разными авторами при решении  различных прикладных задач.

     Но  полноправно можно  сказать, что теория графов берет начало с решения задачи о кенигсбергских мостах в 1736 году знаменитым математиком Леонардом  Эйлером (1707-1783: родился  в Швейцарии, жил  и работал в  России).

     Задача  о кенигсбергских мостах.

       

     Жителям Кенигсберга нравилось гулять по дорожкам, которые включали семь мостов, соединяющие два острова и  берега реки Преголя. Люди интересовались, могут ли они, начав путь с одного участка суши, обойти все мосты, посетив каждый лишь однажды, и вернуться в точку начала пути, не переплывая реку. Для решения задачи Эйлер построил граф: участки суши изобразил вершинами, а дорожки через мосты – как ребра. Сначала им была сформулирована и доказана теорема. И опираясь на эту теорему, Эйлер показал, что такого маршрута нельзя построить. Далее мы рассмотрим, как Эйлер решил эту задача.

     Кроме задачи о кенигсбергских мостах, классическими  задачами стали: задача о трех домах и трех колодцах; задача о четырех красках.

     Задача  о трех домах и  трех колодцах.  Имеется три дома и три колодца, каким-то образом расположенные на плоскости. Провести от каждого дома к каждому колодцу тропинку так, чтобы тропинки не пересекались. Эта задача была решена (показано, что решения не существует) К Куратовским (1896 – 1979) в 1930 году.

H

H

H

     Задача  о четырех красках.  Разбиение плоскости на непересекающиеся области называется картой. Области карты называются соседними, если они имеют общую границу. Задача состоит в раскрашивании карты таким образом, чтобы никакие две области не были закрашены одним цветом. С конца XIX века известна гипотеза, что для этого достаточно четырех красок. В 1976 году Аппель и Хейкен опубликовали решение задачи о четырех красках, которая базировалось на переборе вариантов с помощью компьютера.

     Суть  опубликованного решения состоит  в том, чтобы перебрать большое, но конечное число (около 2000) типов потенциальных  контрпримеров к теореме о четырех красках и показать, что ни один случай контрпримером не является. Этот перебор был выполнен программой примерно за тысячу часов работы суперкомпьютера. Проверить «вручную» полученное решение невозможно – объем перебора выходит за рамки человеческих возможностей. Многие математики ставят вопрос: можно ли считать такое «программное доказательство» действительным доказательством? Ведь в программе могут быть ошибки… Методы формального доказательства правильности программ не применимы к программам такой сложности, как обсуждаемая. Тестирование не может гарантировать отсутствие ошибок. Таким образом, остается уповать на программистскую квалификацию авторов и верить, что они все сделали правильно. 

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

     Определение 1.  Графом G=G(V, E) называется совокупность двух множеств – непустого множества V (множества вершин) и множество E двухэлементных подмножеств множества V. Множество E называется множеством ребер. 

     Вершины v_i и v_j множества V называются соединенными ребром (v_i, v_j) или инцидентны к ребру (v_i, v_j), если (v_i, v_j)ÎE. Если (v_i, v_j) – ребро, тогда вершины v_i и v_j называются концами ребра (v_i, v_j). Ребро (v_i, v_j) называется также инцидентным к вершинам v_i и v_j. Две вершины называются смежными, если они инцидентны к одному ребру. Два ребра называются смежными, если они инцидентны к общей вершине.

     Число вершин графа G обозначим v, а число ребер - e:

      . 

     Определение 2.  Ориентированный граф или орграф G=G(V, E) – это такой граф, который состоит из множества V вершин и множества E упорядоченных пар элементов из V. Элемент множества E называется дугой. Если (v_i, v_j)ÎE, то v_i называется начальной вершиной дуги (v_i, v_j), а v_j называется конечной вершиной. 

     Геометрическое  представление графов следующее:

     1)  вершина графа – точка в  пространстве (на плоскости);

     2)  ребро неориентированного графа  – отрезок;

     3)  дуга ориентированного графа  – направленный отрезок. 

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

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

     Определение 3.  Граф G¢(V¢, E¢) называется подграфом (или частью) графа G(V,E), если V¢ ÍV, E¢ ÍE. Если V¢=V, то G¢ называется остовным подграфом G. 

     Аналогично, как и для графа, для орграфа  вводится понятие ориентированный  подграф. 

     Определение  4.  Граф называется полным, если любые две его вершины соединены ребром. Полный граф с n вершинами обозначается через K_n.

     Определение 5.  Граф G=G(V, E) называется двудольным, если V можно представить как объединение непересекающихся множеств, скажем V=AÈB, так что каждое ребро имеет вид (v_i, v_j), где v_iÎA и v_jÎB. Двудольный граф называется полным двудольным графом K_{m, n}, если A содержит m вершин, B содержит n вершин и для каждого v_iÎA, v_jÎB имеем (v_i, v_j)ÎE.

     Пример.  Построить полный двудольный граф K_2,4 и полный граф K₄. 

v₁

v₂

v₃

v₄

v₅

v₆

x₁

x₂

x₃

x₄

Полный двудольный граф K_2,4

A={v₁, v₂}

B={v₃, v₄, v₅, v₆}

Полный граф K₄

 
 
 

2.  Связность графов. 

     Определение 6.  Пусть G=G(V, E) – граф с вершинами v₀, v₁, v₂, …, v_nÎV и ребрами e₁, e₂, …, e_mÎE. Маршрутом (путем) длины k из v₀ в v_k (или между v₀ и v_k) называется последовательность v₀e₁v₁e₂v₂e₃v₃…v_k-1e_kv_k такая, что e_i=(v_i-1, v_i).

     Таким образом, путь длины k имеет k ребер. По причине избыточности обозначений в этом определении для графа в общем случае путь будет обозначаться через v₀v₁v₂…v_k.

     Если  все ребра различны, то путь называется цепью. Если все вершины различны (а значит, и ребра), то путь называется простой цепью. Замкнутая цепь называется циклом. Замкнутая простая цепь называется простым циклом. Граф без циклов называется ациклическим.

     Аналогично, как и для графа, для орграфа  вводятся понятия ориентированный  путь, ориентированный цикл.

     Пример  3.  Дан неориентированный граф.

v₁

v₂

v₃

v₄

v₅

e₁

e₂

e₃

e₄

e₆

e₅

G(V, E) – граф

v₁e₁v₂e₂v₃e₃v₁e₁v₂e₅v₅ или v₁v₂v₃v₁v₂v₅ – маршрут

v₁v₂v₃v₁v₅ – цепь

v₁v₃v₂v₅ – простая цепь

v₁v₃v₂v₅v₁ – простой цикл

     , 

     Определение 7.  Граф G=G(V, E) называется связным, если имеется цепь между любыми двумя его различными вершинами.

     Для заданного ориентированного графа  G можно построить неориентированный граф такой, что каждая ориентированная дуга G (исключая петли) станет неориентированным ребром графа . В таком случае граф называется соотнесенным графом орграфа G(V, E).

     Определение 8.  Орграф G(V, E) называется связным, если его соотнесенный граф является связным. Орграф называется сильно связным, если для любой пары вершин v_i ,v_jÎV существует ориентированный путь из v_i в v_j. 
 

     3.  Изоморфизм графов. 

     Определение 9.  Функция f : G(V, E) ® G₁(V₁, E₁) является изоморфизмом (обозначается G~G₁), если f: V®V₁ и f: E® E₁ представляют собой взаимно однозначные соответствия. Если f:G®G₁ – изоморфизм, то G и G₁ называются изоморфными.