Графы

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

Что такое граф?

Связные и несвязные графы

Степени вершин графа A B C D A – 1 B – 3 C – 2 D – 2

Количество ребер графа A B C D EF ( ):2=6

Задача 1 Построить граф, сумма степеней вершин которого равна 10. Построить граф, у которого 2 вершины имеют степень 4, 1 вершина – степень 3, 1 вершина – степень 2, 3 вершины - степень 1.

Решения могут быть такими: 10:2=5 ребер

Задача 2 В государстве 100 городов, а из каждого города выходит 4 дороги. Сколько всего дорог в государстве? Может ли в государстве, в котором из каждого города выходит 3 дороги, быть ровно 100 дорог? X- число городов

Можно ли нарисовать фигуру одним росчерком, не отрывая карандаша от бумаги и не проводя по одной линии дважды?

Применение графов Карты дорог электросхемы

Применение графов Чертёж многоугольника Технические схемы

Леонард Эйлер ( ) Леонард Эйлер выдающийся математик, внёсший значительный вклад в развитие математики, а также механики, физики, астрономии, основоположник теории графов. Родился Эйлер в Швейцарии, но жил и работал в России, в Санкт- Петербурге.

Задача Эйлера Задача, для решения которой Эйлер впервые применил графы, - это задача о мостах Кенигсберга. В XVIII веке город Кенигсберг был расположен на берегах реки и двух островах. Различные части города были соединены семью мостами. Можно ли совершить прогулку, пройдя по каждому мосту ровно один раз?

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

Логическая задача Алексей, Борис, Виталий и Геннадий – друзья. Один из них –врач, другой – журналист, третий – тренер спортивной школы, четвертый – строитель. Журналист написал статьи об Алексее и Геннадие. Тренер и журналист вместе с Борисом ходили в поход. Алексей и Борис были на приеме у врача. У кого какая пофессия?

Логическая задача Алексей Борис Геннадий Виталий строитель тренер журналист врач

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

Генеалогическое дерево

Дополнительные задачи Можно ли организовать футбольный турнир девяти команд, чтобы каждая команда провела по четыре встречи? 9*4:2=18 да

Дополнительные задачи В графе из любой вершины выходит по 3 ребра. Может ли быть в нем 300 ребер? 300*2:3=200да