Сумма степеней вершин графа

Сумма степеней вершин графа

Графы!

Вводное.

Что это вообще такое? На данном этапе граф можно и нужно воспринимать как некоторое обобщение различных объектов, которые можно изобразить, обозначив что-то за точки, а что-то – за линии, их соединяющие. Например, города и дороги между ними (город – точка, дорога — линия), или знакомства между людьми (человек – точка, знакомство – линия; если люди не знакомы, линии между ними нет).

  • Напишите по кругу числа от 1 до 15. А потом соедините линией те пары, где большее число делится на меньшее. У вас получится граф.
  • Теперь напишите названия всех дней недели (понедельник, вторник, …, воскресенье). Соедините названия линиями, если они имеют общую букву. Теперь напишите заново и соедините, если букв хотя бы две.
  • Придумайте свой граф – объекты и то, что соединяет некоторые из них.

Суть вы поняли! Кстати, карта метро – уже готовый граф.

Основные понятия, которые нам нужны.

Вершины графа – это те самые точки, которые мы соединяем. Города, числа, люди и так далее.

Ребра графа – линии, соединяющие точки. Дороги между городами, рукопожатия между людьми, делимость между числами и так далее.

Степень вершины – число ребер, выходящих из нее. Например, в графе, который нарисован справа, вершины A, I, E и D имеют степень 1, потому что из них выходит всего по одному ребру, вершины B, H, F и С имеют степень 2, а вершины G и J имеют степень 3.

Если в графе всего N вершин, то максимальная степень вершины в нем может быть равна N-1 – когда одна вершина соединена со всеми остальными. Минимальная, разумеется, может быть равна 0.

Путь в графе – последовательность вершин, в которой любые две соседние вершины соединены между собой ребром. На данной картинке, например, A B J I – путь.

Цикл в графе – путь, у которого первая вершина совпадает с последней. На картинке – C G F C.

Связный граф – граф, в котором от любой до любой другой существует путь (то есть можно «дойти» по ребрам). Например, граф справа не связный, ведь от A до E, например, не добраться.

1) Нарисуйте граф с 6 вершинами и степенями вершин 2,2,3,3,4,4

2) Попробуйте нарисовать граф с 7 вершинами и степенями 6,6,4,4,2,1,1. Почему не получается?

Основное соображение.

Давайте посчитаем количество ребер в графе. Делать это будем так – сложим все степени вершин, ведь так мы как раз подсчитаем все ребра. Если из вершины А выходит три ребра, из вершины Б – два, из вершины В — тоже два, из вершины Г – одно, то сумма 3+2+2+1=8 должна учитывать все ребра.

Но! Поскольку каждое ребро выходит ровно из двух вершин, мы и учли его дважды. Например, ребро между А и Б мы подсчитали и в степени А, и в степени Б. Следовательно, наше полученное число следует еще разделить пополам, и тогда мы получим реальное количество ребер. То есть

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

  • Проверьте это на графах, которые вы уже нарисовали – подсчитайте сумму степеней и количество ребер. Убедитесь в том, что это правило работает и запомните его навсегда.

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

Примеры того, как помогают решать задачи эти соображения.

Пример №1: Могут ли все вершины в графе иметь степень 2, а одна вершина – степень 3?

Ответ: Нет, не могут. Сумма степеней – какое-то количество двоек и одна тройка – безусловно нечетна. А она не может быть нечетной, потому что равна удвоенному количеству ребер.

Пример №2: В графе сто вершин и а) каждая соединена с каждой; б) у каждой степень равна 50; в) степень 25 из них равна 4, 25 – 8, а у 50 – 6. Сколько ребер в графе?

Ответ: Просто считаем сумму степеней и делим пополам. В первом случае это (100*99):2 = 4950, во втором — (100*50):2=2500, в третьем – (25*4+25*8+50*6):2=300.

В нижеследующих задачах очень важно «найти граф» — определить какие-то объекты как вершины, а какие-то – как ребра.

Решите это сами:

3) Известно, что в графе все степени вершин равны, самих вершин 24, а ребер – 60. Чему равна степень любой вершины этого графа?

Читайте также:  Как разобрать мышь qumo dragon war

4) Докажите, что в любом графе какие-то две вершины имеют одинаковую степень.

5*) В компании из k человек каждый имеет ровно трех знакомых, любые двое незнакомых имеют общего знакомого и есть трое попарно знакомых. Найдите наибольшее возможное значение k.

6) В стране есть несколько аэропортов, каждый из которых соединён авиалиниями ровно с пятью другими. Однажды из-за сильного снегопада бóльшую часть аэропортов пришлось закрыть. После этого оказалось, что из каждого работающего аэропорта можно вылететь только в три других, а закрытыми оказались 26 авиалиний. (Авиалиния закрывается, если закрывается хотя бы один из двух аэропортов, которые она соединяет.)

а) Докажите, что число работающих после снегопада аэропортов чётно.
б*) Докажите, что число закрывшихся аэропортов делится на 4.
в*) Сколько авиалиний не закрылось из-за снегопада?

Делимость и остатки.

С остатками все просто. Любое натуральное число от деления на любое другое дает какой-то остаток (иногда этот остаток равен 0, и тогда мы говорим, что одно число делится на другое). Например, 10 дает остаток 1 от деления на 3 и остаток 2 от деления на 8. И, к слову, оно же дает остаток 10 от деления на 11, 25, 26, 100, 413… и так далее. В общем, на любое число, которое больше, чем оно само.

Определение 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)

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

a b c d

граф с кратными

рёбрами и петлёй

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

Элементы aij матрицы A равны числу дуг, направленных из i-й вершины в j-ю. Если орграф состоит из однократных дуг, то элементы матрицы равны либо 0, либо 1.

Пусть дан граф G, его матрица смежности А = [aij] определяется следующим образом:

Определение 7.14. Матрицей инциденций (инцидентности) неориентированного графа с вершинами и ребрами называется матрица размерности, строки которой соответствуют вершинам, а столбцы – ребрам. Элементыматрицы инциденций неориентированного графа равны 1, если вершинаинцидентна ребру, и 0 в противном случае.

Матрицей инциденций (инцидентности) орграфа с вершинами и дугами называется матрица размерностиnm, строки которой соответствуют вершинам, а столбцы -дугам орграфа.

Читайте также:  Заданный символ является цифрой

1, если дуга ej исходит из i-й вершины;

0, если дуга не инцидентна i-й вершине

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

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

В каждом столбце также будут две единицы, так как каждое ребро инцидентно двум вершинам.

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

Поэтому, используя матрицу инцидентности, нельзя восстановить ориентированный граф.

Такую возможность обеспечивает матрица смежности,

Пример 7.7.1. Для заданного неориентированного графа построить матрицы смежностей и матрицу инциденций.

Решение. 1) Строим матрицу смежности вершин, которая будет размерности 44. Строим матрицу смежности ребер, которая будет размерности 55.

2) Строим матрицу инциденций, которая будет размерности 45.

Пример 7.7.2. Для заданного ориентированного графа построить матрицы смежностей и матрицу инциденций.

Решение. 1) Строим матрицу смежности вершин, которая будет размерности 44. Строим матрицу смежности ребер, которая будет размерности 55.

2) Строим матрицу инциденций, которая будет размерности 45.

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

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

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

Последовательность степеней вершин неориентированного графа является невозрастающей последовательностью. [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 ).
Читайте также:  User request что это

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

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

См. также

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

Примечания

  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 Существование эйлерова пути и цикла … Википедия

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

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

Ссылка на основную публикацию
Стиральная машина самсунг горит красный замок
Любая стиральная машина в независимости от марки производителя иногда выходит из строя. Довольно частым признаком неисправности, является мигание индикатора замка....
Справка по форматированию steam
С помощью этих тегов разметки можно форматировать текст ваших сообщений, примерно как в HTML. Маркированный список Маркированный список Маркированный список...
Справочные материалы база данных
АРМ предназначено для комплексной автоматизации операций, связанных с первичным размещением и вторичным обращением ценных бумаг. Оно рассчитано на работу с...
Стиральная машинка lg не выжимает
Покупка стиральной машинки – знаменательное событие для любой хозяйки. Незаменимая помощница позволяет женщинам экономить личное время, не тратя его на...
Adblock detector