Существует ли граф у которого сумма степеней всех вершин равна 365

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задача

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

<A1, A4>,<A4,A2>,<A2, A1>,<A1, A4>,<A4, A5> — не является путем, т.к. ребро <A1, A4> встречается дважды.

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

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

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

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

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

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

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

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

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

Следствие 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 = . Тогда множество 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. Такой граф называется мультиграфом.

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

Заключение

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

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 [/math] .

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

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

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

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

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

3.02.1. Основные числовые характеристики и матрицы графа. Степени вершин графа

Степенью вершины V графа G называется число инцидентных ей рёбер, т. е. число рёбер, выходящих из данной вершины. (В случае псевдографов каждая петля добавляет 2 в степень вершины). Обозначается степень вершины V графа G: degGv или просто deg V, если ясно, о каком графе G идет речь.

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

Называется Концевым.

Вершина V Графа G, смежная со всеми другими вершинами G, называется Доминирующей. Её степень degGv очевидно равна |G| —1.

Граф G называется Регулярным (или, по-другому, Однородным), если степени всех его вершин равны. Эта общая степень всех вершин регулярного графа G называется степенью регулярного графа G и обозначается deg G.

Последовательность степеней вершин графа G, записанная в каком либо порядке называется степенной последовательностью графа G. Например, граф на рисунке справа имеет степенную последовательность (3, 3, 1, 0, 1, 2).

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

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

Лемма 1 ("о рукопожатиях"). Сумма степеней всех вершин графа G есть число чётное, ровно в два раза большее числа рёбер графа G, т. е.

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

Но при этом каждое ребро будет учтено 2 раза: один раз, когда рассматривался один его конец, другой раз, когда — второй. Таким образом, лемма верна.

Из леммы 1 вытекает

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

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

В ориентированных графах для каждой вершины V дополнительно рассматривается также полустепень исхода и полустепень захода. Полустепенью исхода вершины V называется число дуг графа G, для которых V Является началом, а Полустепенью захода – число дуг, для которых V является концом. Обозначаются полустепени захода и исхода графа G соответственно deg-V и deg+V. При этом полная степень degV = deg-V+ deg+V. Поскольку каждая дуга имеет ровно одно начало и один конец, то справедлива