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

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

В графе ребро, концы которого совпадают, то есть [math]e=(v, v)[/math] , называется петлей (англ. loop).

Два ребра, имеющие общую концевую вершину, то есть [math]e_1=(v, u_1)[/math] и [math]e_2=(v, u_2)[/math] , называются смежными (англ. adjacent).

Если имеется ребро [math] (v, u) \in E [/math] , то говорят:

• [math] v [/math] — предок (англ. direct predecessor) [math] u [/math] .
• [math] u [/math] и [math] v [/math] — смежные.
• Вершина [math] u [/math] инцидентна ребру [math] (v, u) [/math] .
• Вершина [math] v [/math] инцидентна ребру [math] (v, u) [/math] .

Инцидентность (англ. incidence) — понятие, используемое только в отношении ребра и вершины. Две вершины или два ребра не могут быть инцидентны.

Граф с [math] p [/math] вершинами и [math] q [/math] рёбрами называют [math] (p, q) [/math] -графом. [math] (1, 0) [/math] -граф называют тривиальным.

Заметим, что по определению ориентированного графа, данному выше, любые две вершины [math]u,

v[/math] нельзя соединить более чем одним ребром [math](u, v)[/math] . Поэтому часто используют другое определение.

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

Ориентированным графом [math]G[/math] называется четверка [math]G = (V, E, \operatorname, \operatorname)[/math] , где [math]V[/math] и [math]E[/math] — некоторые множества, а [math]\operatorname, \operatorname : E \rightarrow V[/math] .

Данное определение разрешает соединять вершины более чем одним ребром. Такие рёбра называются кратными (иначе — параллельные, англ. multi-edge, parallel edge). Граф с кратными рёбрами принято называть мультиграфом (англ. multigraph). Если в мультиграфе присутствуют петли, то такой граф называют псевдографом (англ. pseudograph).

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

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

Граф G задается с помощью пары множеств G = (V, R ), где V есть множество вершин, а R – множество линий, соединяющих пары вершин. Линии со стрелками называются дугами, без стрелок – ребрами. Обычно граф представляют с помощью схемы, на которой некоторые вершины соединены ребрами (дугами).

Вершинами могут служить объекты любой природы: будь то населенные пункты, компьютерные сети, элементы блок- схем алгоритмов. Под ребром могут подразумеваться дороги между соседними городами, линии связи между компьютерами.

Вершины называются смежными, если их соединяет ребро. Например, на рис. смежны вершины V₁ и V₂ , так как их соединяет ребро R₁₂ .

Множество V , R являются конечными – мы можем перечислить все вершины и ребра графа. Количество вершин и количество ребер графа определяют мощности множеств V и R . Так, количество вершин графа G ровно 5, а количество ребер равно 8.

Ребро и любая из его двух вершин называются инцидентными. Под степенью вершин подразумевается количество инцидентных ей ребер. Так, степень вершин V₁ равно 3, а степень вершин V ₅ равна 4.

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

Длина маршрута равна количеству ребер, входящих в него.

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

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

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

Взвешенные графы.

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

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

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

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

Допустим, что множество вершин графа можно разбить на два непересекающихся подмножества V₁ и V₂ , так, что каждое ребро в G соединяет какую-нибудь вершину из V₁ с какой-либо вершиной из V₂ , тогда G называем двудольным графом. Такие графы иногда обозначают G( V₁ , V₂ ) , если хотят выделить два указанных подмножества. Двудольный граф можно определить и по-другому: в терминах раскраски его вершин двумя цветами, скажем, красным и синим. При этом граф называется двудольным, если каждую его вершину можно окрасить красным или синим цветом так, чтобы любое ребро имело один конец красный, а другой — синий. Следует подчеркнуть, что в двудольном графе совсем не обязательно каждая вершина из V₁ соединена с каждой вершиной из V₂ ; если же это так и если при этом граф G простой, то он называется полным двудольным графом и обычно обозначается K_m,n , где m, n — число вершин соответственно в V₁ и V₂ .

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

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

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

На рисунке показано плоское представление графа G с тремя гранями: (1, 5,4,1), (1, 3, 2,4,1) , (1,2,3,1). Часть плоскости, ограниченная простым циклом (1,2,4,1), гранью не является, так как содержит цикл (1, 2, 3,1). Простой цикл, ограничивающий грань, называется границей грани. Две грани будем называть соседними, если их границы имеют хотя бы одно общее ребро.

В данном графе часть плоскости, ограниченная простым циклом (1,2,3,4,1), является гранью, так как ребро (4,5), расположенное внутри грани, не образует цикла.

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

В качестве грани можно рассматривать и часть плоскости, расположенную «вне» плоского представления графа. Она ограничена «изнутри» простым циклом и не содержит других циклов. Эту часть плоскости называют бесконечной гранью.

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

Два графа гомеоморфны (или тождественны с точностью до вершин степени 2), если они оба могут быть получены из одного и того же графа «включением» в его ребра новых вершин степени 2.

Гомеоморфные графы

Элементарным стягиванием называется такая процедура: берем ребро е (вместе с инцидентными ему вершинами, например, V и W ) и»стягиваем» его, то есть удаляем е и отождествляем V и W . Полученная при этом вершина инцидентна тем ребрам (отличным от е ), которым первоначально были инцидентны V или W .

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

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

Формула Эйлера

Для всякого плоского представления связного плоского графа без перегородок число вершин ( V ), число ребер ( Е ) и число граней с учетом бесконечной ( R ) связаны соотношением V –Е + R = 2 .

Пусть граф G — связный, плоский граф без перегородок. Определим значение алгебраической суммы V –Е + R для его произвольного плоского представления.

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

Заметим, что при таком удалении одного ребра число граней уменьшается на 1, так как при этом либо пропадет один простой цикл, либо два простых цикла преобразуются в один. Следовательно, значение разности Е — R при этом остается неизменным.

На рисунке ребра, которые мы удаляем, изображены кривыми. В полученном дереве обозначим число вершин — V_d , число ребер — E_d , число граней — R_d . Справедливо равенство Е — R = E_d — R_d .

В дереве одна грань, то есть Е — R = E_d — 1. Операция удаления ребер из графа не меняет число его вершин, то есть V = V_d . По теореме в дереве V_d — E_d = 1. Отсюда V — E_d = 1, то есть E_d = V — 1, а потому Е- R = V — 2 или V — Е + R = 2.

Итак, доказано, что если в плоском представлении связного графа без перегородок V вершин, Е ребер и R граней, то V — Е + R = 2 . Полученная формула называется формулой Эйлера.

Полный граф

вершинами имеет рёбер и обозначается . Является регулярным графом степени .

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

Примеры

Ниже приведены полные графы с числом вершин от 1 до 12 и количества их рёбер.

K1: 0	K2: 1	K3: 3	K4: 6
K5: 10	K6: 15	K7: 21	K8: 28
K9: 36	K10: 45	K11: 55	K12: 66

• Теория графов

Wikimedia Foundation . 2010 .

Полезное

Смотреть что такое «Полный граф» в других словарях:

ГРАФ ПЛОСКИЙ — планарный граф, граф, допускающий правильную укладку на плоскости (см. Графа укладка). Иными словами, граф G наз. плоским, если он может быть изображен на плоскости так, что вершинам соответствуют различные точки плоскости, а линии,… … Математическая энциклопедия

ГРАФ СЛУЧАЙНЫЙ — вероятностная модель, предназначенная для изучения частотных характеристик различных параметров графов. Под Г. с. обычно понимается нек рый класс графов на к ром задано распределение вероятностей. Произвольный конкретный граф Gиз наз. реализацией … Математическая энциклопедия

ГРАФ ЭКСТРЕМАЛЬНЫЙ — граф, на к ром та или иная числовая характеристика принимает свое минимальное или максимальное значение. Обычно отыскиваются экстремальные значения нек рой одной числовой характеристики при ограничениях на другие числовые характеристики и… … Математическая энциклопедия

Граф — Граф: От древневерхненемецкого gravo, gravio «предводитель, вождь»: Граф (титул)  дворянский титул; «Граф»  короткометражная немая кинокомедия Чарли Чаплина (The Count, 1916). От греч. γράφω «царапаю, черчу, пишу»: Граф… … Википедия

Граф Шпее — Тяжёлый крейсер «Адмирал граф Шпее» Graf Spee Schwerer Kreuzer Тяжёлый крейсер «Адмирал граф Шпее» на Спитхедском морском параде 1937 г. Основная информация … Википедия

ГРАФ — множество Vвершин и набор Енеупорядоченных и упорядоченных пар вершин; обозначается Г. через . Неупорядоченная пара вершин наз. ребром, упорядоченная пара дугой. Г., содержащий только ребра, наз. неориентированным; Г., содержащий только дуги,… … Математическая энциклопедия

Граф Шарль д’Артуа — Карл X Charles X … Википедия

ГРАФ ДВУДОЛЬНЫЙ — бихроматический граф, граф, множество вершин к рого можно разбить на два непересекающихся подмножества и , (т … Математическая энциклопедия

Планарный граф — Планарный граф  граф, который может быть изображен на плоскости без пересечения ребер. Более строго: Граф укладывается на некоторой поверхности, если его можно на ней нарисовать без пересечения ребер. Уложенный граф называется геометрическим … Википедия

Плоский граф — Планарный граф граф, который может быть изображен на плоскости без пересечения ребер. Более строго: Граф укладывается на некоторой поверхности, если его можно на ней нарисовать без пересечения ребер. Уложенный граф называется геометрическим, его … Википедия