Презентация на тему "Проектная работа по теме "Графы в нашем городе"." 10 класс

Содержание

• 
  Слайд 1

  Проект по теме «Графы в нашем городе»

  Выполнили: ученики 10Л класса Земляная Валерия Бруй Анастасия Блохина Юлия Астафьев Ярослав Батырев Кирилл Арещенко Егор Булатов Дмитрий Жилин Сергей Руководитель: Курченко Марина Владимировна МБОУ технический лицей №176 Карасукского района Новосибирской области

• 
  Слайд 2
  

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

• 
  Слайд 3

  Задачи:

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

• 
  Слайд 4

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

• 
  Слайд 5
  

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

• 
  Слайд 6
  

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

• 
  Слайд 7
  
• 
  Слайд 8
  

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

• 
  Слайд 9

  .

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

• 
  Слайд 10

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

• 
  Слайд 11

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