Студопедия

КАТЕГОРИИ:

АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника


Полные графы. Двудольные графы. Однородные и реберные графы




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

Полный неориентированный граф с n вершинами обозначается Kn.

К5:
К4:
К3:

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

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

 

Пример:

G:

 

Матрица смежности дополнительного графанаходится по формуле:

A ( ) = J – A (G)

где J – матрица смежности полного графа, состоящая полностью из единиц, за исключением элементов диагонали.

Определение: Двудольнымграфом G = (V, X) называется граф, вершины которого разбиты на два пересекающихся класса, т. е.: V = V1 V2, V1∩V2 = Ø, а ребра связывают вершины только из разных классов – не обязательно все пары.

 

Определение: Если в двудольном графе каждая из вершин класса V1 связана с каждой из вершин класса V2, то граф называется полным двудольным и обозначается Km,n , где m – количество вершин первого класса (множество V1), n – количество вершин второго класса (V2). Граф Km,n содержит (m + n) вершин и m·n ребер.

 

К3,2 K3,3 Двудольный

 

Определение: Пусть G = (V, X) V = {v1,v2…,vn}. Если вершины графа имеют одинаковую степень δ(vi) = s для всех i { 1, 2, …, n}, то такой граф называется однородным(регулярным).

Теорема 1: Пусть дан однородный граф G = (V, X), V = {v1,v2…,vn}, тогда:

δ(vi) = n·s;

где n – количество вершин; m – количество ребер; s – степень каждой вершины.

 

Полный граф является однородным.

Теорема 2: Степень каждой вершины полного графа Kn на 1 меньше числа вершин, т. е. s = n – 1

Теорема 3: Если полный граф имеет n вершин, то

Для однородного графа G матрицы смежности и инцидентности связаны соотношением:

A(G) = B(G)· BT(G) – s·E, где

BT(G) – транспонированная матрица инцидентности B(G);

s – степень вершины v однородного графа;

Е – единичная матрица.

Определение: Граф Gp называется реберным, если в качестве вершин его выбраны ребра исходного графа G с m ребрами и n вершинами, имеющего матрицу инцидентности B(G).

В этом случае матрица смежности реберного графа находится по формуле: A (Gp) = BT(G) · B(G) – 2E

Исходный граф G для построения реберного графа Gp необязательно должен быть регулярным. Если все же граф G является регулярным, то и реберный Gp тоже будет регулярным. В общем случае, если ребро xi в графе G ограничено вершинами vj и vk , степень которых равна δ(vj) и δ(vk) , то степень вершины xiв реберном графе Gp определяется по формуле:

δ(xi) = δ(vj) + δ(vk) – 2

Число ребер в реберном графе Gp определяется по формуле:

m’ = δ2(vi) – m = δ(xi)


Поделиться:

Дата добавления: 2015-01-29; просмотров: 277; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.006 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты