Исторические сведенияОсновы теории графов как математической науки заложил в 1736 году Леонард Эйлер. Первые задачи теории графов были связаны с решением математических развлекательных задач и головоломок.
Слайд 4
Задачи о Кёнигсбергских мостах. Рассмотрим знаменитую задачу о
Кёнигсбергских мостах.
Бывший Кёнигсберг (сейчас это город Калининград) расположен
на реке Прегель. В пределах города река омывает два острова.
С берегов на острова были перекинуты мосты. Жители города предлагали туристам следующую задачу: пройти по всем мостам и вернуться в начальный пункт, причём на каждом мосту нужно побывать только один раз.
Слайд 5
Задачи о Кёнигсбергских мостах. С берегов на острова
были перекинуты мосты. Жители города предлагали туристам следующую задачу:
пройти по всем мостам и вернуться в начальный пункт, причём на каждом мосту нужно побывать только один раз. Прогуляться по городским мостам предложили и Эйлеру. После безуспешной попытки совершить нужный обход он начертил упрощённую схему мостов.
Слайд 6
Головоломки «Не отрывая карандаша от бумаги и не
проводя дважды по одной линии, начертить фигуру». «Сабли Магомета»
«Распечатанное письмо»
Слайд 7
Графы с цветными рёбрами. Перейдём к рассмотрению графов,
в которых рёбра могут быть окрашены в несколько цветов.
Такой граф называется графом с цветными рёбрами. Так же будем рассматривать такие графы, у которых каждая пара вершин соединена ребром. Такие графы называются полными. Применение графов с цветными рёбрами упрощает решение некоторых задач и делает их более наглядными.
Слайд 8
Некоторые задачи. Шесть школьников участвуют в шахматном турнире,
который проводится в один круг. Доказать, что всегда среди
них найдутся три участника турнира, которые провели уже все встречи между собой, либо ещё не сыграли друг с другом ни одной партии.
Слайд 9
Некоторые задачи. 1) На географической карте
выбраны пять городов. Известно, что из любых трёх из
них найдутся два, соединённые авиалиниями, и два – не соединённые. Докажите, что:
1. Каждый город соединён авиалиниями с двумя и только с двумя
другими городами.
2. Вылетев из любого города, можно облететь пять остальных городов,
побывав в каждом по одному разу, и вернуться назад.
2) В офисе 15 компьютеров. Можно ли соединить их друг с другом так, чтобы каждый был соединен ровно с тремя другими? 3) В государстве 100 городов. Из каждого города выходит четыре дороги. Сколько всего дорог в государстве?