Формула суммы степеней графа

Формула суммы степеней графа

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Читайте также:  Взлом роутера тп линк

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

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

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

А В

С Д — не полный граф

С Д — полный граф

Только для неориентированного графа существует дополнение:

– дополнение

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

Степенью вершины называется количество ребер ей принадлежащих

Степень А=1, степень В=2, степень С=2, степень Д=1, степень Е=0

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

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

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

где каждое

М – симметричная на главной диагонали – 0

М(Г)=

Лабораторная работа № 2.

Задание графа матрицей смежности

Изучить понятия полный граф, дополнение графа.

Рассмотреть способ задания графа с помощью матрицы смежности.

"’Графы и их применение". Березина Л.Ю.. М: Просвещение. 1979г.

"Теория графов. Алгоритмический подход", Кристофидес Н.

"Применение теории графов в программировании". Евстигнеев В.А. — М.: Наука. 1985г.

Порядок выполнения работы:

Разработать схему алгоритмов основной программы и подпрограмм.

Написать и отладить программу на языке Turbo Pascal.

Граф задан матрицей смежности

М=

Изобразить граф, исходя из внешнего вида данной матрицы.

Краткие теоретические сведения:

Матричный эквивалент графа широко используется в работе с графами на ЭВМ.

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

от граф не является полным

Граф, не являющийся полным, можно преобразовать в полный граф с теми же вершинами, добавив недостающие ребра.

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

Каждой вершине графа можно поставить в соответствие строку и столбец с номером i, причем

< 1, если

< 0, если

Тогда матрица называется матрицей смежностей графа Г и обозначается М(Г).

Написание программы на языке Turbo Pascal

Что такое полный граф?

Дайте понятие дополнение графа?

Что такое матрица смежностей графа?

Как составить матрицу смежностей?

Тема 7.3 Метрические характеристики графа.

Пусть дан граф:

Как от вершины А1 дойти до А5?

Читайте также:  Топ самых надежных смартфонов

Существуют следующие пути:

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

Путь, в котором начальные и конечные вершины совпадают называют циклом.

Путь от вершины А1 до Аn называется простым, если он не проходит ни через одну из вершин графа более одного раза.

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

Длиной пути (цикла) называется количество ребер его составляющих.

Дан граф. Найти пути от А1 до А6 и определить их длину

Расстоянием от вершины А до вершины В называется длина наименьшего пути, если не существует пути от А до В, то считают что расстояние равно бесконечности.

Вершины А и В называются связными, если не существует пути связывающего их.

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

Ясно, что степень любой вершины конечного графа есть целое неотрицательное число. Вообще, определенное нами понятие степени имеет смысл лишь для вершин, инцидентных конечному числу ребер, при этом множество вершин и множество ребер графа могут быть бесконечными. Так, на рис. 6 представлен бесконечный граф, все вершины которого имеют степень 4 (кроме первой вершины, имеющей степень 2). Этот граф моделирует так называемые размножения».

Вершина графа степени 0 называется изолированной. Если степень вершины равна 1, то она называется концевой или висячей вершиной. Вершина, степень которой больше или равна 2, называется промежуточной или проходной. Так, на рис. 4 вершина D — изолированная, вершина С — висячая, а остальные вершины — проходные.

Вершины графа называются четными или нечетными в зависимости от четности их степеней. Так, в графе на рис. 6 все вершины — четные. Граф на рис. 4 имеет две нечетные вершины (С и Н),а остальные вершины этого графа — четные.

Теорема 1. В любом конечном графе G(V, Е) количество нечетных вершин — четно.

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

Здесь через Е обозначено число элементов во множестве

Е, т.е. количество ребер графа G. Формула (1.4.1) показывает, что сумма степеней всех вершин графа есть четное число. Поэтому в эту сумму может входить лишь четное количество нечетных слагаемых, т.е. количество нечетных вершин графа G есть четное число.

Читайте также:  Почему полосит струйный принтер

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

Задачи и упражнения

  • 1. Докажите, что число перекрестков любого города, в которых встречается нечетное число улиц — четно.
  • 2. У марсиан бывает произвольное число рук. Однажды все марсиане взялись за руки так, что свободных рук не осталось. Докажите, что количество марсиан с нечетным числом рук четно.
  • 3. Докажите, что число зрителей, пришедших на стадион смотреть футбольный матч и имеющих нечетное число знакомых (среди того же множества зрителей) четно.
  • 4. Докажите, что число людей, когда-либо живших на Земле и сделавших нечетное число рукопожатий, четно.
  • 5. В классе 30 человек. Может ли быть так, что 9 из них имеют по 5 друзей каждый, 11 — по 4 друга и 10 — по 3 друга?
  • 6. В офисе 15 телефонов. Можно ли их соединить между собой проводами так, чтобы каждый был соединен с 3 другими?
  • 7. Можно ли нарисовать на плоскости 11 отрезков так, чтобы каждый пересекался ровно с тремя другими?
  • 8. В государстве 100 городов, и из каждого из них выходит по 4 дороги. Сколько всего дорог в государстве?
  • 9. Может ли в государстве, в котором из каждого города выходит ровно по три дороги, быть 100 дорог?
  • 10. На радиостанции каждый радиоузел соединен ровно с 15 другими. Может ли быть число проводов на радиостанции равно 200?

Во всех задачах нужно смоделировать условия при помощи графов. Задачи 1-7 решаются при помощи теоремы 1, а при решении задач 8-10 нужно использовать следствие из этой теоремы.

Доказательство утверждений в задачах 1—4 дословно повторяет доказательство теоремы 1.

В задачах 5-7 ответ отрицательный, так как ситуации, соответствующие условиям каждой из этих задач, противоречат теореме 1.

  • 7. Нужно рассмотреть граф, вершины которого соответствуют отрезкам, а ребра соединяют вершины, которым соответствуют пересекающиеся отрезки.
  • 8. Рассмотрим граф G(V, Е), у которого множество вершин V состоит из 100 городов, а множество ребер Е состоит из всех дорог государства. По условию задачи каждая вершина этого графа имеет степень 4. Применяя формулу (1.4.1), получим, что 4100 = 2-|?|.

Следовательно, количество дорог |?| равно 200.

9. Моделируя условие задачи так же, как в задаче 8, и применяя следствие из теоремы 1, получим: 3-|f| = 2• 100. Так как количество вершин |f| должно

быть натуральным числом, то ответ на вопрос задачи — отрицательный.

10. Ответ к задаче — отрицательный. Ее решение аналогично решению задачи 9.

Ссылка на основную публикацию
Уроки нлп для начинающих
Если вы хотя бы немного интересуетесь психологией, то о нейролингвистическом программировании (НЛП), наверное, тоже слышали. В статье мы постараемся объяснить...
Технология etth что это
ETTH — Ethernet To The Home (ETTH) is a specific application of Fiber to the premises (FTTP) that first emerged...
Технология nfc в наушниках что это
NFC — это аббревиатура от английского Near Field Communication. С помощью этой технологии становится возможным обмен данными между различными устройствами,...
Уроки ворд 2010 для начинающих
Microsoft Office 2010 — бесплатные обучающие уроки для чайников с нуля. Получите необходимые навыки профессиональной работы с пакетом Microsoft Office...
Adblock detector