b9e6dc71c45642409a56c5c591cde9f8

1.

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

2.

.
.
.

3.

4.

Во многих случаях жизни старая
привычка толкает нас рисовать на бумаге
точки, изображающие людей, населенные
пункты, химические вещества и т. д., и
соединять эти точки линиями или стрелками,
означающими некоторые отношения. Такие
схемы встречаются всюду под разными
названиями: социограммы (в психологии),
симплексы (в топологии), электрические цепи
(в физике), диаграммы организации (в
экономике),
сети
коммуникаций,
генеалогические деревья и т.д. Д.Кёниг, без
сомнения первый, предложил называть такие
схемы "графами" и систематически изучать
их свойства.

5.

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

6.

7.

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

8.

Один и тот же граф может выглядеть на
рисунках по-разному

9.

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

10.

Путь называется простым, если он не
проходит ни через одну из вершин графа
более одного раза

11.

Задача
о
Кенигсбергских
мостах.
На
рисунке
представлен
схематический
план центральной части города
Кенигсберг (ныне Калининград),
включающий два берега реки
Перголя, два острова в ней и
семь соединяющих мостов.
Задача состоит в том, чтобы
обойти все четыре части суши,
пройдя по каждому мосту один
раз, и вернуться в исходную
точку. Эта задача была решена
(показано, что решение не
существует) Эйлером в 1736
году.

12.

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

13.

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

14.

15.

Решение задач.
Задача №1

16.

Решение задач.
Задача №2

17.

Решение задач.
Задача №3

18.

Решение задач.
Задача №4

19.

Решение задач.
Задача №5

20.

Решение задач.
Задача №6

21.

Решение задач.
Задача №7

22.

Решение задач.
Задача №8

23.

Решение задач.
Задача №9