Что такое степень вершины в графе

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.

Что такое степень вершины в графе

Под графом мы будем понимать множество точек ( вершин ), некоторые из которых соединены отрезками ( ребрами ).
Степень вершины графа — это количество выходящих из нее (или, что то же самое, входящих в нее) ребер (еще говорят: количество ребер, инцидентных данной вершине). Вершина графа называется четной , если ее степень четна, и нечетной в противном случае.
Некоторая часть вершин данного графа называется компонентой связности , если из любой ее вершины можно «дойти» до любой другой, двигаясь по ребрам.

В некоторых случаях на ребрах графа выбирается «направление движения» (например, когда на автомобильной дороге вводится одностороннее движение). При этом получается ориентированный граф . (Если направление движения по ребрам не определено, то граф называется неориентированным ). В ориентированном графе различают положительную и отрицательную степень каждой вершины (то есть количество ребер, соответственно, входящих и выходящих из нее). Две вершины могут быть соединены и несколькими ребрами, направления движения по которым противоположны («дорога с двусторонним движением»). Изменяется понятие компоненты связности: теперь каждый «маршрут» от одной вершины до другой должен учитывать направление движения по ребрам.

Задачи

3. Можно ли, сделав несколько ходов конями из исходного положения (верхний рисунок), расположить их так, как показано на нижнем рисунке? (Выходить за пределы поля 3×3 не разрешается.)

Построим граф, вершинами которого являются города, а ребрами — существующие авиалинии. Вспомним признак делимости на 3: натуральное число делится нацело на 3 тогда и только тогда, когда сумма его цифр делится на 3. Заметим, что если название города делится на 3, то он соединен авиалиниями только с городами, названия которых тоже делятся на 3. Наоборот, те города, названия которых не делятся на 3, не могут быть соединены авиалиниями с городами, названия которых делятся на 3. Поэтому города 3, 6 и 9 образуют одну компненту связности графа, в которую никакие другие города не входят. Это означает, что из города 1 в город 9 добраться по воздуху нельзя.

Упражнение: А какие еще компоненты связности есть в этом графе?

Теорема 1. Количество ребер в любом графе равно половине суммы степеней его вершин.
Докажите эту теорему самостоятельно по аналогии с задачей 5.

6. В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими?
Подсказка: попытайтесь посчитать количество телефонных проводов.

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

8. В классе 30 человек. Может ли быть так, что 9 человек имеют по 3 друга, 11 — по 4 друга, а 10 — по 5 друзей?

Теория графов. Термины и определения в картинках

В этой статье мы познакомимся с основными терминами и определениями Теории графов. Каждый термин схематично показан на картинках.

Самый объёмный модуль на курсе «Алгоритмы и структуры данных» посвящён теории графов.

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

Например, граф на рисунке состоит из 8 вершин и 8 рёбер.

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

В этой статье мы познакомимся с основными терминами и определениями теории графов. На курсе “Алгоритмы и Структуры данных” в компании Отус “Теория графов” изучается в самом объёмном модуле из 6 вебинаров, где мы изучаем десяток самых популярных алгоритмов.

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

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

Инцидентность — вершина и ребро называются инцидентными, если вершина является для этого ребра концевой. Обратите внимание, что термин “инцидентность” применим только к вершине и ребру.

Смежность вершин — две вершины называются смежными, если они инцидентны одному ребру.

Смежность рёбер — два ребра называются смежными, если они инцедентны одной вершине.

Говоря проще — две вершины смежные, если они соединены ребром, два ребра смежные — если они соединены вершиной.

Петля — ребро, инцидентное одной вершине. Ребро, которое замыкается на одной вершине.

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

Кратные рёбра — рёбра, имеющие одинаковые концевые вершины, по другому их называют ещё параллельными.

Мультиграф — граф с кратными рёбрами.

Псевдомультиграф — граф с петлями и кратными рёбрами.

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

Изолированная вершина — вершина с нулевой степенью.

Висячая вершина — вершина со степенью 1.

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

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

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

Сколько рёбер в полном графе? Это известная задача о рукопожатиях: собралось N человек (вершин) и каждый с каждым обменялся рукопожатием (ребро), сколько всего было рукопожатий? Вычисляется как сумма чисел от 1 до N — каждый новый участник должен пожать руку всем присутствующим, вычисляется по формуле: N * (N — 1) / 2.

Регулярный граф — граф, в котором степени всех вершин одинаковые.

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

Планарный граф. Если граф можно разместить на плоскости таким образом, чтобы рёбра не пересекались, то он называется “планарным графом” или “плоским графом”.

Если это невозможно сделать, то граф называется “непланарным”.

Минимальные непланарные графы — это полный граф К5 из 5 вершин и полный двудольный граф К3,3 из 3+3 вершин (известная задача о 3 соседях и 3 колодцах). Если какой-либо граф в качестве подграфа содержит К5 или К3,3, то он является непланарным.

Путь или Маршрут — это последовательность смежных рёбер. Обычно путь задаётся перечислением вершин, по которым он пролегает.

Длина пути — количество рёбер в пути.

Цепь — маршрут без повторяющихся рёбер.

Простая цепь — цепь без повторяющихся вершин.

Цикл или Контур — цепь, в котором последняя вершина совпадает с первой.

Длина цикла — количество рёбер в цикле.

Самый короткий цикл — это петля.

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

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

Взвешенный граф — граф, в котором у каждого ребра и/или каждой вершины есть “вес” — некоторое число, которое может обозначать длину пути, его стоимость и т. п. Для взвешенного графа составляются различные алгоритмы оптимизации, например поиск кратчайшего пути.

Пока ещё не придуман алгоритм, который за полиномиальное время нашёл бы кратчайший цикл Гамильтона в полном нагруженном графе, однако есть несколько приближённых алгоритмов, которые за приемлимое время находят если не кратчайший, то очень короткий цикл, эти алгоритмы мы также рассматриваем на курсе Отуса — “Алгоритмы и структуры данных”.

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

Дерево — связный граф без циклов.

Между любыми двумя вершинами дерева существует единственный путь.

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

Лес — граф, в котором несколько деревьев.

Ориентированный граф или Орграф — граф, в котором рёбра имеют направления.

Дуга — направленные рёбра в ориентированном графе.

Полустепень захода вершины — количество дуг, заходящих в эту вершину.

Исток — вершина с нулевой полустепенью захода.

Полустепень исхода вершины — количество дуг, исходящих из этой вершины

Сток — вершина с нулевой полустепенью исхода.

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

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

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

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

Это только основные термины и определения теории графов, которые мы рассматриваем на первом вебинаре модуля “Теория графов”. Цель статьи — дать наглядное и понятное представление об этих терминах, для чего и были нарисованы эти картинки.

Основные понятия теории графов

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

Степень вершины

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

Степенью вершины называется число ребер графа, которым принадлежит эта вершина . Вершина называется четной , если ее степень — число четное. Вершина называется нечетной , если ее степень — число нечетное. Две вершины графа называются смежными , если существует соединяющее их ребро , то есть ребро вида и называются инцидентными этому ребру , а ребро — инцидентным этим вершинам . Аналогично, два различных ребра графа называются смежными, если они имеют, по крайней мере, одну общую вершину. Иначе можно определить степень вершины . Степенью или валентностью вершины графа называется число ребер, инцидентных ; степень вершины будем обозначать через . При вычислении степени вершины будем учитывать петлю в два раза, а не один. Вершина степени называется изолированной вершиной , вершина степени называется висячей , или концевой , вершиной. Граф , у которого все вершины имеют одну и ту же степень, называется регулярным графом .

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

2. Количество нечетных вершин любого графа четно.

3. Во всяком графе с вершинами, где , всегда найдутся по меньшей мере две вершины с одинаковыми степенями.

4. Если в графе с вершинами в точности две вершины имеют одинаковую степень, то в этом графе всегда найдется либо в точности одна вершина степени , либо в точности одна вершина степени .