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

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

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

Рисунок 4- Задача о кёнигсбергских мостах.

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

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

Рисунок 5 – Граф.

Элементы графа. Способы задания графа. Подграфы.

Такая структура как граф в качестве (синонима используется также термин «сеть»), имеет самые различные применения в информатике.

Графом G называется система (V, U),

где V={v} — множество элементов, называемых вершинами графа;

U=={u} — .множество элементов, называемых ребрами графа.

• Каждое ребро определяется либо парой вершин (v1,v2), либо двумя противоположными парами (v1,v2) и (v2,v1).

• Если ребро из U представляется только одной парой (v1,v2), то оно называется ориентированным ребром, ведущим из v1 в v2. При этом v1 называется началом, а v2 -концом такого ребра.

• Если ребро U представляется двумя парами (v1,v2) и (v2,v1), то U называется неориентированным ребром. Всякое неориентированное ребро между вершинами v1 и v2 ведет как из v1 в v2, так и обратно. При этом вершины v1 и v2 являются как началами, так и концами этого ребра. Говорят, что ребро ведет как из v1 в v2, так и из v2 в v1.

• Всякие две вершины, которые соединяются ребром, являются смежными.

v1 v2

• По количеству элементов графы делятся на конечные и бесконечные.

• Граф, все рёбра которого неориентированные, называется неориентированным графом.

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

Рисунок 6 – Ориентированный граф.

• Существуют смешанные графы, состоящие как из ориентированных, так и из неориентированных рёбер.

• Если две вершины соединены двумя или более рёбрами, то эти рёбра называют параллельными.

• Если начало и конец ребра совпадают, то такое ребро называется петлёй .

• Граф без петель и параллельных рёбер называется простым.

• Если ребро определяется вершинами v1 и v2, то ребро инцидентно вершинам v1 и v2.

• Вершина, не инцидентная ни одному ребру, называется изо­лированной.

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

• Ребра, которым поставлена в соответствие одна и та же пара вер­шин, называются кратными, или параллельными.

• Две вершины неориентированного графа v1 и v2 называются смежными, если в графе существует ребро (v1,v2).

• Две вершины ориентированного графа v1 и v2 называются смежными, если они различны и существует ребро, ведущее из вершины v1 в v2.

Рассмотрим некоторые понятия для ориентированного графа.

• Путём в графе называется такая последовательность рёбер u1,u2,…un , в которой конец каждого предыдущего ребра совпадает с началом последующего.

• Длина пути - это число рёбер, составляющих путь. Возможна длина пути =

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

• Контур – это конечный путь, у которого начальная вершина v1 совпадает с конечной вершиной

• Контур называется элементарным, если все вершин, через которые он проходит, различны между собой.

Рисунок 7 – Ориентированный граф.

Путь:

Простой путь:

Элементарный путь:

Элементарный контур:

Контур:

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

• Неориентированный связный граф без циклов называется деревом.

• Неориентированный несвязный граф без циклов - лесом.

Рисунок 8 – Связный граф.

Рисунок 9 –Лес.

Рисунок 10 – Дерево.