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

Решение задачс помощью графов Выполнила ученица 7-Б классаМОУ СОШ № 9Им. В.Т. СтепанченкоИванова Мария2008 год

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

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

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

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

Граф-дерево

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

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

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

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

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

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

Благодарю за внимание!