Как посчитать количество ребер в графе

Как посчитать количество ребер в графе

Предположим, что футбольная команда вашей школы участвует в соревнованиях и играет с командами других школ. Пусть общее число команд равно шести. Вашу команду обозначим буквой А, а другие команды — буквами B, C, D, E и F. Через несколько недель после начала соревнований окажется, что не­которые из команд уже сыграли друг с другом, например:
A с C, D, F;
B c C, E, F;
С с A, B;
D с A, E, F;
E с B, D, F;
F с A, B, D.

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

Схема такого вида называется графом. Она состоит из нескольких точек А, В, С, D, E, F,называемых вершинами, и нескольких соединяющих эти точки отрезков, таких, как АС или ЕВ, называемых ребрами графа.

Итак, фигуру, образованную набором точек и отрезков, соединяющих некоторые из этих точек, называется графом. Точки называются вершинами графа. А отрезки – ребрами графа.

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

Из рис. 5 видно, что точки пересечения некоторых ребер графа могут не являться его вершинами; это происходит потому, что мы изобразили наш граф на плоскости. Возможно, удобнее было бы представлять себе его ребра нитями, проходящими друг над другом в пространстве; во всяком случае, при изображении на плоскости вершины графа во избежание путаницы должны отмечаться достаточно отчетливо (например, кружочками).

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

рис. 6

Задача 1.1. Рассмотрим следующие рисунки. Изображают ли они один и тот же граф?
А)

1. Проверим число вершин на графах.
В первом графе три вершины, а во втором четыре, следовательно, графы разные.
B)

1. Проверим число вершин на графах.
В первом и во втором графе по четыре вершины.

2. Проверим, соединены ли ребрами соответствующие вершины графа.
Вершина А в первом графе соединена только с вершиной В. А во втором графе вершина А соединена еще и с вершиной D. Следовательно графы разные.

Задача 1.2. Аркадий, Борис, Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу). Сколько всего рукопожатий было сделано?
Решение:
Пусть каждому из пяти молодых людей соответствует определенная точка на плоскости, названная первой буквой его имени, а производимому рукопожатию – отрезок или часть кривой, соединяющая конкретные точки – имена.
Рассмотрим процесс соединения точек А, Б, В, Г, Д ребрами.
1. Ситуация, соответствующая моменту, когда рукопожатия еще не совершались, представляет собой точечную схему, изображенную на рис 3. Такую схему называют нулевым графом.

Рис 9. Рис 10.
2. Ситуация, соответствующая моменту, когда совершены еще не все рукопожатия, может схематически быть изображена, например, с помощью рис. 10.
Графы, в которых построены не все возможные ребра, называются неполными графами.
3. На рис. 9 Борис не сделал ни одного рукопожатия. Вершины, которые не принадлежат ни одному ребру, называются изолированными.
Теперь мы можем тать четкое определение нулевому графу. Схема, состоящая из «изолированных» вершин, называется нулевым графом.
4. Ситуация, когда осуществились все рукопожатия, изображена на рис. 11. В нем каждая из вершин соединена с каждой из оставшихся. Этот граф называется полным графом.

Рис 11.
Если мы подсчитаем число ребер графа, изображенного на рис. 11, то это число и будет равно количеству совершенных рукопожатий между пятью молодыми людьми. Их 10.
Заметим, что граф, не являющийся полным, можно дополнить до полного с теми же вершинами, добавив недостающие ребра. Так на рис. 10 изображен неполный граф с пятью вершинами. А на рис. 11 граф превращен в полный. Ребра, превращающие граф в полный изображены фиолетовым цветом. Совокупность вершин графа с этими ребрами называется дополнением графа.
Предложение 1. Докажем, что если полный граф имеет n вершин, то количество ребер будет равно: .
Действительно, всего вершин n штук, каждая соединена с n-1 вершиной – получаем произведение n(n-1). Но мы посчитали каждое ребро два раза, значит, надо произведение разделить на два, и тогда получим искомую формулу для нахождения количества ребер.
Задача 1.3. Существует ли полный граф с семью ребрами?
Решение. Допустим, что такой граф существует.
Зная количество ребер, узнаем количество вершин.
=7; n(n-1)=14.

Заметим, что n и (n-1) – это два последовательных натуральных числа. Число 14 не6льзя представить в виде произведения двух последовательных натуральных чисел, значит, данное уравнение не имеет решений. Следовательно, такого графа не существует.

Как посчитать количество ребер в графе

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

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

Задачи

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 друзей?

Подсчет количества ребер и вершин при операциях над графами

Над графами, как и над другими математическими объектами, можно производить ряд операций. Рассмотрим основные из них.

Удаление вершины. Пусть б= (Е, Ц) — граф и у є V. Удалить вершину у из графа б — значит построить новый граф б’ = (У’, (/’), в котором V’ = У <г>и и’ получается из б удалением всех ребер, инцидентных вершине V.

Удаление ребра. Пусть б = (V, б) — граф и и є и. Удалить ребро и — значит построить новый граф б’ = (V’, б’), в котором У’= Уи и’=и<и>.

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

Объединение графов. Пусть даны два графа = (6(6]), 6(6,)), б₂ = (У(С₂), б(б₂)), причем множества Е(б[), б(б₂) не пересекаются. Пусть У(в_х) = п_<, |б(б₂)| = п₂, |б(б|)| = т|, |б(б₂)| = т₂. Объединением графов (7[, б₂ называется граф б = и б₂ с множеством вершин У(Оі) и б(б₂) И семейством ребер б(б,) и б(б₂).

Сложение графов. Пусть даны два графа б, = (6(6,), 6(6^), б₂ = (б(б₂), б(б₂)), причем множества Е(б[), б(б₂) не пересекаются. Тогда суммой графов б_1; б₂ называется граф б = б₁ + б₂, полученный как их объединение, при этом каждая вершина б] соединяется ребром с каждой вершиной графа б₂.

Если множества У(С_Х), б(б₂) пересекаются, т.е. исходные графы имеют общие вершины, операции объединения и сложения осуществляются так же, за исключением того, что общие вершины склеиваются или сливаются в одну единую вершину. Если общие вершины в двух исходных графах соединены ребром, то эти ребра тоже склеиваются. При операции сложения общие (склеенные) вершины не участвуют в построении новых ребер.

Задача 2.5. Для графов б), б₃, б₅ (рис. 2.4) определить число вершин и ребер, а также нарисовать граф, получаемый в результате операции объединения этих трех графов при отсутствии общих вершин.

Рис. 2.4. Условие для задач 2.5—2.13

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

Задача 2.6. Для графов б₂ и б₅ (см. рис. 2.4) определить число вершин и ребер, а также нарисовать граф, получаемый в результате операции объединения этих двух графов при условии, что они имеют одну общую вершину.

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

Результирующий граф будет представлять из себя присоединение ребра, инцидентного общей вершине в графе б₅, к общей вершине в графе б₂. Результат объединения двух графов представлен на рис. 2.5.

Рис. 2.5. Решение задачи 2.6

Характеристики графа: количество вершин — 10, ребер — 8.

Задача 2.7. Для графов б₄ и б₃ (см. рис. 2.4) определить число вершин и ребер, а также нарисовать графы, получаемые в результате операции объединения этих двух графов при условии, что у них одна общая вершина степени 3.

Задача 2.8. Для графов б₄ и б₅ (см. рис. 2.4) определить число вершин и ребер, а также нарисовать графы, получаемые в результате операции объединения этих двух графов при условии, что у них три общие вершины степени 1.

Задача 2.9. Для графов б] и б₅ (см. рис. 2.4) определить число вершин и ребер, а также нарисовать графы, получаемые в результате операции сложения этих двух графов при отсутствии общих вершин.

Задача 2.10. Для графов б[ и б₂ (см. рис. 2.4) определить число вершин и ребер, а также нарисовать графы, получаемые в результате операции сложения этих двух графов при отсутствии общих вершин.

Задача 2.11. Для графов б, и б₃ (см. рис. 2.4) определить число вершин и ребер, а также нарисовать графы, получаемые в результате операции сложения этих двух графов при условии, что у них две общие вершины степени 2, несмежные в обоих графах.

Задача 2.12. Для графов и б₃ (см. рис. 2.4) определить число вершин и ребер, а также нарисовать графы, получаемые в результате операции сложения этих двух графов при условии, что у них три общие вершины, попарно несмежные в обоих графах.

Задача 2.13. Для графов б₃ и б₃ (см. рис. 2.4) определить число вершин и ребер, а также нарисовать графы, получаемые в результате операции сложения этих двух графов при условии, что у них три общие вершины, попарно несмежные в обоих графах.

Задача 2.14. Сколько вершин и ребер имеет:

• а) дополнение графа К_{8 5};
• б) дополнение графа АГ₁₂?

Задача 2.15. Какое максимальное число ребер имеет:

• а) двудольный граф с долями 6 и 11;
• б) произвольный граф на семи вершинах?

Задача 2.16. Сколько вершин и ребер имеет граф, полученный в результате объединения регулярного графа степени 3 на восьми вершинах и полного графа К₉‘?

• а) графы не имеют общих вершин;
• б) графы имеют одну общую вершину

Задача 2.17. Сколько вершин и ребер имеет граф, полученный в результате сложения регулярного графа степени 3 на восьми вершинах и полного графа К₉?

• а) графы не имеют общих вершин;
• б) графы имеют одну общую вершину.

Задача 2.18. Сколько вершин и ребер имеет граф, полученный в результате объединения полного двудольного графа К_{7 8} и пустого графа на шести вершинах?

• а) графы не имеют общих вершин;
• б) графы имеют одну общую вершину.

Задача 2.19. Сколько вершин и ребер имеет граф, полученный в результате сложения полного двудольного графа К_{7 8} и полного графа на шести вершинах?

• а) графы не имеют общих вершин;
• б) графы имеют одну общую вершину.

Задача 2.20. Сколько вершин и ребер имеет граф, полученный в результате объединения регулярного графа степени 5 на десяти вершинах и полного графа К₄?

Количество ребер

Поскольку число ребер известно в теории графов , число ребер одного графа .

Если это рассматриваемый график, это число обычно отмечается (или кратко , если ясно, какой это график). Как вариант, вы также можете написать . г <\ displaystyle G>м ( г ) <\ displaystyle m (G)>м <\ displaystyle m>| | г | |

Содержание

определение

В случае неориентированных графов количество ребер данного графа — это количество его ребер или сумма кратных отдельных ребер, если это граф с несколькими ребрами. м ( г ) <\ displaystyle m (G)>г знак равно ( V , Э. )

Его также можно увидеть как толщину набора краев . | Э. | <\ displaystyle | E |>Э.

характеристики

• Применяется следующее: . Здесь клика число из ; количество узлов в самой большой клике . Равенство происходит с полными графами . м ( г ) ≥ Δ τ ( г ) — 1 знак равно τ ( г ) ( τ ( г ) — 1 ) 2 <\ Displaystyle м (G) \ geq \ Delta _ <\ тау (G) -1>= <\ гидроразрыва <\ тау (G) (\ тау (G) -1)><2>>> τ ( г ) <\ Displaystyle \ тау (G)>г <\ displaystyle G>г
• Также применяется

Расчет по матрице смежности

Если задана матрица смежности графа, очень легко определить количество ребер этого графа.

Матрица смежности имеет запись в -й строке и -м столбце для ребра, которое соединяет узлы и . Если график неориентированный, 1 также находится в -й строке и -м столбце. я <\ displaystyle i>j <\ displaystyle j>я <\ displaystyle i>j <\ displaystyle j>j <\ displaystyle j>я

Чтобы рассчитать количество ребер, вам просто нужно сложить все записи и разделить на 2. Эта процедура также работает для графов с несколькими ребрами.

Расчет для разных классов графиков

В следующем разделе всегда предполагаются простые графы , т. Е. Неориентированные графы без кратных ребер .

Полный график

м знак равно ( п 2 ) знак равно п ( п — 1 ) 2 знак равно Δ п — 1 <\ displaystyle m = = <\ frac <2>> = \ Delta _ > ,

так что число треугольника . Δ п — 1 <\ displaystyle \ Delta _ >

Это видно из того факта, что каждое ребро определяется двумя узлами, и есть варианты выбора двух узлов. ( п 2 ) <\ displaystyle <п \ выбрать 2>>

Деревья

У деревьев с узлами есть ребра по формуле Кэли . Это частный случай замены плоских графов многогранником Эйлера (см. Планарные графы). Класс графов деревьев также включает линейные графы и звездчатые графы . Звездообразный граф — это граф, центральный узел которого соединен со всеми остальными узлами. У других узлов есть только один сосед. п <\ displaystyle n>м знак равно п — 1

Планарные графики

Номер области применяется и есть . п знак равно | V | , м знак равно | Э. | <\ displaystyle n = | V |, m = | E |>л

Если вы решите уравнение для , вы получите м

Максимальные планарные графики

Максимально плоский граф представляет собой график , к которому могут быть добавлены никакие дальнейшие ребра. Если он имеет как минимум 3 узла, это треугольный граф, и каждая его область окружена 3 ребрами.

Количество ребер максимального плоского графа не менее чем с 3 узлами равно . м знак равно 3 п — Шестой

Регулярные графики

Для регулярного графа со степенями и узлами количество ребер равно k <\ displaystyle k>п

Это связано с тем, что ребра исходят из каждого узла ; Однако вы считаете каждое ребро дважды и поэтому должны делить на 2. k

Учитывая среднюю степень

Учитывая среднюю степень и количество узлов , количество ребер можно рассчитать следующим образом d ( г ) <\ displaystyle d (G)>п

Умножив на количество всех ребер в числителе; однако каждая из них считается дважды, поэтому она делится на 2. п

Эта формула является обобщением формулы для регулярных графов.

Двудольный граф

Если данный граф является двудольным графом , множество узлов которого можно разделить на два непересекающихся подмножества и , то для количества ребер может быть задан только один максимум. г <\ displaystyle G>V <\ displaystyle V>V 1 <\ displaystyle V_ <1>> V 2 <\ displaystyle V_ <2>>

Так что краев не больше. м знак равно | V 1 | ⋅ | V 2 | <\ Displaystyle m = | V_ <1>| \ cdot | V_ <2>|>

В общем случае максимальное количество ребер k-долевого графа с непересекающимися подмножествами равно г знак равно ( V , Э. ) <\ Displaystyle G = (V, E)>k <\ displaystyle k>V 1 , . , V k <\ Displaystyle V_ <1>, \ dotsc, V_ >

Здесь стоит за -й треугольное число . Формулу можно получить, посчитав, сколько ребер все еще отсутствует в полном графе . Δ k <\ displaystyle \ Delta _ > k

Поскольку каждое — узел-раскраска графа также -дольная, приведенная выше формула также может быть использована для -node-раскраски графов. k <\ displaystyle k>k <\ displaystyle k>k

Сетка графика

Сетки графы с узлами могут быть представлены в виде прямоугольника , в котором все ребра имеют одинаковую длину. г я , j <\ displaystyle G_ > п знак равно я ⋅ j

Количество ребер можно рассчитать, сначала посчитав внешние ребра, а затем добавив внутренние.

м 2 знак равно [ ( я — 2 ) ( j — 1 ) ] + [ ( я — 1 ) ( j — 2 ) ] знак равно я ⋅ j — я — 2 j + 2 + я ⋅ j — j — 2 я + 2 знак равно 2 я j — 3 я — 3 j + 4-й <\ Displaystyle <\ begin m_ <2>& = [(i-2) (j-1)] + [(i-1) (j-2)] \\ & = i \ cdot ji-2j + 2 + i \ cdot jj-2i + 2 \\ & = 2ij-3i-3j + 4 \ end >>

внутренние края. Вместе это приводит

м знак равно м 1 + м 2 знак равно ( 2 я + 2 j — 4-й ) + ( 2 я j — 3 я — 3 j + 4-й ) знак равно 2 я j — я — j <\ Displaystyle <\ begin m & = m_ <1>+ m_ <2>\\ & = (2i + 2j-4) + (2ij-3i-3j + 4) \\ & = 2ij-ij \ end <выровнено>>>

В качестве альтернативы вы можете сложить количество вертикальных и горизонтальных кромок и получить

Лестничные графики

Лестница графики имеют структуру лестницы. Он состоит из двух линейных графов равной длины (лонжероны), два соответствующих узла соединены ребром (перекладины).

Лестничный граф с узлами имеет ребра для стоек и ребра для ступенек , поэтому в целом Л. п <\ displaystyle L_ > 2 п <\ displaystyle 2n>2 п — 2 <\ displaystyle 2n-2>п

м знак равно 2 п — 2 + п знак равно 3 п — 2

Графики колес

Колесный граф состоит из кругового графа, к которому был добавлен еще один узел, связанный со всеми узлами. Граф колеса имеет узлы. С. п <\ displaystyle C_ > W. п <\ displaystyle W_ > п + 1

Количество ребер рассчитывается через W. п <\ displaystyle W_ >

Графики, возникающие друг из друга в результате операций

Двойные графики

Для данного графа , то двойственный граф создается путем замены каждой области с вершиной . Кроме того, ребра, от которых отделяются области, становятся ребрами, соединяющими новые узлы . г знак равно ( V , Э. ) <\ Displaystyle G = (V, E)>г ′ знак равно ( V ′ , Э. ′ ) <\ Displaystyle G '= (V', E ')>г <\ displaystyle G>г ′ <\ displaystyle G '>г <\ displaystyle G>г ′

Количество ребер остается неизменным при использовании этого метода, поэтому применяется следующее

Изоморфные графы

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

Следовательно, для двух изоморфных графов и г <\ displaystyle G>г ′

Графики дополнений

Дополнение графы графа называется граф , который имеет тот же набор узлов , как , но все ребра , которые делают не так . г знак равно ( V , Э. ) <\ Displaystyle G = (V, E)>г ′ знак равно ( V ′ , Э. ′ ) <\ Displaystyle G '= (V', E ')>V ′ <\ displaystyle V '>г <\ displaystyle G>г

Количество ребер дополнительного графа может быть вычислено в зависимости от количества ребер . г <\ displaystyle G>г

Стенды для числа из узлов . Формула выводится потому, что объединение двух наборов узлов образует полный граф. п ( г ) <\ Displaystyle п (G)>г

Реберные графы

Реберный граф графа возникает тогда , когда каждое ребро становится узлом . Затем узлы соединяются ребром, которое было смежным в. Л. ( г ) знак равно ( V ′ , Э. ′ ) <\ Displaystyle L (G) = (V ', E')>г знак равно ( V , Э. ) <\ Displaystyle G = (V, E)>г <\ displaystyle G>Л. ( г ) <\ Displaystyle L (G)>Л. ( г ) <\ Displaystyle L (G)>г

Формула для числа ребер могут быть получены из рассмотрения , что каждый узел из будет заменен ребер, соединяющих узлы, которые возникли вместо смежных ребер. Л. ( г ) <\ Displaystyle L (G)>v ∈ V <\ displaystyle v \ in V>г <\ displaystyle G>( d ( v ) 2 ) знак равно Δ d ( v ) — 1 <\ Displaystyle <\ tbinom <2>> = \ Delta _ >