Презентация: Степень (валентность) вершины. Число рёбер и суммарная степень вершин

• 1 слайд

  Степень (валентность) вершины.
  Число рёбер и суммарная степень вершин.
  

• 2 слайд

  Повторение
  Что называется графом?
  Что называется вершиной графа?
  Что нарывается ребром графа?
  

• 3 слайд

  Проверка домашнего задания
  1. Андрей, Борис, Виктор и Григорий играли в шахматы. Каждый сыграл с каждым по одной партии. Сколько партий было сыграно?
  А
  Б
  В
  Г
  Ответ: 6 партий
  

• 4 слайд

  2. Андрей, Борис, Виктор и Григорий подарили на память друг другу свои фотографии. Причём каждый мальчик подарил каждому по одной фотографии. Сколько всего фотографий было подарено?
  А
  Б
  В
  Г
  Ответ: 12 фотографий
  Проверка домашнего задания
  

• 5 слайд

  3.На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?
  Ответ: 8
  Проверка домашнего задания
  

• 6 слайд

  4. Между девятью планетами Солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам: Земля — Меркурий, Плутон — Венера, Земля — Плутон, Плутон — Меркурий, Меркурий — Венера, Уран — Нептун, Нептун — Сатурн, Сатурн — Юпитер, Юпитер — Марс и Марс — Уран. По каждому маршруту ракеты летают в обе стороны. Можно ли долететь на рейсовых ракетах от Земли до Марса?
  Ответ: нельзя
  Проверка домашнего задания
  

• 7 слайд

  
  Что называется степенью графа?
  
  В каком случае вершина называется четной? Нечетной?
  Степень (валентность) вершины графа
  

• 8 слайд

  Количество рёбер графа – равно сумме степеней всех его вершин, делённой на 2.
  A
  B
  C
  D
  E
  F
  (1+3+2+2+3+1):2=6
  1
  3
  2
  2
  3
  1
  Пример:
  

• 9 слайд

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

• 10 слайд

  Решение.
  Пусть х – число городов.
  Число дорог:
  (3х)/2 или 100 дорог.
  (3х)/2 = 100
  3х=200
  х = 200/3
  Число городов может быть только натуральном, значит 100 дорог в таком государстве быть не может.
  Ответ: не может.
  2. Может ли в государстве, в котором из каждого города выходит ровно 3 дороги, быть ровно 100 дорог?
  

• 11 слайд

  Теорема. Сумма степеней всех вершин графа равна удвоенному числу ребер этого графа.
  2+3+3+2+2+3+3+2 12·2
  24 24
  =
  =
  

• 12 слайд

  3. В графе 12 рёбер, а каждая вершина имеет индекс 3. Сколько у него вершин? Нарисуйте такой граф.
  12·2=24 – сумма степеней всех вершин
  24:3=8 – вершин
  Ответ: 8 вершин.
  

• 13 слайд

  Следствие . Сумма степеней всех вершин графа - четное число
  4. В классе 15 компьютеров. Можно ли их соединить друг с другом так, чтобы каждый компьютер был соединен ровно с пятью другими?
  15·5=75 – сумма степеней всех вершин
  Ответ: невозможно.
  

• 14 слайд

  Следствие . Число вершин с нечетным индексом четно.
  5. Может ли граф иметь пять вершин, в каждой из которых сходится три ребра?
  Ответ: Нет. Число вершин с нечетным индексом должно быть четным.
  6. В классе 30 человек. Может ли быть так, что 9 человек имеют по 3 друга, 11 – по 4 друга, а 10 – по 5 друзей ?
  Ответ: Нет. Число вершин с нечетным индексом должно быть четным (9 человек – 3 друга).