Сколько ребер в полном графе

Сколько ребер в полном графе

Пишу лабу где нужно подсчитать кол-во циклов в графе
решил протестировать ее для полного графа — выходит очень много циклов
Есть ли зависимость кол-ва циклов в полном графе без петель для фиксированного
числа вершин?
Если известно сколько циклов в графах с небольшим кол-вом вершин (5. 10)
напишите

Marina Molchanova
2004-04-26 14:38:15 UTC

KV> Пишу лабу где нужно подсчитать кол-во циклов в графе

тебе нужно количество _всех_ циклов? Или количество независимых? Или
циклов без «поперечных мостиков»? Или вообще что?

KV> решил протестировать ее для полного графа — выходит очень много циклов

Для полного графа эта задача вообще решается без программы. Согласно
формуле Эйлера (легко доказываемой при любой погоде) количество
_независимых_ циклов в любом графе равно Р — В + К, где Р — число
ребер, В — число вершин, а К — число компонентов (в твоем случае
всегда 1). Число ребер в полном графе будет В*(В-1)/2. Вот и считай.

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

Konstantin Vasilyev
2004-04-26 18:40:59 UTC

MM> тебе нужно количество _всех_ циклов? Или количество независимых? Или
MM> циклов без «поперечных мостиков»? Или вообще что?

MM> Для полного графа эта задача вообще решается без программы. Согласно
MM> формуле Эйлера (легко доказываемой при любой погоде) количество
MM> _независимых_ циклов в любом графе равно Р — В + К, где Р — число
MM> ребер, В — число вершин, а К — число компонентов (в твоем случае
MM> всегда 1). Число ребер в полном графе будет В*(В-1)/2. Вот и считай.

MM> Число _всех_ циклов в полном графе будет считаться чуть сложнее, но
MM> опять же, легко должна выводиться аналитическая формула. Хотя бы
MM> по индукции.

А вот такой граф сколько имеет циклов?

Если считать что циклов: 2 как такой граф будет называться?

Сколько ребер в полном графе

Задача 1: Сколько рёбер в полном графе с 20 вершинами?

Решение: 190

Задача 2: Сколько всего рёбер в графе, степени вершин которого равны 3, 4, 5, 3, 4, 5, 3, 4, 5 ?

Решение: 18

Задача 3: В дереве имеется 100 вершин степени 5, 100 вершин степени 3, а остальные – висячие. Сколько висячих вершин в этом дереве?

Решение: 402

Задача 4: Какое число рёбер нужно убрать из полного графа с 15 вершинами, чтобы оставить его скелет?

Решение: 91

Задача 5: Какое минимальное количество рёбер нужно убрать из полного графа с 15 вершинами, чтобы он перестал быть связным?

Решение: 14

Задача 6: Лес состоит из 10 деревьев. Всего в лесу 200 вершин. Сколько в нем рёбер?

Решение: 190

Задача 7: Однажды Рома сказал: «Если степень каждой вершины 100-вершинного графа не меньше N, то этот граф связен». При каком наименьшем значении N Рома сможет это доказать, если известно, что его не зря взяли в профи?

Решение: 50

Задача 8: Из нескольких кусочков проволоки спаяна проволочная решетка 8 × 8 клеток. Какое наименьшее число кусочков для этого могло потребоваться?

Решение: 14

Задача 9: Во дворе живут 4 пёсика: Бобик, Робик, Тобик и Толстолобик. Каждому из них случалось драться с кем-нибудь из остальных, причём у Бобика, Робика и Тобика число тех, с кем они дрались – разное. Со сколькими собаками двора дрался Толстолобик?

Решение: 2

Задача 10: В стране 6 городов. Авиасообщение осуществляют несколько авиакомпаний. Каждая обслуживает 3 авиалинии, связывающие попарно некоторые три города (между двумя городами могут летать самолеты нескольких компаний). Каждые два города связаны по крайней мере одной линией. При каком наименьшем числе компаний это возможно?

Решение: 6

Задача 11: Каждое ребро графа покрасили в синий или зелёный цвет так, что ни из одной вершины не выходит двух одноцветных рёбер. Синих рёбер оказалось на 5 больше, чем зелёных. Какое наименьшее число компонент связности может иметь этот граф?

Решение: 5

Задачная база >> Разное >> Материалы Кировской ЛМШ, 2001 г, 7 класс >> Тест по графам

Убрать решения

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

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

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

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

Сумма входящих и исходящих степеней всех вершин ориентированного графа — чётное число, равное удвоенному числу рёбер:
[math]\sum\limits_ deg^\ v \; + \sum\limits_ deg^\ v=2\cdot |E(G)| [/math]

[math]deg^<->+deg^=10=2\cdot |E|[/math]

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

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

Пример бесконечного графа, в котором не выполняется лемма

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

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

Регулярный граф

Определение:

Граф называется регулярным, если степени всех его вершин равны.

В регулярном графе с [math] n [/math] вершинами ровно [math]\frac [/math] рёбер.

Если степень каждой вершины нечётна и равна [math] k[/math] , то количество рёбер кратно [math] k [/math] .

Регулярный граф с [math]\frac = \frac=9 [/math] рёбрами

Источники информации

• Lecture Notes on Graph Theory By Tero Harju, Department of Mathematics University of Turku, 2011 — с. 7-8
• Handshaking lemma — Wikipedia

Характеристики графа

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

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

G ( X , T ) Полный граф

Определение 3. Степенью вершины x_i графа G ( X , T ) называется число d_i , равное количеству ребер графа, инцидентных этой вершине. Вершина называется четной (нечетной), если ее степень — четное (нечетное) число.

Теорема 1. Если конечный граф G ( X , T ) (без петель) имеет n вершин и m ребер, то

Доказательство. Рассмотрим граф

Очевидно, что d ₁ =3, d ₂ =2, d ₃ =2, d ₄ =3. Сложим эти числа:
d ₁ + d ₂ + d ₃ + d ₄ =10. В этой сумме каждое ребро участвует дважды: 10:5=2.

Рассмотрим произвольный граф G ( X , T ) . Каждая вершина графа x _i инцидентна d _i ребрам. Если сложить эти величины по всем вершинам, то в полученной сумме каждое ребро будет участвовать дважды, т.е. эта сумма будет равна 2 m .

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

Доказательство. Так как левая часть равенства (1) является четным числом, то нечетных вершин должно быть четное число.

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

Доказательство. Предположим противное — все вершины имеют разные степени: 0, 1, 2, …, n — 1. Но если в графе есть вершина степени 0, то не может быть вершины со степенью n — 1. Получено противоречие.

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