Эйлеровы и гамельтовы графы

ВВЕДЕНИЕ

 

Первая работа по теории графов, принадлежащая  известному швейцарскому математику Л.Эйлеру, появилась в 1736г. Вначале теория графов казалась довольно незначительным разделом математики, так как она имела дело в основном с математическими развлечениями и головоломками. Однако дальнейшее развитие математики и особенно её приложений дало сильный толчок развитию теории графов. Уже в XIX столетии графы использовались при построении схем.

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

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

   

 

 

 

 

 

ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ  ТЕОРИИ ГРАФОВ

1. ПОНЯТИЕ "ГРАФ"

Граф G – пара (V,X), где V конечное непустое множество,  содержащее  p вершин, а множество Х содержит q неупорядоченных пар различных вершин из V.

Каждую пару X={u,v} вершин в Х называют ребром графа G и говорят, что Х соединяет u и v.Мы будем писать X=uv и говорить, что u и v – смежные вершины. Вершина u и ребро Х инцидентны, так же как v и Х. Если два различных ребра X и Y инцидентны одной и той же вершине, то они называются смежными. Граф с р вершинами и q ребрами называется (p;q)- графом. Граф (1,0)- называется тривиальным.[6]

Если элементом множества V может быть пара одинаковых элементов u, то такой элемент множества V называется петлёй.[3]

Типы графов:

• Мультиграф, в нём не допускаются петли, но пары вершин могут соединяться более чем одним ребром, эти рёбра называются кратными (рис.1).
• Псевдограф, в нём допускаются петли и кратные рёбра (рис.2).

 

 

            Рис.1                                                   Рис.2

• Ориентированный граф, или орграф, состоит из конечного непустого множества V вершин и заданного набора Х упорядоченных пар различных вершин. Элементы из Х называются ориентированными рёбрами, или дугами. Нет петель и кратных дуг (рис. 3).

 

 

• Направленный граф – это орграф, не имеющий симметричных пар ориентированных рёбер (рис.4).
• Помеченные графы (или перенумерованные), если его вершины отличаются одна от другой какими-либо пометками. В качестве пометок обычно используются буквы или целые числа.[6]

Степенью вершины v_i  в графе G называется число рёбер, инцидентных v_i ,обозначается d_i.[6] Для орграфа вводятся понятия степени входа и выхода. Степенью выхода вершины v называется количество рёбер, для которых v является начальной вершиной, обозначается outdeg(v). Степенью входа вершины v называется количество рёбер , для которых v является конечной вершиной, обозначается indeg(v). Если indeg(v)=0, то вершина v называется источником. Если outdeg(v)=0, то вершина v называется стоком.

 

 

 

1.2. Маршруты и связность

 

Граф G^/(U^/,V^/) называется подграфом графа G(U,V), если  U^/ÌU и V^/ÌV. Обозначение: G^/ÌG.

Если V^/=V, то G^/ называется остовным подграфом G.[3]

Маршрутом в графе G называется чередующаяся последовательность вершин и рёбер v₀,x₁,v₁,…v_n-1,x_n,v_n; эта последовательность начинается и кончается вершиной, и каждое ребро последовательности инцидентно двум вершинам, одна из которых непосредственно предшествует ему, а другая непосредственно следует за ним. Указанный маршрут соединяет вершины v₀ и v_n и его можно обозначить v₀v₁v₂…v_n (наличие рёбер подразумевается). Эта последовательность иногда называется (v₀-v_n)-маршрутом. Маршрут замкнут, если v₀=v_n, и открыт в противном случае. Маршрут называется цепью, если все его рёбра различны, и простой цепью, если все вершины (а следовательно, и рёбра ) различны. Замкнутая цепь называется циклом. Замкнутый маршрут называется простым циклом, если все его  n вершин различны и n³3.

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

Свойства маршрутов, цепей  и циклов

1. Всякий незамкнутый (и, v)- маршрут, содержит в себе простую (и, v)- цепь. В частности, любая (и, v)- цепь, содержит в себе простую (и, v)- цепь. Причем, если (и, v)- маршрут содержит в себе вершину w (w^u и w^v), то в общем случае, простая (и, v)- цепь может не содержать в себе вершину w.
2. Всякий непростой цикл можно разбить на два или более простых. Причем для замкнутого маршрута такое утверждение не верно.
3. Всякая непростая (и, v)- цепь, может быть разбита на простую (и, v)- цепь и один или более простых циклов. Причем для незамкнутого маршрута такое утверждение не верно.

  4)  Для любых трех вершин и, w, v из существования (и, w)- цепи их и (w, v)- цепи, следует существование (и, v)- цепи. Причем может не существовать

(и, v)- цепи, содержащей вершину w.

      5) Объединение двух несовпадающих простых (и, v)- цепей содержит простой цикл.

6. Если граф содержит 2 несовпадающих цикла с общим ребром e, то после удаления этого ребра граф по-прежнему содержит цикл.

Лемма. Если два графа изоморфны:

1. то они одного порядка;
2. у них одинаковое количество ребер;
3. для произвольного i, 0 <i<n-1, (n - порядок графов) количество вершин степени i, у обоих графов одинаковое;
4. у них совпадают обхваты;
5. у них одинаковое количество простых циклов минимальной длины (по количеству ребер).

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

     Теорема. Граф G=(V,E) связен тогда и только тогда, когда множество

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1.3. СТЕПЕНИ ВЕРШИН ГРАФА  И ИХ СВОЙСТВА

Степенью вершины графа  G называется число инцидентных ей ребер, т.е. число вершин в ее окружении. Будем обозначать степень вершины v через deg_Gv (или deg v).Тем самым deg v=|N(v)|. Максимальная и минимальная степени вершин графа G обозначаются символами Δ(G) и δ(G) соответственно.

Вершина степени 0 называется изолированной, вершина степени 1 — висячей (или концевой). Ребро, инцидентное концевой вершине также называется концевым.

Теорема.    Сумма степеней всех вершин графа есть число, равное удвоенному числу ребер.

Следствие (лемма о рукопожатиях). В любом графе число вершин нечетной степени четно.

Граф называется регулярным (или однородным), если степени всех его вершин равны; степенью регулярного графа называется степень его вершин. Степень регулярного графа G обозначается через deg G.

 

 

 

 

 

Матрицей смежности графа G с множеством  вершин {v₁ ..., v_n} (соответствующей данной нумерации вершин) называется матрица А = (a_ij) размера n X n, в которой элемент а_ij- равен числу ребер в G, соединяющих v₁ и v_j. Например, на рис. 2.6 дана матрица смежности графа, изображенного на рис. 2.4.

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

 

Примеры задач и их решение

Задача 1.

 Утверждают что в  одной компании из пяти человек  каждый знаком с двумя и  только с двумя другими.  Возможна  ли такая компания?

Решение.

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

Задача  2.

 Участники пионерского  слета, познакомившись, обменялись  конвертами с адресами. Докажите, что 

а) всего было передано четное число конвертов;

б) число участников, обменявшихся конвертами нечетное  число раз, четное.

Решение.

Пусть участники слета  А₁,A₂, ..., А_n - вершины графа, а ребра соединяют на рисунке пары вершин, изображающих ребят, обменявшихся конвертами:

а) степень каждой вершины A_i показывает число конвертов, которые передал участник А_i своим знакомым. Общее число переданных  конвертов N равно сумме степеней всех вершин  графа. N = степ. A₁ +степ. A₂ +...+степ. A_n-1 + + степ. A_n, но N = 2р, где р — число ребер графа, то есть N — четное. Следовательно, было передано четное число конвертов;

б) в равенстве N = степ. . A₁ +степ. A₂ +...+степ. A_n-1 + + степ. A_n сумма нечетных слагаемых должна быть четной, а это может быть только в том случае, если число нечетных слагаемых четно. А это означает, что число участников, обменявшихся  конвертами нечетное число раз, четное.

 

 

 

 

 

 

 

Эйлеровы графы 2.1 Задача  о  кёнигсбергских  мостах.   Отцом теории графов является Эйлер (1707-1782), решивший в 1736г. широко известную  в то время задачу, называвшуюся проблемой Кёнигсбергских мостов. В  городе Кёнигсберге (ныне Калининград) было два острова, соединенных семью  мостами с берегами реки Преголя  и друг с другом так, как показано на рисунке 5. Задача состояла в следующем: найти маршрут прохождения всех четырёх частей суши, который начинался бы с любой из них, кончался бы на этой же части и ровно один раз проходил по каждому мосту.

 

 

                                                                       Рис.5.

 

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

Для доказательства того, что задача не имеет решения, Эйлер обозначил каждую часть суши точкой (вершиной), а каждый мост – линией (ребром), соединяющей соответствующие точки. Получился “граф”. Этот граф показан на рисунке 6, где точки отмечены теми же буквами, что и четыре части суши на рисунке 5. 

 

 

 

 

Рис.6.

 

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

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

 

2.2 Эйлеровы  графы

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

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