Основы теории графов. Тема 4.1

1. РАЗДЕЛ 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ. Тема 4.1. Основы теории графов

«Так о великих вещах помогают
составить понятье
Малые вещи, пути намечая для их
постижения»
Лукреций
1. История теории графов
2. Основные понятия теории графов
3. Разновидности графов
4. Операции над графами
5. Матричные представления графов

2. 1. История теории графов

3.

4. 1. История теории графов

5. 1. История теории графов

6. 1. История теории графов

7. 1. История теории графов

В 1975 году преподавателем архитектуры
Будапешта Эрне Рубиком для развития
пространственного воображения у студентов
изобрел головоломку Кубик Рубика.
В 1859 г. английский математик Уильям
Гамильтон выпустил в продажу головоломку.
Она
представляла
собой
деревянный
додекаэдр (12-гранник), в вершинах которого
вбиты гвоздики. Каждая из 20 вершин была
помечена названием одного из крупных
городов мира – Дели, Брюссель и т.д.
Требовалось
найти
замкнутый
путь,
проходящий по ребрам додекаэдра и
позволяющий побывать в каждой его вершине
по одному разу. Путь следовало отмечать с
помощью шнура, зацепляя его за гвоздики.
Решить все эти задачи или доказать, что
они не имеют решений возможно с
помощью теории графов!

8.

9. 2. Основные понятия теории графов

Теория графов – раздел
дискретной
математики,
изучающий свойства графов.
В математической теории
графов и информатике граф –
это совокупность объектов со
связями между ними.
Понятие «граф» впервые
ввел в 1936 году венгерский
математик Денни Кёниг.

10.