ТВИС. Теория графов

1.

ТВИС
Неустроев Глеб Александрович
[email protected]

2.

3.

Леонард Эйлер
(1707г – 1783гг)
Швейцарский, прусский и российский
математик
■ Теория графов зародилась в ходе решения головоломок двести с
лишним лет назад.
■ Основы теории графов как математической науки заложил в 1736
г. Леонард Эйлер, рассматривая задачу о кенигсбергских мостах.
■ Сегодня эта задача стала классической.

4.

Графы
■ Слово «граф» в математике означает картинку, где нарисовано
несколько точек, некоторые из которых соединены линиями.
■ В процессе решения задач математики заметили, что удобно
изображать объекты точками, а отношения между ними отрезками
или дугами.

5.

Граф

6.

Граф

7.

Граф

8.

Лемма о рукопожатии
■ Лемма (греч. λημμα — предположение) — доказанное
утверждение, полезное не само по себе, а для
доказательства других утверждений.

9.

Пример

10.

Задание 1

11.

Задание 2

12.

Задание 3

13.

Задание 4

14.

Задание 5
Известно, что в графе все степени вершин равны,
самих вершин 24, а ребер – 60. Чему равна степень
любой вершины этого графа?

15.

Задание 6

16.

Задание 7