Степень вершины (теория графов)
Степень вершины (англ. degree , также валентность, англ. valency ) в теории графов — количество рёбер графа 
, инцидентных вершине 
. При подсчёте степени ребро-петля учитывается дважды. [1] Степень вершины обозначается как 
(в западных источниках — 
). Максимальная и минимальная степень вершин графа G обозначаются соответственно Δ(G) и δ(G). На рис. 1 максимальная степень равна 5, минимальная — 0. В регулярном графе степени всех вершин одинаковы, поэтому в данном случае можно говорить о степени графа.
Содержание
Лемма о рукопожатиях
По формуле суммы степеней для графа ,
Последовательность степеней вершин неориентированного графа является невозрастающей последовательностью. [2] Для графа, изображённого на рис. 1, она имеет вид (5, 3, 3, 2, 2, 1, 0). Последовательность степеней вершин есть инвариант графа, поэтому у изоморфных графов она одинакова. Однако последовательность степеней вершин не является уникальной характеристкой графа: в некоторых случаях неизоморфные графы также обладают одинаковой последовательностью.
Проблема последовательности степеней заключается в нахождении некоторых или всех графов с заданной невозрастающей последовательностью, состоящей из натуральных чисел (нулевые степени при этом могут быть проигнорированы, так как их количество изменяется добавлением или удалением изолированных вершин). Последовательность, являющаяся последовательностью степеней какого-либо графа, называется графической (англ. graphical sequence ). Из формулы суммы степеней следует, что любая последовательность с нечётной суммой (как, к примеру, 3, 3, 1) не может быть последовательностью степеней графа. Обратное также верно: если последовательность имеет чётную сумму, она представляет собой последовательность степеней мультиграфа. Построение такого графа осуществляется достаточно простым способом: необходимо объединить вершины нечётных степеней в пары, к оставшимся незаполненными вершинам следует добавить петли.
Сложнее реализовать простой граф с заданной последовательностью. Теорема Эрдёша — Галлаи утверждает, что невозрастающая последовательность di (при i = 1,…,n) может быть последовательностью простого графа только если её сумма чётна и выполняется неравенство
Здесь точка – это точка с именем «а».
Линия
Линия – это связь между двумя точками. Это может быть представлено сплошной линией.
пример
Здесь «а» и «б» являются точками. Связь между этими двумя точками называется линией.
Вершина – это точка, где встречаются несколько линий. Это также называется узлом . Подобно точкам, вершина также обозначается алфавитом.
пример
Здесь вершина названа с алфавитом «а».
Ребро – это математический термин для линии, соединяющей две вершины. Многие ребра могут быть сформированы из одной вершины. Без вершины ребро не может быть сформировано. Для ребра должна быть начальная и конечная вершина.
пример
Здесь «a» и «b» – две вершины, и связь между ними называется ребром.
график
Граф ‘G’ определяется как G = (V, E), где V – множество всех вершин, а E – множество всех ребер графа.
Пример 1
В приведенном выше примере ab, ac, cd и bd являются ребрами графа. Аналогично, a, b, c и d являются вершинами графа.
Пример 2
В этом графе есть четыре вершины a, b, c и d и четыре ребра ab, ac, ad и cd.
петля
В графе, если ребро нарисовано от вершины к себе, это называется циклом.
Пример 1
На приведенном выше графике V – вершина, для которой у нее есть ребро (V, V), образующее петлю.
Пример 2
В этом графе есть две петли, которые сформированы в вершине a, и вершине b.
Степень вершины
Это число вершин, смежных с вершиной V.
Обозначение – град (V).
В простом графе с n числом вершин степень любых вершин равна –
Вершина может образовывать ребро со всеми остальными вершинами, кроме самой себя. Таким образом, степень вершины будет равна числу вершин в графе минус 1 . Это 1 для собственной вершины, поскольку она не может образовывать петлю сама по себе. Если в любой из вершин есть петля, то это не простой граф.
Степень вершины можно рассматривать по двум случаям графов –
- Ненаправленный граф
- Направленный граф
Степень вершины в неориентированном графе
Ненаправленный граф не имеет направленных ребер. Рассмотрим следующие примеры.
Пример 1
Посмотрите на следующий график –
На приведенном выше неориентированном графике
deg (a) = 2, поскольку в вершине ‘a’ встречаются 2 ребра.
deg (b) = 3, поскольку в вершине ‘b’ встречаются 3 ребра.
deg (c) = 1, поскольку в вершине ‘c’ сформировано 1 ребро
Итак, «c» – это вершина с кулоном .
deg (d) = 2, поскольку в вершине ‘d’ встречаются 2 ребра.
deg (e) = 0, так как в вершине ‘e’ есть 0 ребер.
Так что «е» – изолированная вершина .
deg (a) = 2, поскольку в вершине ‘a’ встречаются 2 ребра.
deg (b) = 3, поскольку в вершине ‘b’ встречаются 3 ребра.
deg (c) = 1, поскольку в вершине ‘c’ сформировано 1 ребро
Итак, «c» – это вершина с кулоном .
deg (d) = 2, поскольку в вершине ‘d’ встречаются 2 ребра.
deg (e) = 0, так как в вершине ‘e’ есть 0 ребер.
Так что «е» – изолированная вершина .
Пример 2
Посмотрите на следующий график –
На приведенном выше графике
deg (a) = 2, deg (b) = 2, deg (c) = 2, deg (d) = 2 и deg (e) = 0.
Вершина «е» является изолированной вершиной. Граф не имеет никакой вершины.
Степень вершины в ориентированном графе
В ориентированном графе каждая вершина имеет степень и степень.
Степень графа
Степень вершины V – это количество ребер, входящих в вершину V.
Обозначение – град – (V).
Степень вершины V – это количество ребер, входящих в вершину V.
Обозначение – град – (V).
Степень графа
Отступ вершины V – это число ребер, выходящих из вершины V.
Обозначение – град + (V).
Отступ вершины V – это число ребер, выходящих из вершины V.
Обозначение – град + (V).
Рассмотрим следующие примеры.
Пример 1
Посмотрите на следующий ориентированный граф. Вершина «а» имеет два ребра, «ad» и «ab», которые идут наружу. Следовательно, его степень равна 2. Аналогично, существует ребро «ga», идущее к вершине «a». Следовательно, степень «а» равна 1.
Степень и степень других вершин показаны в следующей таблице:
| темя | полустепень захода | полустепень |
|---|---|---|
| 1 | 2 | |
| б | 2 | 0 |
| с | 2 | 1 |
| d | 1 | 1 |
| е | 1 | 1 |
| е | 1 | 1 |
| г | 0 | 2 |
Пример 2
Посмотрите на следующий ориентированный граф. Вершина ‘a’ имеет ребро ‘ae’, идущее наружу от вершины ‘a’. Следовательно, его степень равна 1. Аналогично, у графа есть ребро «ba», приближающееся к вершине «a». Следовательно, степень «а» равна 1.
Степень и степень других вершин показаны в следующей таблице:
| темя | полустепень захода | полустепень |
|---|---|---|
| 1 | 1 | |
| б | 0 | 2 |
| с | 2 | 0 |
| d | 1 | 1 |
| е | 1 | 1 |
Кулон Вертекс
Используя степень вершины, мы получаем два специальных типа вершин. Вершина с первой степенью называется нерешенной вершиной.
пример
Здесь, в этом примере, вершина ‘a’ и вершина ‘b’ имеют соединенное ребро ‘ab’. Таким образом, что касается вершины «a», то к вершине «b» имеется только одно ребро, и аналогично по отношению к вершине «b» есть только одно ребро к вершине «a». Наконец, вершина ‘a’ и вершина ‘b’ имеют степень как единицу, которая также называется висячей вершиной.
Изолированная вершина
Вершина с нулевой степенью называется изолированной вершиной.
пример
Здесь вершина «a» и вершина «b» не имеют связи между собой, а также с любыми другими вершинами. Таким образом, степень обеих вершин ‘a’ и ‘b’ равна нулю. Они также называются изолированными вершинами.
смежность
Вот нормы смежности –
В графе две вершины называются смежными, если между двумя вершинами есть ребро. Здесь смежность вершин поддерживается одним ребром, соединяющим эти две вершины.
В графе два ребра называются смежными, если между двумя ребрами есть общая вершина. Здесь смежность ребер поддерживается единственной вершиной, соединяющей два ребра.
В графе две вершины называются смежными, если между двумя вершинами есть ребро. Здесь смежность вершин поддерживается одним ребром, соединяющим эти две вершины.
В графе два ребра называются смежными, если между двумя ребрами есть общая вершина. Здесь смежность ребер поддерживается единственной вершиной, соединяющей два ребра.
Пример 1
На приведенном выше графике –
«a» и «b» – это смежные вершины, так как между ними есть общее ребро «ab».
«a» и «d» являются смежными вершинами, так как между ними есть общее ребро «ad».
ab ‘и’ be ‘- смежные ребра, так как между ними есть общая вершина’ b ‘.
be ‘и’ de ‘- смежные ребра, так как между ними есть общая вершина’ e ‘.
«a» и «b» – это смежные вершины, так как между ними есть общее ребро «ab».
«a» и «d» являются смежными вершинами, так как между ними есть общее ребро «ad».
ab ‘и’ be ‘- смежные ребра, так как между ними есть общая вершина’ b ‘.
be ‘и’ de ‘- смежные ребра, так как между ними есть общая вершина’ e ‘.
Пример 2
На приведенном выше графике –
a ‘и’ d ‘являются смежными вершинами, так как между ними есть общее ребро’ ad ‘.
‘c’ и ‘b’ являются смежными вершинами, так как между ними есть общее ребро ‘cb’.
‘ad’ и ‘cd’ являются смежными ребрами, так как между ними есть общая вершина ‘d’.
ac ‘и’ cd ‘являются смежными ребрами, так как между ними есть общая вершина’ c ‘.
a ‘и’ d ‘являются смежными вершинами, так как между ними есть общее ребро’ ad ‘.
‘c’ и ‘b’ являются смежными вершинами, так как между ними есть общее ребро ‘cb’.
‘ad’ и ‘cd’ являются смежными ребрами, так как между ними есть общая вершина ‘d’.
ac ‘и’ cd ‘являются смежными ребрами, так как между ними есть общая вершина’ c ‘.
Параллельные края
В графе, если пара вершин соединена более чем одним ребром, то эти ребра называются параллельными ребрами.
На приведенном выше графике «a» и «b» – это две вершины, которые соединены между собой двумя ребрами «ab» и «ab». Так это называется параллельным ребром.
Мульти График
Граф, имеющий параллельные ребра, называется мультиграфом.
Пример 1
На приведенном выше графике есть пять ребер «ab», «ac», «cd», «cd» и «bd». Поскольку ‘c’ и ‘d’ имеют два параллельных ребра между ними, это мультиграф.
Пример 2
На приведенном выше графике вершины «b» и «c» имеют два ребра. Вершины ‘e’ и ‘d’ также имеют два ребра между ними. Следовательно, это мультиграф.
Степень последовательности графика
Если степени всех вершин в графе расположены в порядке убывания или возрастания, то полученная последовательность называется последовательностью графа графа.
Пример 1
| темя | б | с | d | е | |
|---|---|---|---|---|---|
| Присоединенный к | До нашей эры | объявление | объявление | с, Ь, е | d |
| степень | 2 | 2 | 2 | 3 | 1 |
На приведенном выше графике для вершин
Пример 2
| темя | б | с | d | е | е | |
|---|---|---|---|---|---|---|
| Присоединенный к | быть | а, с | б, г | с, е | объявление | – |
| степень | 2 | 2 | 2 | 2 | 2 | 0 |
На приведенном выше графике для вершин
"Степень вершины и подсчет числа ребер графа". 7-й класс
Назад Вперёд
Загрузить презентацию (487 кБ)
Профиль класса: общеобразовательный.
Тип урока: изучение и первичное закрепление новых знаний.
- ученик знает понятия графа и мультиграфа, знаком с понятиями “вершина графа” (смежные вершины) и “ребро графа” (кратные ребра и петли);
- умеет приводить примеры использования графов в различных учебных предметах и повседневной жизни.
- закрепить понятие графа, сформировать представление о степени вершины графа (четная, нечетная вершины), сформулировать определение о связности графа, рассмотреть утверждение о количестве ребер графа и теорему о четности числа нечетных вершин графа;
- отработать навыки использования теоретических знаний для решения новых задач.
- развивать логическое мышление учащихся, способность к рассуждению, внимательность;
- формировать умение представлять информацию в виде графов.
- воспитывать культуру общения на уроке, взаимоуважение.
- Организационный момент (приветствие класса, подготовка к уроку, проверка домашнего задания, включающая повторение материала предыдущего урока);
- Теоретический материал (знакомство с темой предстоящего урока, объяснение нового материала и краткая запись в рабочую тетрадь новых теоретических сведений по теме урока);
- Закрепление материала (решение задач);
- Итоги урока (краткий вывод и домашнее задание).
Давайте вспомним основные понятия теории графов. Для этого проведем разминку по типу незаконченного предложения (Презентация, сл.: 2, 3, 4). Каждый ученик имеет карточки с пропущенными словами в предложение. Учитель зачитывает предложение, останавливаясь перед пропущенным словом, и выбирает ученика, который в свою очередь должен поднять карточку. Далее этот ученик читает дальше предложение, также останавливаясь перед пропущенным словом, и уже сам выбирает одноклассника для ответа и т. д. по цепочке.
Проверим в классе решение домашней задачи (Презентация, сл.: 5, 6, 7). Один ученик выходит к доске и рисует граф. Далее мы вместе проверяем ребра (дороги между городами), считаем количество выходящих ребер из каждой вершины и смотрим связи между городами.
Сегодня на уроке мы продолжим изучение графов, познакомимся с понятием “степень вершины графа” и сформулируем определение связности графа (обратим внимание на наш граф из домашнего задания и определим, является ли он связным или нет и почему). Рассмотрим утверждение о количестве ребер графа, и проверим в соответствие с этим утверждением, правильно ли мы посчитали количество ребер графа в домашней задаче. И рассмотрим теорему о четности числа нечетных вершин графа.
Количество ребер, выходящих из одной вершины, называют степенью этой вершины. Для петли будем считать, что это ребро выходит из вершины дважды (Презентация, сл. 8).
Запишем определение в рабочую тетрадь и зарисуем представленный граф, для данного графа посчитаем степень каждой вершины. Ребята смотрят на слайд и работают самостоятельно, далее вслух зачитаем степень каждой вершины.
Вершина, имеющая четную степень, называется четной вершиной, соответственно, вершина, имеющая нечетную степень, называется нечетной вершиной (Презентация, сл. 9).
Запишем определение в тетрадь и перечислим через запятую сначала четные вершины, а потом нечетные вершины для уже нарисованного графа. Проверим задание вслух.
Количество ребер графа равно половине суммы степеней его вершин. Пусть граф имеет n вершин, тогда число ребер равно:
(Презентация, сл. 10)
Запишем утверждение в рабочую тетрадь и посчитаем количество ребер графа в домашней задачке. Проверим ответ в классе. Рассмотрим задачу и ее решение на подсчет числа ребер графа без построения. (Презентация, сл. 11).
Сформулируем теорему о количестве вершин нечетной степени любого графа и запишем формулировку в рабочую тетрадь. (Презентация, сл. 12).
Теорема. Количество вершин нечетной степени любого графа всегда четно.
Доказательство: Количество ребер графа равно половине суммы степеней его вершин.
Так как количество ребер должно быть целым числом, то сумма степеней вершин должна быть четной.
А это возможно только в том случае, если граф содержит четное число нечетных вершин.
Разберем доказательство и проверим теорему на нашей домашней задачке.
Рассмотрим несколько задач.
Задача. В государстве 50 городов, из каждого города выходит 4 дороги. Сколько всего дорог в государстве.
Решение. Подсчитаем общее количество выходящих дорог из городов: 50 * 4 = 200. Однако, мы понимаем, что при подсчете каждая дорога посчитана 2 раза – она выходит из одного города и входит в другой. Значит всего дорог в два раза меньше, т.е. 100.
Задача. В классе 30 человек. Может ли быть так, что 9 человек имеют по 3 друга, 11 – по 4 друга, а 10 – по 5 друзей?
Ответ. Нет (теорема о четности числа нечетных вершин).
Сегодня мы с вами познакомились с новыми определениями, связанными с понятием графа, рассмотрели утверждение, которое помогает быстро подсчитывать число ребер графа, и сформулировали теорему, которая значительно упрощает решение многих задач. В частности, поучительная сторона этой теоремы заключается в исследовании и ответе на вопрос, возможно или нет решение данной задачи, прежде чем приступать за ее решение.
В качестве домашнего задания ученики получать карточки с тремя задачами (Презентация, сл. 13).