Решение задач с помощью графов

Графы – «графо» (лат.) – «пишу»
график
биография
голография

Задача.
1. Андрей
2. Борис
3. Виктор
4. Галина
5. Дмитрий
6. Елена
А
Б
Г
Е
А
Г
В
Г
Д
Е
Б
В
А
Е

Граф
А, Б, В, Г, Д, Е - вершины
АБ, АГ, АЕ, ВЕ, ВД, ВГ - рёбра

Сколько осталось провести игр?
Ответ: 8 (по числу рёбер)

Граф-дерево

Примеры графов

Примеры графов
Схема городской
телефонной сети
Структура алмаза

Первая работа по теории графов появилась в 1736 году в публикациях Петербургской Академии наук

Задача о соревнованиях
В школе проводятся соревнования по плаванию. Болельщики высказывают следующие предположения о будущих победителях:

Ваня: Наташа будет первой, а Вера- второй.
Серёжа: Первой будет Света,
а Люда займет третье место.
Дима: Света будет второй, Вера может
рассчитывать лишь на третье место.
Кто из участниц занял первое, второе и третье место, если известно, что каждое место заняла одна из них, и все они были призёрами?

Решим задачу с помощью построения граф-дерева