Презентация на тему "Граф, вершина, ребро. Степень вершины. Число рёбер и суммарная степень вершин" 8 класс

Содержание

• 
  Слайд 1
  

  Граф, вершина, ребро. Степень вершины. Число рёбер и суммарная степень вершин.Учитель : Коваленко Ирина Анатольевна

• 
  Слайд 2

  Задача 1.

  В деревне 9 домов. Известно, что у Петра соседи Иван и Антон, Максим сосед Ивану и Сергею, Виктор – Диме и Никите, Евгений – сосед Никиты, а больше соседей в этой деревне нет (соседними считаются дворы, у которых есть общий участок забора). Может ли Пётр огородами пробраться к Никите за яблоками?

• 
  Слайд 3
  

  Решение. Нарисуем схему: точками обозначим дома и соединим непересекающимися между собой линиями только те из них, которые являются соседними (см. рис. 1). Теперь видно, что пробраться огородами из дома Петра к дому Никиты нельзя.

• 
  Слайд 4

  Задача 2.

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

• 
  Слайд 5
  

  Решение. Заметим, что диагонали пятиугольника образуют один замкнутый цикл. Представим себе, что фишки – это пуговицы, нанизанные на нитку (см. рис. 2в). Ясно, что если двигать пуговицы по нитке, то поменять местами две пуговицы нельзя. Поэтому переставить фишки требуемым образом невозможно.

• 
  Слайд 6
  

  Определение 1. Графом называется конечное множество точек, некоторые из которых соединены линями. Точки называются вершинами графа, а соединяющие линии – рёбрами. Примерами графов могут служить: любая карта дорог, схема метро, электросхема, чертёж прямоугольника и т.д.

• 
  Слайд 7

  Замечания:

  1. Каждое ребро соединяет ровно две вершины. 2. Вершины, из которых не исходит ни одного ребра, называются изолированными. 3. Графы, у которых вершина соединена сама с собой, и графы, в которых пара вершин соединена несколькими рёбрами, мы пока не рассматриваем, хотя иногда такие графы также бывают нужны. 4. Полезно представить граф как набор пуговиц, некоторые из которых соединены нитями. При этом, где именно расположены пуговицы, и как проходят нити – не важно: граф от этого не меняется, важно лишь то, какие пары пуговиц (вершины) соединены нитями.

• 
  Слайд 8
  

  Такие одинаковые, но, быть может, по-разному нарисованные графы принято называть изоморфными. На рисунках 3а и 3б изображены изоморфные графы.

• 
  Слайд 9
  

  Определение 2.  Степенью (или порядком) вершины называется количество рёбер, исходящих из этой вершины. Вершина называется чётной, если из неё выходит чётное число рёбер, и нечётной, если из неё выходит нечётное число рёбер.

• 
  Слайд 10
  

  Например, в графе, изображенном на рисунке 3, первая и пятая вершины имеют степень 1, вторая вершина – степень 4, третья и четвертая вершины – степень 2.

• 
  Слайд 11

  Задача 3

  В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединён с пятью другими?

• 
  Слайд 12
  
• 
  Слайд 13

  Замечания:

  5. Чтобы подсчитать число рёбер графа нужно просуммировать степени вершин и полученный результат разделить на два. 6. Сумма степеней всех вершин графа должна быть чётной (иначе её нельзя было бы разделить на два нацело).

• 
  Слайд 14

  Например:

• 
  Слайд 15

  Задача 4

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

• 
  Слайд 16

  Задание: Сколько ребер и вершин в данном графе?