Основные способы заданий графов. С помощью специальных структур

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

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

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

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

Путь:

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

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

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

Контур:

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

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

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

 

 

 

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

 

 

 

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

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

Рассмотрим пример геометрического задания графа, приведенный на рисунке 11.

Рисунок 11 - Пример геометрического задания графа

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