Что называется степенью вершины графа
Степень вершины (теория графов)
Содержание
Лемма о рукопожатиях
По формуле суммы степеней для графа 
,
то есть сумма степеней вершин любого графа равна удвоенному числу его рёбер. Кроме того, формула утверждает, что в любом графе число вершин нечётной степени чётно. Данное утверждение (и сама формула) известны как лемма о рукопожатиях. Название происходит от известной математической задачи: необходимо доказать, что в любой группе число людей, пожавших руку нечётному числу других чётно.
Последовательность степеней вершин
Последовательность степеней вершин неориентированного графа является невозрастающей последовательностью. [2] Для графа, изображённого на рис. 1, она имеет вид (5, 3, 3, 2, 2, 1, 0). Последовательность степеней вершин есть инвариант графа, поэтому у изоморфных графов она одинакова. Однако последовательность степеней вершин не является уникальной характеристкой графа: в некоторых случаях неизоморфные графы также обладают одинаковой последовательностью.
Проблема последовательности степеней заключается в нахождении некоторых или всех графов с заданной невозрастающей последовательностью, состоящей из натуральных чисел (нулевые степени при этом могут быть проигнорированы, так как их количество изменяется добавлением или удалением изолированных вершин). Последовательность, являющаяся последовательностью степеней какого-либо графа, называется графической (англ. graphical sequence ). Из формулы суммы степеней следует, что любая последовательность с нечётной суммой (как, к примеру, 3, 3, 1) не может быть последовательностью степеней графа. Обратное также верно: если последовательность имеет чётную сумму, она представляет собой последовательность степеней мультиграфа. Построение такого графа осуществляется достаточно простым способом: необходимо объединить вершины нечётных степеней в пары, к оставшимся незаполненными вершинам следует добавить петли.
Сложнее реализовать простой граф с заданной последовательностью. Теорема Эрдёша — Галлаи утверждает, что невозрастающая последовательность di (при i = 1,…,n) может быть последовательностью простого графа только если её сумма чётна и выполняется неравенство
Например, последовательность (3, 3, 3, 1) не может являться последовательностью простого графа; она удовлетворяет неравенству Эрдёша — Галлаи только при k равном 1, 2 или 4, но не при k равном 3.
С. Л. Хакими доказал, что (d1, d2, …, dn) есть последовательность степеней простого графа только если существует (d2 − 1, d3 − 1, …, dd1+1 − 1, dd1+2, dd1+3, …, dn). Этот факт позволил разработать простой алгоритм нахождения простого графа с заданной реализуемой последовательностью:
Проблема нахождения или оценки числа графов по заданной последовательности относится к области перечисления графов.
Частные значения
Общие свойства
См. также
Примечания
Источники
Полезное
Смотреть что такое «Степень вершины (теория графов)» в других словарях:
Дуга (теория графов) — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
Цикл (теория графов) — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
Дерево (теория графов) — У этого термина существуют и другие значения, см. Дерево (значения). Дерево это связный ациклический граф.[1] Связность означает наличие путей между любой парой вершин, ацикличность отсутствие циклов и то, что между парами вершин… … Википедия
Графов теория — раздел конечной математики (См. Конечная математика), особенностью которого является геометрический подход к изучению объектов. Основное понятие теории граф. Граф задаётся множеством вершин (точек) и множеством рёбер (связей), соединяющих … Большая советская энциклопедия
Глоссарий теории графов — Эта страница глоссарий. См. также основную статью: Теория графов Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице) … Википедия
Словарь терминов теории графов — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И К Л М Н О П Р С … Википедия
Практическое применение раскраски графов — Эту статью следует викифицировать. Пожалуйста, оформите её согласно правилам оформления статей. Раскраска графов практически применяется (постановку задачи различиных раскрасок здесь обсуждаться не будет) дл … Википедия
Теоремы теории графов — Здесь собраны теоремы из теории графов. Содержание 1 Лемма о рукопожатиях 2 Существование эйлерова пути и цикла … Википедия
Вершина (граф) — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
Длина пути в орграфе — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
Теория графов — основы
График — это диаграмма точек и линий, соединенных с точками. У него есть по крайней мере одна линия, соединяющая набор из двух вершин без вершин, соединяющих себя. Понятие графов в теории графов опирается на некоторые основные термины, такие как точка, линия, вершина, ребро, степень вершин, свойства графов и т. Д. Здесь, в этой главе, мы рассмотрим эти основы теории графов.
точка
Точка — это конкретная позиция в одномерном, двухмерном или трехмерном пространстве. Для лучшего понимания точку можно обозначить алфавитом. Его можно обозначить точкой.
пример
Здесь точка — это точка с именем «а».
Линия
Линия — это связь между двумя точками. Это может быть представлено сплошной линией.
пример
Здесь «а» и «б» являются точками. Связь между этими двумя точками называется линией.
пример
Здесь вершина названа с алфавитом «а».
Ребро — это математический термин для линии, соединяющей две вершины. Многие ребра могут быть сформированы из одной вершины. Без вершины ребро не может быть сформировано. Для ребра должна быть начальная и конечная вершина.
пример
Здесь «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
Посмотрите на следующий график —
На приведенном выше неориентированном графике
deg (a) = 2, поскольку в вершине ‘a’ встречаются 2 ребра.
deg (b) = 3, поскольку в вершине ‘b’ встречаются 3 ребра.
deg (c) = 1, поскольку в вершине ‘c’ сформировано 1 ребро
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 ребро
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 |
На приведенном выше графике для вершин
Теория Графов. Часть 1 Введение и классификация графов
«Графы являются одним из объединяющих понятий информатики – абстрактное представление, которое описывает организацию транспортных систем, взаимодействие между людьми и телекоммуникационные сети. То, что с помощью одного формального представления можно смоделировать так много различных структур, является источником огромной силы для образованного программиста». Стивен С. Скиена
Введение
Сначала под землей города Москвы ничего не было. Потом была построена первая станция метро, а затем и вторая и третья. Образовалось множество станций метро. На карту было занесено множество точек. Позже между станциями стали прокладывать пути линии. И соединилась станция метро А со станцией метро Б. Все остальные станции также стали соединятся друг с другом и на карте появилось множество линий. В итоге мы имеем Московский метрополитен очень красивый, я там был проверял.
Схема Московского метро
Посмотрите какая красота. У нас имеется множество точек (которые называются вершинами или узлами), а также множество линий (называемые рёбрами или дугами). Обозначим множество вершин буквой V от английского vertex−вершина и множество рёбер обозначим E от английского edge−ребро. Граф в формулах именуют буквой G. Все вершины обязательно должны быть идентифицированы.
Отмечу, что число вершин обозначается буквой n:
Число рёбер обозначается буквой m:
Таким образом граф задается и обозначается парой V,E:
Также определение графа рассказывается в этой статье на Хабре (https://habr.com/ru/post/65367/)
Неформально граф является совокупностью точек и линий. Линии в котором задаются парой вершин, расположенных не важно в каком порядке.
Разберем определение графа подробней. Может ли в G быть пустым множество E? Да без проблем! Такой граф будет называться нулевым, а вершины в нем будут называться изолированными.
Нулевой граф
Только вот множество V вершины пустым быть не может. Ведь множество E рёбра задается парой неупорядоченных вершин множества V. Две вершины образующие ребро, называются концами этого ребра.
Множество E задается парой неупорядоченных вершин множества V.
Пример: Пусть множество V = <1,2,3,4,5>. Тогда множество E =
Граф будет выглядеть следующим образом:
Висячей вершиной называется вершина которая соединена только с одной соседней вершиной. В нашем случаи висячей вершиной будет вершина 5, так как она соединена только с вершиной 1.
Степень записывают, как:
Максимальная степень, то есть какое количество степеней вообще присутствуют в графе обозначаются, как:
Формула суммы степеней для G = V,E выглядит так:
То есть сумма степеней всех вершин v графа равна удвоенному количеству его рёбер E. Считаем количество степеней в нашем примере. От этого никуда не денешься. Я насчитал 12. А теперь считаем, сколько у нас рёбер. Их 6! Умножаем на 2 и получаем 12. Совпадение? Не думаю!
А давайте представим наш граф в другом виде, но с сохранением данных пар. G теперь имеет следующий вид:
Заметьте я не изменил пары между собой. Вершина 4 также соединяется с вершиной 3, а у вершины 1 степень также осталась 4. Так почему граф имеет совершенно другой вид и законно ли это?
Классификации графов
Первым признаком классификации является отсутствие или наличие ориентации у ребер.
Ребро является неориентированным если у него нет понятия начала или конца. То есть оба его конца равноправны. Такой граф называется неориентированным, обыкновенным или неографом.
Неориентированный граф
Ориентированное ребро обозначается стрелкой. И указывает ориентацию от вершины к вершине. То есть данный граф имеет начало и конец. И называется он ориентированным или орграфом.
Ориентированный граф
Также существует граф со смешанными ребрами. Это когда в графе присутствуют, как ориентированные рёбра, так и неориентированные.
Смешанный граф
Вторым признаком является отсутствие или наличие кратных ребер.
Мультиграф
Граф в котором кратных ребер нет, является простым графом. В простом графе мы просто называем пару вершин для идентификации ребра, но в мультиграфе такое уже не сработает, так как одна и та же пара вершин будет указывать на два ребра и не понятно что к чему будет относится. Поэтому если вы повстречаете мультиграф, то вы должны обозначить каждое ребро отдельно.
Заключение
В данной стать я не рассмотрел, понятия смежности и инцидентности, однако я решил их рассмотреть в следующий раз. Также хочу отметить, что более подробно виды графов, я буду рассматривать в следующих статьях. Если у вас есть вопросы, предложения или я где-то допустил ошибки, то прошу написать их в комментариях.