Тема №8. Введение в теорию графов

класс
Тема №8. Введение в теорию графов

математик Денеш Кёниг («Теория конечных и бесконечных графов»).
1) Основоположник

теории графов - Леонард Эйлер (1736 год, задача о Кёнигсбергских мостах)

Денеш Кёниг (1884-1944)

Леонард Эйлер (1707-1783)

Популяризация ТГ - книга французского математика Клода Бержа: «Теория графов и ее применения», 1960 г.

Клод Берж (1926-2002)

Применение ТГ
1. Упрощение решения задач, в различных областях знаний:
в

автоматике, электронике, физике, химии и др.

2. Изображение схемы дорог, газопроводов, тепло и электросети.

попарно соединяющих некоторые из этих вершин линий (ребрам или дуги

графа).

Вершины графа: A, B, C, D.
Граф в целом одна заглавная буква.

3. Основные понятия

Граф - непустое множество точек (вершин) и отрезков (ребер), оба конца которых принадлежат заданному множеству точек.

U - бинарное отношение на множестве вершин
U  V 2

состоящий только из изолированных вершин, называется нуль-графом.
Обозначение: O' – граф

с вершинами, не имеющий ребер.

4.Граф, в котором каждая пара вершин соединена ребром, называется полным.
Обозначение: U' – граф, состоящий из n вершин и ребер, соединяющих всевозможные пары этих вершин. Такой граф можно представить как n–угольник, в котором проведены все диагонали.

5.Степенью вершины называется число ребер, которым принадлежит вершина.
Обозначение: p (A) – степень вершины A.

A к X, такая, что каждые два соседних ребра имеют

общую вершину, и никакое ребро не встречается более одного раза.

7.Циклом называется путь, в котором совпадают начальная и конечная точка.

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

9. Длиной пути, проложенного на цикле, называется число ребер этого пути.

же в графе найдется хотя бы одна пара несвязных вершин,

то граф называется несвязным.

12.Деревом называется связный граф, не содержащий циклов.

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

10.Две вершины A и B в графе называются связными (несвязными), если в нем существует (не существует) путь, ведущий из A в B.

раз через каждый из этих мостов?

четным или нечетным.
Так, в нашем случае к участку A

ведут пять мостов, а к остальным – по три моста.

Представим задачу в виде графа, где вершины – острова и берега (A,B,C,D), а ребра – мосты

можно изобразить «одним росчерком пера».

не отрывая карандаш от бумаги, при этом движение нужно начать

с одной из этих нечетных вершин и закончить во второй из них.

«одним росчерком».

кружочках.
Нечетные вершины: А, B, C, D.
3
3
3
5

как данный граф имеет более двух нечетных вершин.

(Эйлерова линия)
Условия существования Эйлеровой линии:
-граф связный
-все вершины четные
Другими словами,

эйлеров граф – это граф, который можно нарисовать одним росчерком

Эйлеров граф

берега, а ребра – мосты.
2. Определить степень каждой вершины

и подписать возле нее.
3. Посчитать количество нечетных вершин.
4. Обход возможен:
a. ЕСЛИ все вершины – четные, и его можно начать с любого участка.
b. ЕСЛИ 2 вершины – нечетные, но его нужно начать с одной из нечетных местностей.
5. Обход невозможен, если нечетных вершин больше 2.
6. Сделать ВЫВОД.
7. Указать Начало и Конец пути.

– мосты.
Нечетные вершины: D, E. 
ВЫВОД: Так как количество нечетных вершин

= 2, то обход возможен.
Его Начало может быть в местности D, а Конец в местности E.

4

4

6

3

5

8

(решить с помощью графа)

ключ. Чтобы его найти нужно войти в одну из крайних

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

Укажите номер комнаты с ключом

движение из нечетной вершины