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

7.4. Степень вершин.

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

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

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

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

.

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

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

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

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

.

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

Пример 7.5. Определить степени вершин данного графа.

Пример 7.6. Определить полустепени исхода и захода данного орграфа.

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

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

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

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

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

Матрица смежности:

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

a_ij = 1 если в G существует дуга (x_i, x_j)

a_ij = 0 если в G нет дуги (x_i, x_j)

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

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

Элементы c_ij равны

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

–1, если дуга e_j заходит в 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.

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

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

Следствие 2. Число рёбер в полном графе [math]\frac <2>[/math] .

Ориентированный граф

Аналогично доказательству леммы о рукопожатиях неориентированном графе.

Бесконечный граф

В бесконечном графе лемма не работает, даже в случае с конечным числом вершин нечётной степени. Покажем это на примере.

При выборе бесконечного пути из вершины [math] V [/math] (см. рисунок справа) имеем путь, в котором все вершины кроме стартовой имеют чётную степень, что противоречит следствию из леммы.

Теория Графов. Часть 1 Введение и классификация графов

«Графы являются одним из объединяющих понятий информатики – абстрактное представление, которое описывает организацию транспортных систем, взаимодействие между людьми и телекоммуникационные сети. То, что с помощью одного формального представления можно смоделировать так много различных структур, является источником огромной силы для образованного программиста». Стивен С. Скиена

Введение

Сначала под землей города Москвы ничего не было. Потом была построена первая станция метро, а затем и вторая и третья. Образовалось множество станций метро. На карту было занесено множество точек. Позже между станциями стали прокладывать пути линии. И соединилась станция метро А со станцией метро Б. Все остальные станции также стали соединятся друг с другом и на карте появилось множество линий. В итоге мы имеем Московский метрополитен очень красивый, я там был проверял.

Схема Московского метро

Посмотрите какая красота. У нас имеется множество точек (которые называются вершинами или узлами), а также множество линий (называемые рёбрами или дугами). Обозначим множество вершин буквой V от английского vertex−вершина и множество рёбер обозначим E от английского edge−ребро. Граф в формулах именуют буквой G. Все вершины обязательно должны быть идентифицированы.

Отмечу, что число вершин обозначается буквой n:

Число рёбер обозначается буквой m:

Таким образом граф задается и обозначается парой V,E:

Граф — это совокупность пары множеств. Конечного есть и бесконечные, однако мы их пока не рассматриваем непустого множества V и множества E заданного неупорядоченными парами множества V.

Также определение графа рассказывается в этой статье на Хабре (https://habr.com/ru/post/65367/)

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

Разберем определение графа подробней. Может ли в G быть пустым множество E? Да без проблем! Такой граф будет называться нулевым, а вершины в нем будут называться изолированными.

Нулевой граф

Только вот множество V вершины пустым быть не может. Ведь множество E рёбра задается парой неупорядоченных вершин множества V. Две вершины образующие ребро, называются концами этого ребра.

Множество E задается парой неупорядоченных вершин множества V.

Пример: Пусть множество V = <1,2,3,4,5>. Тогда множество E =

Граф будет выглядеть следующим образом:

Висячей вершиной называется вершина которая соединена только с одной соседней вершиной. В нашем случаи висячей вершиной будет вершина 5, так как она соединена только с вершиной 1.

Степенью вершины — является количество рёбер исходящих выходящих из вершины и входящих в нее. Данное определение верно для ориентированных графов см. классификацию графов. Для неориентированных графов исходящая степень равна входящей. Степенью вершины 1 будет является число 4. Так как вершина 1 соединена с вершиной 2, 3, 4, 5.

Степень записывают, как:

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

Формула суммы степеней для G = V,E выглядит так:

То есть сумма степеней всех вершин v графа равна удвоенному количеству его рёбер E. Считаем количество степеней в нашем примере. От этого никуда не денешься. Я насчитал 12. А теперь считаем, сколько у нас рёбер. Их 6! Умножаем на 2 и получаем 12. Совпадение? Не думаю!

А давайте представим наш граф в другом виде, но с сохранением данных пар. G теперь имеет следующий вид:

Заметьте я не изменил пары между собой. Вершина 4 также соединяется с вершиной 3, а у вершины 1 степень также осталась 4. Так почему граф имеет совершенно другой вид и законно ли это?

Самое главное в графе это вершины и проведенные между ними рёбра. В связи с этим граф является топологическим объектом, а не геометрическим . То есть объектом который не меняется при любых растяжениях и сжатиях. Нам все равно какой мы сделали отрезок. Кривой, прямой, самое главное это наличие связи между вершинами. По этой причине графы являются очень универсальными в плане практического применения. Мы можем обозначать ими дороги, компьютерную сеть, людей которые дружат друг с другом или даже влюблены друг в друга.

Классификации графов

Первым признаком классификации является отсутствие или наличие ориентации у ребер.

Ребро является неориентированным если у него нет понятия начала или конца. То есть оба его конца равноправны. Такой граф называется неориентированным, обыкновенным или неографом.

Ориентированное ребро обозначается стрелкой. И указывает ориентацию от вершины к вершине. То есть данный граф имеет начало и конец. И называется он ориентированным или орграфом.

Ориентированный граф

Также существует граф со смешанными ребрами. Это когда в графе присутствуют, как ориентированные рёбра, так и неориентированные.

Вторым признаком является отсутствие или наличие кратных ребер.

Кратные ребра — это ребра которые встречаются между двумя вершинами сразу несколько раз. В примере ниже мы видим, что вершина a соединена с вершиной c несколько раз. То же самое происходит и a c b. Такой граф называется мультиграфом.

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

Заключение

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

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

Вершины в графе могут отличаться друг от друга тем, скольким ребрам они принадлежат.
Степенью вершины называется число ребер графа, которым принадлежит эта вершина.
Обозначать степени вершин А, В, Сбудем соответственно так: d(А), d(В), d(С) и т. п.
Задача 2.1.
а) Найдите степени вершин А, В, С и D.
Ответ: степ.А=1; степ.В=2; степ.С=1; степ.D=2.

б) Чему равна степень каждой вершины?
Ответ: 2
в) Чему равна степень каждой вершины?
Ответ: 0.
Степень изолированной вершины равна 0.
Вершина называется нечетной,если ее степень — число не­
четное. Вершина называется четной,если ее степень — число
четное.
Задача 2.2. Уезжая из летнего лагеря, подружившиеся ребята обменялись конвертами с адресами. Докажите, что
а) всего было передано четное число конвертов;
б) число участников, обменявшихся конвертами нечетное чис­ло раз, четное.
Решение. Пусть участники слета А1, А2, A3. Ап — вершины графа, а ребра соединяют на рисунке 15 пары вершин, изобра­жающих ребят, обменявшихся конвертами:
рис. 15
а) степень каждой вершины Ai показывает число конвертов, которые передал участник Аi своим знакомым. Общее число переданных кон­вертов N равно сумме степеней всех вершин графа. N = степ. А1+степ. А2+. +степ. Ап-1+ степ. Ап, но N = 2р, где р — число ре­бер графа, то есть N — четное. Следовательно, было передано четное число конвертов.
б) в равенстве N = степ. А1 + степ. А2 + . + степ. Ап-1 + степ. Ап сумма нечетных слагаемых должна быть четной, а это может быть только в том случае, если число нечетных слагаемых четно. А это означает, что число участников, обменявшихся кон­вертами нечетное число раз, четное.
В ходе решения задачи 1 доказаны два свойства.
Свойство 1. В графе G сумма степеней всех его вершин — число четное, равное удвоенному числу ребер графа.
степ. А1 + степ. А2+ . + степ. Аn = 2р,
где р — число ребер графа Г, n — число его вершин.
Свойство 2. Число нечетных вершин любого графа четно.
Задача 2.3. Девять шахматистов проводят турнир в один круг (каждый из участников должен сыграть с каждым из осталь­ных по одному разу). Покажите, что в любой момент найдутся двое, закончившие одинаковое число партий.
Решение. Переведем условие задачи на язык графов. Каж­дому из шахматистов поставим в соответствие вершину графа, со­единим ребрами попарно вершины, соответствующие шахматистам, уже сыгравшим между собой партию. Получим граф с девятью вер­шинами. Степени его вершин равняются числу партий, сыгранных соответствующими игроками. Покажем, что во всяком графе с де­вятью вершинами всегда найдутся хотя бы две вершины одинаковой степени.
Каждая вершина графа с девятью вершинами может иметь сте­пень, равную 0, 1, 2, . 7, 8. Предположим, что существует граф G, все вершины которого имеют разную степень, т. е. каждое из чисел последовательности 0, 1, 2, . 7, 8 является степенью одной и только одной из его вершин. Но этого не может быть. Действитель­но, если в графе есть вершина Астепени 0, то в нем не найдется вер­шина Всо степенью 8, так как эта вершина В должна быть соедине­на ребрами со всеми остальными вершинами графа, в том числе и с А. Иначе говоря, в графе с девятью вершинами не могут быть одновременно вершины степени 0 и 8. Следовательно, найдутся хотя бы две вершины, степени которых равны между собой.
Вернемся к задаче. Доказано, что в любой момент найдутся хотя бы двое, сыгравшие одинаковое число партий.
Решение этой задачи почти дословно повторяется в ходе дока­зательства следующего свойства (только число 9 приходится заменить произвольным натуральным числом n ? 2).
Свойство 3. Во всяком графе с n вершинами, где n ? 2, всегда найдутся, по меньшей мере, две вершины с одинаковыми сте­пенями.
Задача 2.4. Девять человек проводят шахматный турнир в один круг. К некоторому моменту выясняется, что в точности двое сыграли одинаковое число партий. Докажите, что тогда либо в точности один участник еще не сыграл ни одной партии, либо в точности один сыграл все партии.
Решение: Условие задачи переведем на язык графов. Пусть вершины графа — игроки, а каждое ребро означает, что соответ­ствующие игроки уже сыграли между собой партию. Из условия известно, что в точности две вершины имеют одинаковые степе­ни. Требуется доказать, что в таком графе всегда найдется либо только одна изолированная вершина, либо только одна вершина степени 8.
В общем случае у графа с девятью вершинами степень каждой вершины может принимать одно из девяти значений: 0, 1, 2, . 7, 8. Но у такого графа степени вершин принимают только восемь разных значений, ибо ровно две вершины имеют одинако­вую степень. Следовательно, обязательно либо 0, либо 8 будет значением степени одной из вершин.
Докажем, что в графах с девятью вершинами, из которых в точности две имеют одинаковую степень, не может быть двух вершинстепени 0 или двух вершин степени 8. Допустим, что все же найдется граф с девятью вершинами, в котором ровно две вершины изолированные, а все остальные имеют разные между собой степени. Тогда, если не рассматривать эти две изолированные вершины, останется граф с семью вершинами, степени которых не совпадают. Но такого графа не существует (см. свойство 3). Значит, это предположение неверное.
Теперь допустим, что существует граф с девятью вершинами, в котором ровно две вершины имеют степень 8, а все остальные — несовпадающие степени. Тогда в дополнении данного графа ровно две вершины будут иметь степень 0, а остальные попарно различ­ные степени. Этого тоже не может быть (свойство 3), т. е. и второе предположение неверное.
Следовательно, у графа с девятью вершинами, из которых в точности две имеют одинаковую степень, всегда найдется либо одна изолированная вершина, либо одна вершина степени 8.
Вернемся к задаче. Как и требовалось доказать, среди рассмот­ренных девяти игроков либо только один еще не сыграл ни одной партии, либо только один сыграл уже все партии.
При решении этой задачи число 9 можно было заменить любым другим натуральным числом n > 2.
Это решение поможет вам провести доказательство следующего свойства:

Свойство 4. Если в графе с n вершинами (n > 2) в точно­сти две вершины имеют одинаковую степень, то в этом графе всег­да найдется либо в точности одна вершина степени 0, либо в точ­ности одна вершина степени n — 1.