No Image

Укажите степени вершин графа

СОДЕРЖАНИЕ
7 просмотров
11 марта 2020

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

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

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

Последовательность степеней вершин неориентированного графа является невозрастающей последовательностью. [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. Изначально граф не имеет рёбер.
  2. Составляется список вершин, для которых требования по степеням пока не удовлетворены. Оставшиеся требования располагаются в порядке невозрастания.
  3. Первая вершина соединяется со следующими d1 вершинами из списка. После этого первая вершина удаляется, список пересортируется. Действие повторяется до тех пор, пока все требования не будут удовлетворены.

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

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

  • Вершина степени 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.
Читайте также:  Видеокарта s3 trio64v2 dx

См. также

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

Примечания

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

Источники

  • Дистель, Рейнхард (2005), «Graph Theory» (3rd ed.), Berlin, New York: Springer-Verlag, ISBN 978-3-540-26183-4 , .
  • Эрдёш, П. & Галлаи, T. (1960), "«Gráfok előírt fokszámú pontokkal»", Matematikai Lapok Т. 11: 264—274 , .
  • Хакими, С. Л. (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 .

Wikimedia Foundation . 2010 .

Смотреть что такое "Степень вершины (теория графов)" в других словарях:

Дуга (теория графов) — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия

Цикл (теория графов) — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия

Дерево (теория графов) — У этого термина существуют и другие значения, см. Дерево (значения). Дерево это связный ациклический граф.[1] Связность означает наличие путей между любой парой вершин, ацикличность отсутствие циклов и то, что между парами вершин… … Википедия

Графов теория — раздел конечной математики (См. Конечная математика), особенностью которого является геометрический подход к изучению объектов. Основное понятие теории граф. Граф задаётся множеством вершин (точек) и множеством рёбер (связей), соединяющих … Большая советская энциклопедия

Глоссарий теории графов — Эта страница глоссарий. См. также основную статью: Теория графов Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице) … Википедия

Словарь терминов теории графов — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И К Л М Н О П Р С … Википедия

Читайте также:  Аппарат для создания вакуума

Практическое применение раскраски графов — Эту статью следует викифицировать. Пожалуйста, оформите её согласно правилам оформления статей. Раскраска графов практически применяется (постановку задачи различиных раскрасок здесь обсуждаться не будет) дл … Википедия

Теоремы теории графов — Здесь собраны теоремы из теории графов. Содержание 1 Лемма о рукопожатиях 2 Существование эйлерова пути и цикла … Википедия

Вершина (граф) — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия

Длина пути в орграфе — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия

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

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

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

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

.

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

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

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

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

.

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

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

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

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

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

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

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

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

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

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

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

Читайте также:  Love mail ru регистрация

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

a b c d

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

Максимальная и минимальная степени вершин графа обозначаются символами и соответственно:

Список степеней вершин графа называется его степенной последовательностью. Порядок членов в этой последовательности роли не играет.

Вершина степени 0 называется изолированной, вершина степени 1 — концевой (или висячей). Ребро, инцидентное концевой вершине, также называется концевым.

Рассмотрим сумму степеней всех вершин графа. Каждое ребро вносит в эту сумму 2, поэтому верно

Утверждение 5.1 («лемма о рукопожатиях»). Сумма степеней всех вершин графа — четное число, равное удвоенному числу ребер:

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

Следствие 5.2. В любом графе число вершин нечетной степени четно.

Понятие степени вершины и лемма о рукопожатиях cохраняются для мульти- и псевдографов. При этом каждая петля вносит в степень соответствующей вершины двойку.

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

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

Назовем -последовательность правильной, если выполняются два следующих условия:

2) — четное число.

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

Рассмотрим последовательность . Существуют ровно пять графов (не обязательно связных), являющихся реализациями последовательности . Они имеют следующие компоненты: 1) , и 2) , и 3) и 4) и 5) и .

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

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

Однако указанные условия отнюдь не являются достаточными для графичности последовательности. Очевидно, например, что последовательность не является графической, хотя и удовлетворяет упомянутым условиям. Известно несколько критериев графичности последовательности. Мы укажем один из них.

Теорема 5.3 (П. Эрдёш, Т. Галлаи, 1960 г.). Правильная -последовательность является графической тогда и только тогда, когда для каждого верно неравенство

При тестировании последовательности с помощью этого критерия нет необходимости проверять все неравенств. Обозначим . Тогда верно

Утверждение 5.4. Если правильная -последовательность удовлетворяет каждому из неравенств критерия Эрдеша-Галлаи при , то она удовлетворяет и каждому из оставшихся неравенств.

Комментировать
7 просмотров
Комментариев нет, будьте первым кто его оставит

Это интересно
No Image Компьютеры
0 комментариев
No Image Компьютеры
0 комментариев
No Image Компьютеры
0 комментариев
No Image Компьютеры
0 комментариев
Adblock detector