Графы в нашем городе

1.

МБОУ технический лицей №176 Карасукского
района Новосибирской области
Проект по теме
«Графы в нашем городе»
ВЫПОЛНИЛИ: УЧЕНИКИ 10Л КЛАССА
ЗЕМЛЯНАЯ ВАЛЕРИЯ
БРУЙ АНАСТАСИЯ
БЛОХИНА ЮЛИЯ
АСТАФЬЕВ ЯРОСЛАВ
БАТЫРЕВ КИРИЛЛ
АРЕЩЕНКО ЕГОР
БУЛАТОВ ДМИТРИЙ
ЖИЛИН СЕРГЕЙ
РУКОВОДИТЕЛЬ: КУРЧЕНКО МАРИНА
ВЛАДИМИРОВНА

2.

Выяснить, какое наибольшее число дорог
можно перекрыть в нашем городе, чтобы
из любого пункта можно было проехать в
любой

3.

Задачи:
*Изучить карту города
*Построить граф, опираясь на карту
*Перевести задачу на язык графов
*Решить задачу опираясь, на теорию
графов

4.

Карта города Карасука

5.

Граф- конечное множество точек,
некоторые из которых соединены линиями.

6.

Граф, ребра которого- дороги, вершины –
пересечения и концы дорог

7.

8.

Количество вершин в графе: 355
Сумма степеней вершин в графе: 1022
Теорема: сумма степеней всех вершин
графа равна удвоенному числу его
ребер.
Количество ребер в графе: 511

9.

Дерево-это связный граф без циклов.
Свойство дерева: в дереве количество ребер на одно
меньше количества вершин.
Получили: 354 (минимальное количество ребер,
которое должно быть, чтобы граф остался связным).
511-354=157 – количество ребер которое можно убрать.
Одну дорогу мы не смогли убрать, так как по ул.
Луначарской одностороннее движение: 157-1=156

10.

Дерево, полученное из графа, путем
удаления 156 ребер

11.

цель достигнута