Как найти наибольшую степень вершины графа - Сайт, где вы сможете решить свои вопросы

Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 28 июня 2021 года; проверки требуют 3 правки.

Рис. 1. Граф, на вершинах которого отмечены степени.

Степень (валентность) вершины графа — количество рёбер графа , инцидентных вершине .
При подсчёте степени ребро-петля учитывается дважды.^[1]

Степень вершины обычно обозначается как d(x) или deg(v) .
Максимальная и минимальная степень вершин графа G обозначаются соответственно Δ(G) и δ(G).
На рис. 1 максимальная степень равна 5, минимальная — 0.
В регулярном графе степени всех вершин одинаковы, поэтому в данном случае можно говорить о степени графа.

Лемма о рукопожатиях[править | править код]

По формуле суммы степеней для графа G=(V,E) ,

$sum _{{vin V}}deg(v)=2|E|,,$

то есть сумма степеней вершин любого графа равна удвоенному числу его рёбер. Кроме того, из формулы следует, что в любом графе число вершин нечётной степени чётно. Данное утверждение (и сама формула) известны как лемма о рукопожатиях. Название происходит от известной математической задачи: необходимо доказать, что в любой группе число людей, пожавших руку нечётному числу других, чётно.

Последовательность степеней вершин[править | править код]

Рис. 2. Два неизоморфных графа с одинаковой последовательностью степеней (3, 2, 2, 2, 2, 1, 1, 1).

Последовательность степеней вершин неориентированного графа является невозрастающей последовательностью.^[2] Для графа, изображённого на рис. 1, она имеет вид (5, 3, 3, 2, 2, 1, 0). Последовательность степеней вершин есть инвариант графа, поэтому у изоморфных графов она одинакова. Однако последовательность степеней вершин не является уникальной характеристикой графа: в некоторых случаях неизоморфные графы также обладают одинаковой последовательностью.

Проблема последовательности степеней заключается в нахождении некоторых или всех графов с заданной невозрастающей последовательностью, состоящей из натуральных чисел (нулевые степени при этом могут быть проигнорированы, так как их количество изменяется добавлением или удалением изолированных вершин). Последовательность, являющаяся последовательностью степеней какого-либо графа, называется графической (англ. graphical sequence). Из формулы суммы степеней следует, что любая последовательность с нечётной суммой (как, к примеру, 3, 3, 1) не может быть последовательностью степеней графа. Обратное также верно: если последовательность имеет чётную сумму, она представляет собой последовательность степеней мультиграфа. Построение такого графа осуществляется достаточно простым способом: необходимо объединить вершины нечётных степеней в пары, к оставшимся незаполненными вершинам следует добавить петли.

Сложнее реализовать простой граф с заданной последовательностью. Теорема Эрдёша — Галлаи утверждает, что невозрастающая последовательность d_i (при i = 1,…,n) может быть последовательностью простого графа только если её сумма чётна и выполняется неравенство

$sum _{{i=1}}^{{k}}d_{i}leq k(k-1)+sum _{{i=k+1}}^{n}min(d_{i},k)quad kin {1,dots ,n-1},.$

Например, последовательность (3, 3, 3, 1) не может являться последовательностью простого графа; она удовлетворяет неравенству Эрдёша — Галлаи только при k равном 1, но не при k равном 2 или 3.

Согласно критерию Гавела — Хакими, если невозрастающая последовательность (d₁, d₂, …, d_n) это последовательность степеней простого графа, то (d₂ − 1, d₃ − 1, …, d_d₁+1 − 1, d_d₁+2, d_d₁+3, …, d_n) некоторая последовательность степеней простого графа. Этот факт позволяет построить полиномиальный алгоритм нахождения простого графа с заданной реализуемой последовательностью.

Сопоставим исходной последовательности чисел вершины графа без ребер с требуемыми степенями. Указанное преобразование последовательностей задает как минимум одну вершину графа, все инцидентные ей ребра и множество вершин с новыми требуемыми дополнениями степеней. Упорядочивая оставшиеся вершины по невозрастанию дополнений степеней, получим невозрастающую последовательность степеней простого графа. Повторяя преобразование и упорядочение не более n-1 раза, получаем весь граф.

Проблема нахождения или оценки числа графов по заданной последовательности относится к области перечисления графов.

Частные значения[править | править код]

Рис. 3. Концевыми вершинами являются 4, 5, 6, 7, 10, 11 и 12.

Вершина степени 0 называется изолированной.
Вершина степени 1 называется концевой (англ. end vertex), висячей (англ. pendant vertex) или листом графа (англ. leaf vertex). Ребро, инцидентное такой вершине называется висячим (англ. terminal (pendant) edge, end-edge). На рис. 3 висячим ребром является {3,5}. Подобная терминология используется в изучении деревьев в общем и как структур данных.
Вершина степени n-1 графа порядка n называется доминирующей (англ. dominating vertex).

Общие свойства[править | править код]

Если все вершины графа имеют одинаковую степень k, граф называют k-регулярным или регулярным графом степени k. В этом случае сам граф имеет степень k.
Эйлеров путь существует в неориентированном, связном графе тогда и только тогда, когда граф имеет 0 или 2 вершины нечётной степени. Если граф содержит 0 вершин нечётной степени, Эйлеров путь является циклом.
Орграф является псевдолесом^{[неизвестный термин]} только если полустепень исхода каждой вершины не больше 1. Функциональный граф — частный случай псевдолеса, в котором полустепени исхода всех вершин равны 1.
Согласно теореме Брукса, хроматическое число любого графа за исключением клики или нечётного цикла не превышает максимальной степени его вершин (Δ). Согласно теореме Визинга, хроматический индекс любого графа не превышает Δ + 1.
k-вырожденным графом называется граф, в котором каждый подграф имеет вершину степенью не больше k.

См. также[править | править код]

Полустепень захода и полустепень исхода вершин ориентированных графов
Распределение степеней

Примечания[править | править код]

↑ Дистель, стр. 5
↑ Дистель, стр. 278

Источники[править | править код]

Дистель, Рейнхард (2005), Graph Theory (3rd ed.), Berlin, New York: Springer-Verlag, ISBN 978-3-540-26183-4, <http://diestel-graph-theory.com/index.html>.
Эрдёш, П. & Галлаи, T. (1960), Gráfok előírt fokszámú pontokkal, Matematikai Lapok Т. 11: 264—274, <http://www.renyi.hu/~p_erdos/1961-05.pdf>.
Хакими, С. Л. (1962), On realizability of a set of integers as degrees of the vertices of a linear graph. I, Journal of the Society for Industrial and Applied Mathematics Т. 10: 496–506.
Сирксма, Хирард & Хоохефен, Хан (1991), Seven criteria for integer sequences being graphic, Journal of Graph Theory Т. 15 (2): 223–231, DOI 10.1002/jgt.3190150209.

Источник

Степень вершины (теория графов)

Степень вершины (англ. degree , также валентность, англ. valency ) в теории графов — количество рёбер графа , инцидентных вершине . При подсчёте степени ребро-петля учитывается дважды. [1] Степень вершины обозначается как d(x) (в западных источниках — deg(v) ). Максимальная и минимальная степень вершин графа G обозначаются соответственно Δ(G) и δ(G). На рис. 1 максимальная степень равна 5, минимальная — 0. В регулярном графе степени всех вершин одинаковы, поэтому в данном случае можно говорить о степени графа.

Содержание

Лемма о рукопожатиях

По формуле суммы степеней для графа ,

Последовательность степеней вершин неориентированного графа является невозрастающей последовательностью. [2] Для графа, изображённого на рис. 1, она имеет вид (5, 3, 3, 2, 2, 1, 0). Последовательность степеней вершин есть инвариант графа, поэтому у изоморфных графов она одинакова. Однако последовательность степеней вершин не является уникальной характеристкой графа: в некоторых случаях неизоморфные графы также обладают одинаковой последовательностью.

Проблема последовательности степеней заключается в нахождении некоторых или всех графов с заданной невозрастающей последовательностью, состоящей из натуральных чисел (нулевые степени при этом могут быть проигнорированы, так как их количество изменяется добавлением или удалением изолированных вершин). Последовательность, являющаяся последовательностью степеней какого-либо графа, называется графической (англ. graphical sequence ). Из формулы суммы степеней следует, что любая последовательность с нечётной суммой (как, к примеру, 3, 3, 1) не может быть последовательностью степеней графа. Обратное также верно: если последовательность имеет чётную сумму, она представляет собой последовательность степеней мультиграфа. Построение такого графа осуществляется достаточно простым способом: необходимо объединить вершины нечётных степеней в пары, к оставшимся незаполненными вершинам следует добавить петли.

Здесь точка – это точка с именем «а».

Линия

Линия – это связь между двумя точками. Это может быть представлено сплошной линией.

пример

Здесь «а» и «б» являются точками. Связь между этими двумя точками называется линией.

Вершина – это точка, где встречаются несколько линий. Это также называется узлом . Подобно точкам, вершина также обозначается алфавитом.

пример

Здесь вершина названа с алфавитом «а».

Ребро – это математический термин для линии, соединяющей две вершины. Многие ребра могут быть сформированы из одной вершины. Без вершины ребро не может быть сформировано. Для ребра должна быть начальная и конечная вершина.

пример

Здесь «a» и «b» – две вершины, и связь между ними называется ребром.

график

Граф ‘G’ определяется как G = (V, E), где V – множество всех вершин, а E – множество всех ребер графа.

Пример 1

В приведенном выше примере ab, ac, cd и bd являются ребрами графа. Аналогично, a, b, c и d являются вершинами графа.

Пример 2

graph1

В этом графе есть четыре вершины 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).

Источник

Рис. 1. Граф, на вершинах которого отмечены степени.

Степень вершины (англ. degree, также валентность, англ. valency) в теории графов — количество рёбер графа , инцидентных вершине . При подсчёте степени ребро-петля учитывается дважды.^[1] Степень вершины обозначается как d(x) (в западных источниках — deg(v) ). Максимальная и минимальная степень вершин графа G обозначаются соответственно Δ(G) и δ(G). На рис. 1 максимальная степень равна 5, минимальная — 0. В регулярном графе степени всех вершин одинаковы, поэтому в данном случае можно говорить о степени графа.

Содержание

1 Лемма о рукопожатиях
2 Последовательность степеней вершин
3 Частные значения
4 Общие свойства
5 См. также
6 Примечания
7 Источники

Лемма о рукопожатиях

По формуле суммы степеней для графа ,

$sum_{v in V} deg(v) = 2|E|, ,$

то есть сумма степеней вершин любого графа равна удвоенному числу его рёбер. Кроме того, формула утверждает, что в любом графе число вершин нечётной степени чётно. Данное утверждение (и сама формула) известны как лемма о рукопожатиях. Название происходит от известной математической задачи: необходимо доказать, что в любой группе число людей, пожавших руку нечётному числу других чётно.

Последовательность степеней вершин

Рис. 2. Два неизоморфных графа с одинаковой последовательностью степеней (3, 2, 2, 2, 2, 1, 1, 1).

Последовательность степеней вершин неориентированного графа является невозрастающей последовательностью.^[2] Для графа, изображённого на рис. 1, она имеет вид (5, 3, 3, 2, 2, 1, 0). Последовательность степеней вершин есть инвариант графа, поэтому у изоморфных графов она одинакова. Однако последовательность степеней вершин не является уникальной характеристкой графа: в некоторых случаях неизоморфные графы также обладают одинаковой последовательностью.

Проблема последовательности степеней заключается в нахождении некоторых или всех графов с заданной невозрастающей последовательностью, состоящей из натуральных чисел (нулевые степени при этом могут быть проигнорированы, так как их количество изменяется добавлением или удалением изолированных вершин). Последовательность, являющаяся последовательностью степеней какого-либо графа, называется графической (англ. graphical sequence). Из формулы суммы степеней следует, что любая последовательность с нечётной суммой (как, к примеру, 3, 3, 1) не может быть последовательностью степеней графа. Обратное также верно: если последовательность имеет чётную сумму, она представляет собой последовательность степеней мультиграфа. Построение такого графа осуществляется достаточно простым способом: необходимо объединить вершины нечётных степеней в пары, к оставшимся незаполненными вершинам следует добавить петли.

$sum_{i=1}^{k}d_i leq k(k-1) + sum_{i=k+1}^n min(d_i,k) quad k in {1,dots,n} , .$

Например, последовательность (3, 3, 3, 1) не может являться последовательностью простого графа; она удовлетворяет неравенству Эрдёша — Галлаи только при k равном 1, 2 или 4, но не при k равном 3.

С. Л. Хакими доказал, что (d₁, d₂, …, d_n) есть последовательность степеней простого графа только если существует (d₂ − 1, d₃ − 1, …, d_d₁+1 − 1, d_d₁+2, d_d₁+3, …, d_n). Этот факт позволил разработать простой алгоритм нахождения простого графа с заданной реализуемой последовательностью:

Изначально граф не имеет рёбер.
Составляется список вершин, для которых требования по степеням пока не удовлетворены. Оставшиеся требования располагаются в порядке невозрастания.
Первая вершина соединяется со следующими d₁ вершинами из списка. После этого первая вершина удаляется, список пересортируется. Действие повторяется до тех пор, пока все требования не будут удовлетворены.

Частные значения

Рис. 3. Концевыми вершинами являются 4, 5, 6, 7, 10, 11 и 12.

Вершина степени 0 называется изолированной.
Вершина степени 1 называется концевой (англ. end vertex), висячей (англ. pendant vertex) или листом графа (англ. leaf vertex). Ребро, инцидентное такой вершине называется висячим (англ. terminal (pendant) edge, end-edge). На рис. 3 висячим ребром является {3,5}. Подобная терминология используется в изучении деревьев в общем и как структур данных.
Вершина степени n-1 графа порядка n называется доминирующей (англ. dominating vertex).

Общие свойства

Если все вершины графа имеют одинаковую степень k, граф называют k-регулярным или регулярным графом степени k. В этом случае сам граф имеет степень k.
Эйлеров путь существует в неориентированном, связном графе если и только если граф имеет 0 или 2 вершины нечётной степени. Если граф содержит 0 вершин нечётной степени, Эйлеров путь является циклом.
Орграф является псевдолесом только если полустепень захода каждой вершины не больше 1. Функциональный граф — частный случай псевдолеса, в котором полустепени захода всех вершин равны 1.
Согласно теореме Брукса, хроматическое число любого графа за исключением клики или нечётного цикла не превышает максимальной степени его вершин (Δ). Согласно теореме Визинга, хроматический индекс любого графа не превышает Δ + 1.
k-вырожденным графом называется граф, в котором каждый подграф имеет вершину степенью не больше k.

См. также

Полустепень захода и полустепень исхода вершин ориентированных графов
Распределение степеней

Примечания

↑ Дистель, стр. 5
↑ Дистель, стр. 278

Источники

Дистель, Рейнхард (2005), «Graph Theory» (3rd ed.), Berlin, New York: Springer-Verlag, ISBN 978-3-540-26183-4, <http://diestel-graph-theory.com/index.html>.
Эрдёш, П. & Галлаи, T. (1960), “«Gráfok előírt fokszámú pontokkal»”, Matematikai Lapok Т. 11: 264—274, <http://www.renyi.hu/~p_erdos/1961-05.pdf>.
Хакими, С. Л. (1962), “«On realizability of a set of integers as degrees of the vertices of a linear graph. I»”, Journal of the Society for Industrial and Applied Mathematics Т. 10: 496–506.
Сирксма, Хирард & Хоохефен, Хан (1991), “«Seven criteria for integer sequences being graphic»”, Journal of Graph Theory Т. 15 (2): 223–231, DOI 10.1002/jgt.3190150209.

Источник

Степени вершин графа

Степень
вершины deg(v)
графа G
– число
инцидентных ей ребер.

Максимальная
степень всех вершин графа
G
– (G):

(G)=MAX
deg(v)
.

vV

Минимальная
степень всех вершин графа G
– (G):

(G)
= MIN deg(v)
.

vV

Лемма о рукопожатиях.

Сумма степеней всех вершин графа g четна и равна удвоенному числу ребер.

Изолированная
вершина
графа G
– вершина, степень которой равна 0.

Висячая
вершина
графа G
– вершина, степень которой равна 1.

Доминирующая
вершина
графа G
– вершина, степень которой равна p-1,
где p
– количество
вершин графа G.

Например:

доминирующей
нет

висячие – v₃,
v₄

изолированная – v₅

Экстремальные графы

Полный
граф – любые
две вершины смежные. Обозначается, K_n.

Например:

Пустой
граф – не
имеет ребер. Обозначается через O_n.

Мультиграф
– граф, не содержащий петель, но с
кратными ребрами.

Псевдограф
– граф, содержащий петли и кратные
ребра.

Например:

Нуль-граф
– граф без вершин и без ребер.

Тривиальный
граф – граф
с одной вершиной (1,0 -граф).

Однородный
или регулярный граф –
все вершины имеют равную степень.

Например:

Двудольный
граф –
множество вершин графа можно разбить
на два непересекающиеся подмножества
V₁
и V₂таких, что
каждое ребро имеет одну концевую вершину
в V₁,
а вторую – в V₂,
причем V₁V₂=,
а V₁V₂=V.

Полный
двудольный граф
– двудольный,
у которого любые две вершины, входящие
в разные доли, смежные. Обозначается
K_p_,_q.

Звезда
– полный двудольный граф,
у которого p=1.
Обозначается K_1,_q.

Биграф
– двудольный граф.

Например:

Звезда
K_1,3

Полный
двудольный граф K_3,3

Двудольный
граф

Граф
G(V,E)
называют k-дольным,
если множество его вершин V
можно разбить
на такие подмножества V_i, i=
1..n
, чтолюбое ребро
графа имеет одну концевую вершину в V_i
, а другую – V_j
, причём V_i
V_j
= ,
i

j,
i,j=1..n,
а
V_i=V.

Например:

Изоморфизм графов.

Изоморфные
графы –
существует взаимноодназначное
соответствие, т. е. биекция,
между множествами их вершин, сохраняющая
отношение смежности.

Изоморфизм
графов G
и H
: G

H.

Например:

Заданы
два графа G₁,
G₂.
Определить
изоморфизм G₁,
G₂,
построив
биекцию их вершин.

Решение:

Граф
G₁
изоморфен
графу G₂,
потому что
существует биекция
:
V₁

V₂,
сохраняющая
отношение смежности.

Биекция
:

u 
V₁

 (u)

V₂

Например:

Изоморфны

Изоморфизм
есть отношение эквивалентности,
т. к. он:

симметричен;
рефлексивен;
транзитивен.

Подграфы

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

Дополнение
графа G
– граф G‘
= (V‘,
E‘),
такой, что
V=V‘,
а E‘=
V⁽²⁾
E
(вершины
смежные в G‘
не смежны в
G
и наоборот).

Подграф
G₁
= (V₁,
E₁)
графа G
= (V,
E)
– граф, у
которого все вершины и ребра удовлетворяют
следующим соотношениям V₁
V,
E₁
E.

Остовный
подграф графа G
– подграф,
содержащий
все вершины
графа G,
множество ребер есть подмножество ребер
графа G.

Порожденный
подграф ( порожденный подмножеством
вершин V₁)
– подграф, множество вершин которого
V₁

V,
а множество
ребер Е₁
содержит все ребра графа G,
инцидентные выбранным вершинам V₁.

Например:

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

#
#
#
#
#
#
#
#
#
#
16.11.2019316.42 Кб0om.doc
#

Источник

Содержание

Содержание
Лемма о рукопожатиях [ править | править код ]
Последовательность степеней вершин [ править | править код ]
7.5. Представление (способы задания) графов.

Степень или валентность вершины графа — количество рёбер графа G <displaystyle G> , инцидентных вершине x <displaystyle x> . При подсчёте степени ребро-петля учитывается дважды. [1]

Степень вершины обычно обозначается как d ( x ) <displaystyle d(x)> или deg ⁡ ( v ) <displaystyle deg(v)> . Максимальная и минимальная степень вершин графа G обозначаются соответственно Δ(G) и δ(G). На рис. 1 максимальная степень равна 5, минимальная — 0. В регулярном графе степени всех вершин одинаковы, поэтому в данном случае можно говорить о степени графа.

Содержание

Лемма о рукопожатиях [ править | править код ]

По формуле суммы степеней для графа G = ( V , E ) <displaystyle G=(V,E)> ,

∑ v ∈ V deg ⁡ ( v ) = 2 | E | , <displaystyle sum _deg(v)=2|E|,,>

Последовательность степеней вершин [ править | править код ]

Последовательность степеней вершин неориентированного графа является невозрастающей последовательностью. [2] Для графа, изображённого на рис. 1, она имеет вид (5, 3, 3, 2, 2, 1, 0). Последовательность степеней вершин есть инвариант графа, поэтому у изоморфных графов она одинакова. Однако последовательность степеней вершин не является уникальной характеристикой графа: в некоторых случаях неизоморфные графы также обладают одинаковой последовательностью.

Проблема последовательности степеней заключается в нахождении некоторых или всех графов с заданной невозрастающей последовательностью, состоящей из натуральных чисел (нулевые степени при этом могут быть проигнорированы, так как их количество изменяется добавлением или удалением изолированных вершин). Последовательность, являющаяся последовательностью степеней какого-либо графа, называется графической (англ. graphical sequence ). Из формулы суммы степеней следует, что любая последовательность с нечётной суммой (как, к примеру, 3, 3, 1) не может быть последовательностью степеней графа. Обратное также верно: если последовательность имеет чётную сумму, она представляет собой последовательность степеней мультиграфа. Построение такого графа осуществляется достаточно простым способом: необходимо объединить вершины нечётных степеней в пары, к оставшимся незаполненными вершинам следует добавить петли.

∑ i = 1 k d i ≤ k ( k − 1 ) + ∑ i = k + 1 n min ( d i , k ) k ∈ < 1 , … , n − 1 >. <displaystyle sum _^d_leq k(k-1)+sum _^min(d_,k)quad kin <1,dots ,n-1>,.>

Теория графов

Графы

Бинарное отношение на конечном множестве X есть ориентированный конечный граф (орграф) RÍX 2 . Таким образом, всякий орграф определяется множествами:

X=₁,X₂,…,X_n> – множеством вершин графа и множеством упорядоченных пар (кортежей)

Общепринято обозначать орграфы в виде

X – множество вершин орграфа;

U – множество дуг орграфа, или в виде

ГX = <Гx₁,Гx₂,…,Гx_n> – множество образов элементов множества X, т.е. отображение X в X, понимая термин отображения как точечно-множественное отображение.

Наряду с орграфами в приложениях рассматриваются неориентированные графы. Неориентированный граф является частным случаем орграфа, в котором для каждой дуги , т.е. бинарное отношение R обладает свойством симметрии. Если, кроме того, бинарное отношение R обладает свойством рефлексивности, то соответствующий ему ориентированный граф есть орграф-толерантность, содержащий дуги типа петля для всех вершин графа.

При геометрической реализации неориентированного графа вместо двух дуг и , соединяющих вершины X_i и X_j, употребляется одно ребро (X_i,X_j), не имеющее ориентации. На рис. 3.1.1 приведены геометрические реализации орграфов (слева) и их неориентированных аналогов – неориентированных графов (справа). G(X,U), если X’ÍX; U’ÍU, т.е. подграф G’ получим из графа G, если уберем какое-либо число вершин или ребер (дуг).

Две вершины графа называются смежными, если они соединены с началом другой.

Дуги называются смежными, если конец одной из них совпадает с началом другой.

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

Замкнутый путь называется контуром, а замкнутая цепь – циклом.

Сформулированные определения удобно представить в виде следующей таблицы:

Ориентированный граф	Неориентированный граф
Дуга	Ребро
Путь	Цепь
Контур	Цикл

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

Путь (цепь) называется простым, если он проходит через дуги графа по одному разу. В противном случае путь (цепь) называется составным. Аналогично определяются и простые контуры и циклы.

Цепь (цикл) называется гамильтоновой, если она проходит через все вершины графа по одному разу, т.е. элементарная цепь, проходящая через все вершины графа, есть гамильтонова цепь.

Цепь (цикл) называется эйлеровой, если она проходит через все ребра по одному разу, т.е. простая цепь (цикл), содержащая все ребра графа есть эйлерова цепь (цикл).

Аналогично определяются гамильтоновы и эйлеровы путь и контуры.

Симметричный граф Неориентированный граф

Граф-толерантность Неориентированный граф

Граф-декартово произведение Неориентированный полный граф

(с полным насыщением)

Степень вершины графа. Число ребер графа.

Вершина X_i называется инцидентной дуге (ребру) графа, если она является началом или концом этой дуги (ребра).

Степенью вершины графа называют число дуг (ребер), инцидентных данной вершине. Степень обозначается P(X_i).

Для ориентированного графа различают полустепень захода P + — число дуг, входящих в данную вершину, и полустепень исхода P — — число дуг, выходящих из данной вершины. Степень вершины ориентированного графа составит сумма полустепеней исхода и захода.

Если для некоторой вершины ориентированного графа полустепень захода некоторой вершины P + =0 и при этом полустепень исхода P — ¹0, то вершина называется входом графа.

Если для некоторой вершины ориентированного графа P — =0, а P + ¹0, то вершина называется выходом графа.

Граф, изображенный на рис. 3.1.2, имеет один вход – вершину X

Число ребер графа N связано со степенями его вершин следующим соотношением:

N= ,

где n – число вершин графа. Отсюда следует справедливость следующих утверждений:

1) Сумма степеней вершин любого графа четна;

2) Для любого графа число вершин, имеющих нечетные степени, четно;

3) Для однородного графа, т.е. графа, все степени вершин которого одинаковы и равны r, N= ;

4) Для полного графа, т.е. графа, в котором каждая пара вершин соединена ребром или дугой, P(X_i)=n-1, а N= .

Некоторой противоположностью полному графу является нуль-граф, не имеющий ребер или дуг и состоящий из изолированных вершин. Очевидно, степени верши нуль-графа равны 0.

Связность

Граф называется связным, если множество его вершин нельзя разбить на два или более подмножеств так, чтобы ни одна вершины одного подмножества не отображалась в вершину другого. В противном случае граф называется несвязным. Число подмножеств всех вершин графа, называется числом компонент связности для несвязного графа.

Существует другое определение связности графа. Граф называется связным, если две любые его вершины можно соединить цепью. Граф (рис. 3.1.3) является несвязным с двумя компонентами.

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

Определение 7.10. Степенью вершины v для неориентированного графа, обозначается d(v), называется количество ребер, инцидентных этой вершине. Вершина степени 0 называется изолированной. Вершина степени 1 называется висячей.

Определение 7.11. Полустепенью исхода вершины v для орграфа называется количество дуг, для которых v является начальной вершиной, обозначается .

Полустепенью захода вершины v называется количество дуг, для которых v является конечной вершиной, обозначается . Если, то вершинаv называется истоком. Если , то вершинаv называется стоком.

Теорема 7.2. (Теорема Эйлера) Сумма степеней вершин графа равна удвоенному количеству ребер:

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

Следствие 1. Число вершин нечетной степени четно.

Доказательство. По теореме Эйлера сумма степеней всех вершин – четное число. Сумма степеней вершин четной степени четна, значит, сумма степеней вершин нечетной степени также четна, следовательно, их четное число.

Следствие 2. Сумма полустепеней вершин орграфа равна удвоенному количеству дуг:

Доказательство. Сумма полустепеней вершин орграфа равна сумме степеней вершин графа, полученного из орграфа забыванием ориентации дуг.

7.5. Представление (способы задания) графов.

Граф как алгебраическая система:

модель, носителем которой является множество вершин, а отношение – бинарное отношение смежности вершин.

Получается путём расположения различных точек на плоскости для каждой вершины vÎV, причём если (v₁,v₂)ÎЕ, то проводится ребро (дуга) из v₁ в v₂.

Для представления в компьютере чаще всего граф задается либо матрицей смежности, либо матрицей инциденций.

Матрицей смежности вершин неориентированного графа G, содержащего n вершин, называют квадратную матрицу A=a_ij n-го порядка, у которой строки и столбцы матрицы соответствуют вершинам неориентированного графа.

Элементы a_ij матрицы A равны числу ребер, направленных из i-й вершины в j-ю. В случае неориентированного графа G ему вместе с ребром (v_i, v_j) принадлежит и ребро (v_j, v_i), поэтому матрица смежности вершин A=a_ij будет симметрична относительно главной диагонали.

ПРИМЕР. Граф: множество вершин V =

Матрица смежности симметрична относительно главной диагонали.

На главной диагонали стоит 1 (символ Л) из-за нерефлексивности отношения на множестве вершин (EÍV´V)

Логическая матрица отношения на множестве вершин графа, которое задается его ребрами.

a b c d

Источник

Лемма о рукопожатиях[править | править код]

Последовательность степеней вершин[править | править код]

Частные значения[править | править код]

Общие свойства[править | править код]

См. также[править | править код]

Примечания[править | править код]

Источники[править | править код]

Степень вершины (теория графов)

Содержание

Лемма о рукопожатиях

Линия

пример

пример

пример

график

Пример 1

Пример 2

петля

Пример 1

Пример 2

Степень вершины

Степень вершины в неориентированном графе

Пример 1

Пример 2

Степень вершины в ориентированном графе

Степень графа

Степень графа

Пример 1

Пример 2

Кулон Вертекс

пример

Изолированная вершина

пример

смежность

Пример 1

Пример 2

Параллельные края

Мульти График

Пример 1

Пример 2

Степень последовательности графика

Пример 1

Пример 2

“Степень вершины и подсчет числа ребер графа”. 7-й класс

Содержание

Лемма о рукопожатиях

Последовательность степеней вершин

Частные значения

Общие свойства

См. также

Примечания

Источники

Степени вершин графа

Сумма степеней всех вершин графа g четна и равна удвоенному числу ребер.

Экстремальные графы

Изоморфизм графов.

Подграфы

Содержание

Лемма о рукопожатиях [ править | править код ]

Последовательность степеней вершин [ править | править код ]

7.5. Представление (способы задания) графов.

Вам также может понравиться

Как в торе найти работу

Как найти сережку гвоздик

Как исправить статус в вконтакте

Добавить комментарий Отменить ответ