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

Содержание

• 
  Слайд 1
  

  Графы Степень вершины Подсчет числа ребер графа

• 
  Слайд 2
  

  Разминка… Вставьте недостающие слова в предложения (граф, титул, ребро, вершина) Всем известно, что слово «граф» означает дворянский титул, например, графЛев Николаевич Толстой. А вот в математике … Граф – это конечная совокупность вершин, некоторые из которых соединены ребрами.

• 
  Слайд 3
  

  Если пара вершин соединена несколькими ребрами, то говорят, что задан мультиграф, а ребра, соединяющие одну и ту же пару вершин, называют кратными. Вставьте недостающие слова в предложения ( мультиграф, кратный, вершина) Разминка…

• 
  Слайд 4
  

  Если ребро соединяет вершину саму с собой, то такое ребро называют ________. Если две вершины графа соединены ребром, то такие вершины называются смежными. Разминка… Вставьте недостающие слова в предложения ( смежный, петля)

• 
  Слайд 5
  

  В стране Знак есть 9 городов с названиями 1, 2, 3, 4, 5, 6, 7, 8, 9. Путешественник обнаружил, что два города соединены дорогой в том и только в том случае, если двузначное число, образованное названиями городов, делится на 3.

  Домашняя задачка Условие

• 
  Слайд 6
  

  Постройте граф, обозначив вершины графа цифрами (названия городов). Соедините ребрами те вершины, которые удовлетворяют условию задачи. Посчитайте количество ребер. Можно ли долететь по воздуху из города 1 в город 9 ? Домашняя задачка Задания

• 
  Слайд 7
  

  Поставим в соответствие каждому городу точку и соединим те точки линиями, сумма цифр которых делится на 3. Получим граф. Обратим внимание, что 3, 6, 9 связаны между собой, но не связаны с остальными. Число ребер: 12. Значит долететь из города 1 в город 9 нельзя. Домашняя задачка Решение

• 
  Слайд 8
  

  Количество ребер, выходящих из одной вершины, называют степенью этой вершины. Для петли будем считать, что это ребро выходит из вершины дважды. Степень вершины графа

• 
  Слайд 9
  

  Вершина, имеющая четную степень, называется четной вершиной, соответственно, вершина, имеющая нечетную степень, называется нечетной вершиной.

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

• 
  Слайд 10
  

  Количество ребер графа равно половине суммы степеней его вершин. Пусть граф имеет n вершин, тогда число ребер равно: Подсчет числа ребер графа

• 
  Слайд 11
  

  Рассмотрим утверждение о количестве ребер на примере: Задача: в государстве 100 городов, из каждого выходит 2 дороги, кроме столицы, откуда выходит 6 дорог. Сколько всего дорог в государстве? Решение: сложим количества дорог, выходящих из всех городов: 99*2+6=204. Это число - количество концов всех дорог. Поскольку каждая дорога имеет 2 конца, то количество дорог будет вдвое меньше, а именно 102. Подсчет числа ребер графа

• 
  Слайд 12

  Теорема. Количество вершин нечетной степени любого графа всегда четно.

  Степень вершины графа Доказательство: Количество ребер графа равно половине суммы степеней его вершин. Так как количество ребер должно быть целым числом, то сумма степеней вершин должна быть четной. А это возможно только в том случае, если граф содержит четное число нечетных вершин.

• 
  Слайд 13
  

  Домашнее задание У короля 19 вассалов. Может ли оказаться так, что у каждого вассала 1, 5 или 9 соседей ? Может ли в государстве, в котором из каждого города выходит ровно 3 дороги, быть ровно 100 дорог? Докажите, что число людей, живших когда-либо на Земле и сделавших нечетное число рукопожатий, четно.