Предыдущая страница реферата | 1  2  3  4  5  6  7  8 | Следующая страница реферата

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

Подмножества графов

Подграфом графа  G(X,U) называется граф G(A,UA), определяемый следующим образом:

1. Вершинами A  подграфа G(A,UA)   является некоторое подмножество вершин графа G(X,U);

2. Отображением каждой вершины подграфа является пересечение отображения той же вершины в графе G(X,U) со всем подмножеством вершин A подграфа G(A,UA).

Частичным графом для графа G(X,U) называется граф G(X,U), в котором содержатся все вершины и некоторое подмножество дуг исходного графа.

Частичный подграф - это частичный граф от подграфа.

Фактором графа G(X,U) называется частичный граф G(X,U), в котором  каждая вершина обладает полустепенями исхода и захода, равными единице,  имеются одна заходящая и одна исходящая дуги.

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

Связность графа

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

Операции над графами

1. Объединение графов

G3(X3,Гх3) = G1(X1,Г1х1) È G2(X2,Г2х2), где  X3=X1ÈX2, а Гx3=Г1x1ÈГ2x2

Пример (Рис 1.1).

Рис 1.1

2.  Пересечение графов

G3(X3,Гх3) = G1(X1,Г1х1) ÇG2(X2,Г2х2), где  X3=X1Ç X2, а Гx3=Г1x1ÇГ2x2

Пример (рис 1.2).

Рис 1.2

4. Прямое (декартово) произведение графов.

Прямым произведением множеств Х{x1.......xn} и Y  называется множество Z, элементами которого являются всевозможные пары вида xi , yj , где xiÎX, yjÎY. Обозначают:  Z=X x Y.

G3(X3,Гх3) = G1(X1,Г1х1) Ç G2(X2,Г2х2), где  X3=X1ÇX2, а Гx3=Г1х1ÇГ2х2

Пример. (рис 2.3)

G1(X,Гх)=G1(X1,Гх1)                                           G2(Y,Гy)= G2(X2,Гх2)

X={x1 x2 x3 }                                                           Y={y1 y2} 

Гх1=0                                                                       Гу1={y1 y1}

Гх2={x1 x3}                                                               Гу2={y1}

Рекомендуем скачать другие рефераты по теме: рассказы, древняя греция реферат.



Предыдущая страница реферата | 1  2  3  4  5  6  7  8 | Следующая страница реферата

Поделитесь этой записью или добавьте в закладки