Похожие презентации:
Графы в нашем городе
1.
МБОУ технический лицей №176 Карасукскогорайона Новосибирской области
Проект по теме
«Графы в нашем городе»
ВЫПОЛНИЛИ: УЧЕНИКИ 10Л КЛАССА
ЗЕМЛЯНАЯ ВАЛЕРИЯ
БРУЙ АНАСТАСИЯ
БЛОХИНА ЮЛИЯ
АСТАФЬЕВ ЯРОСЛАВ
БАТЫРЕВ КИРИЛЛ
АРЕЩЕНКО ЕГОР
БУЛАТОВ ДМИТРИЙ
ЖИЛИН СЕРГЕЙ
РУКОВОДИТЕЛЬ: КУРЧЕНКО МАРИНА
ВЛАДИМИРОВНА
2.
Выяснить, какое наибольшее число дорогможно перекрыть в нашем городе, чтобы
из любого пункта можно было проехать в
любой
3.
Задачи:*Изучить карту города
*Построить граф, опираясь на карту
*Перевести задачу на язык графов
*Решить задачу опираясь, на теорию
графов
4.
Карта города Карасука5.
Граф- конечное множество точек,некоторые из которых соединены линиями.
6.
Граф, ребра которого- дороги, вершины –пересечения и концы дорог
7.
8.
Количество вершин в графе: 355Сумма степеней вершин в графе: 1022
Теорема: сумма степеней всех вершин
графа равна удвоенному числу его
ребер.
Количество ребер в графе: 511
9.
Дерево-это связный граф без циклов.Свойство дерева: в дереве количество ребер на одно
меньше количества вершин.
Получили: 354 (минимальное количество ребер,
которое должно быть, чтобы граф остался связным).
511-354=157 – количество ребер которое можно убрать.
Одну дорогу мы не смогли убрать, так как по ул.
Луначарской одностороннее движение: 157-1=156
10.
Дерево, полученное из графа, путемудаления 156 ребер