0: Добрый день, меня зовут Коваленко Ирина Анатольевна, я учитель средней общеобразовательной школы города Белгорода. И сегодня я хочу вас познакомить с темой граф вершина ребро.

1: Степень вершины, число рёбер и суммарная степень вершин.

2: Рассмотрим следующую задачу. Почему-то оно перескочило. Вот она. Рассмотрим следующую задачу. В деревне 9 домов. Известно, что у петра соседи, Иван.

3: И Антон, Максим, сосед Ивану и Сергею, Виктор Диме и никите, Евгений сосед никиты, а больше соседей в этой деревне нет, соседними считают.

4: Дворы, у которых есть общий участок забора, может ли Пётр огородами пробраться к никите за яблоками?

5: Нарисуем схему точками мы обозначим дома и соединим их не пересекающимися между собой линиями. Только те из них, которые являются соседними. Вот.

6: Смотрите, вот Пётр, соседи, Иван и Антон, вот Максим, соседи, Иван и Сергей и здесь, соответственно, соседи Никита, у него соседи под буквой, в под буквой.

7: Может ли пробраться огородами?

8: Пётр к никите. Ну, конечно, нет, потому что они не являются соседними. Следующая задача в 3 вершинах пятиугольника расположили по фишке. Вот рисунок, смотрите, 1.

9: Вершина, 2 вершина, 3 вершина разрешается двигать их по диагонали в свободную вершину, то есть 1 можно двигать в 3 можно двигать вот сюда по диагонали, 2 совер.

10: Совершенно. Вот по диагонали. Смотрите, диагональ это звёздочка, это диагональ. Можно ли такими действиями добиться того, что 1 из фишек вернулась на первоначальное место, a2 другие поменялись?

11: Местами. Ну то есть, смотрите, 2 и 3, предположим, в процессе движения поменялись местами, a1 вернулась на своё место.

12: Диагонали пятиугольника образуют замкнутый цикл, замкнутый. Представим себе, что фишки это пуговицы вот смотрите пуговицы на нитке. Ясно, что если двигать пуговиц

13: По нитке то поменять местами 2 пуговицы нельзя, поэтому переставить фишки требуемым образом невозможно решение этих задач объединяет.

14: Общая идея, графическое изображение, условия картинки очень похожи, это точки, некоторые из них соединены линиями.

15: Определение 1 графом называется конечное множество точек, некоторые из которых соединены линиями точки, называются вершинами графа.

16: А соединяющие линии рёбрами, примерами Графов может служить любая карта дорог, схема метро, электросхемы, чертёж прямоугольника и так далее.

17: Каждое ребро соединяет только 2 вершины вершины, из которых не исходит ни 1 ребро, называют изолированными графы, у которых вершина соеди.

18: Nena сама с собой. И графы, в которых пары вершин соединены несколькими рёбрами, мы пока не рассматриваем, хотя иногда такие графы бывают нужны. Полезно представить, граф как набор пуговиц.

19: Некоторые из которых соединены нитями, при этом, где именно расположены пуговицы и как проходят нити, неважно.

20: Граф от этого не меняется, важно лишь то, какие пары пуговиц или вершины соединены нитями, такие одинаковые, но, может быть, пора.

21: Разному нарисованные графы принято называть изоморфными. На рисунке 3, а изображены такие изоморфные графы. Вот посмотрите, из

22: 3 вершины исходят 2 ребра из 4 вершины тоже исходят, 2 ребра из 2 вершины исходят.

23: 1, 2, 3, 4 ребра тоже самое здесь, когда немножко поменяли.

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

25: Выходит чётное число рёбер и нечётной. Если из неё выходит нечётное число рёбер. И опять вернёмся к нашим изображениям. Итак, смотрите, вершина 3 из

26: Неё исходит 2 ребра. Она чётная вершина. 4 тоже исходит 2 ребра. Она тоже чётная вершина. 2 исходит. 1, 2, 3.

27: 4 ребра, она чётная вершина. 5 исходит 1 ребро. Она нечётная степень вершины 3 равна 2, потому

28: Потому что из неё исходит 2 ребра степень вершины 2 равна 4, потому что из неё выходят 4.

29: Ребра.

30: A1 и 5 исходят по 1 ребру значит, степень имеют единица, ещё раз повторили, значит, степень вершины.

31: Это сколько рёбер выходят из этой вершины? Если выходит чётное количество рёбер, то вершина чётная считается если нечётная, то нечётной в

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

33: Вопрос, мы делаем предположение, пусть это возможно, теперь рассмотрим граф вершинами, которому соответствуют телефонами, а ребра соединяющими их провода.

34: В этом графе 15 вершин, так как 15 телефонов, степень каждой из которых равна 5, так как выходит 5, посчитаем количество рёбер в этом графе для этого сначала.

35: Просуммируем степень всех вершин раз из каждой вершины выходит 5 рёбер, значит, степень каждой вершины равна 5, а вершин всего 15, значит 15.

36: Умножить на 5. Это число рёбер данного графа, и каждое ребро учтено дважды. Следовательно, разделим на 2, если

37: 15 умножим на 5, будет 75 разделим на 2 получается не целое число, а значит, такого графа не существует. Следовательно, соединить телефоны требуемым образом не

38: Возможно ещё замечание, чтобы посчитать число рёбер, графа нужно просуммировать степени вершин и полученный результат разделить на 2. Ну то есть то, что

39: Мы сейчас с вами делали сумма степеней всех вершин графа должна быть чётной, иначе её нельзя было бы разделить на 2 нацело.

40: Ну, например, посмотрите, у этого графа 7 рёбер, они данные ребра, обозначены цифрами 1 2. Нет, цифрами обозначены. Степень каждого.

41: Каждой вершины. Итак, 1. Вот вершина, из неё выходит 1 ребро. Значит, степень равна единице. Вот вершина. Из неё выходит 2 ребра. Значит, степень равна 2. Следующая вершина.

42: Опять исходит 2 ребра. Значит, степень равна 2. В данном случае степень вершины равна 3 исходит 3 ребра. Вот этой вершины. Степень равна 2 и после.

43: Степень равна 4, из неё выходит 4 ребра, всего 7 рёбер, а суммарная степень вершин составляет 2 + 1 плюс.

44: 3 равна 14. То есть сложили все.

45: И получили 14 рёбер 7. Смотрите, 1, 2, 3, 4, 5, 6, 7. А степень вершин 14. Задача в классе 3.

46: Человек. Может ли быть так, что 9 из них имеют по 3 друга в этом классе 11 по 4 друга, а 10 по 5 друзей, если

47: Если бы это было возможно, то можно было бы нарисовать граф с 30 вершинами 30 человек, 30 вершин, 9 из которых имели бы степень 3 11, степень 4.

48: 10 степень.

49: 5 однако сумма степеней такого граффа смотрите, 3 + 4, 7, прибавить 5.

50: Получа. Ага. Ещё прибавить. 9 получается нечётной, что противоречит замечанию. Значит, так сделать невозможно, чтобы 9 из них

51: Имели по 3 друга, остальные имели по 4 друга 11, а 10 по 5 друзей. Задание вам посчитать, сколько реб?

52: И вершин в данном графе. Ну, напоминаю, ребра это вот эти соединённые отрезки. 1, 2, 3, че.

53: 4, 5. А степень вершин показывает, сколько из этой вершины исходит рёбер. Из вершины ц исходит 1 ребро, значит.

54: Единичка из a2 ребра, 1 + 2. Это 3 из д, 3 ребра, 3 + 3. Это 6 ф, 2 ребра.

55: То есть 6 + 2 это 8 и из б тоже 2 ребра. Значит, степень вершин равна 10. A2, посчитайте.