фів
G 3 (X 3 , Гх 3 ) = G 1 (X 1 , Г1х 1 ) Г‡ G 2 ( X 2 , Г2х 2 ) , де X 3 = X 1 Г‡ X 2 , а Гx 3 = Г1x 1 Г‡ Г2x 2
Приклад (рис 1.2).
Рис 1.2
4. Пряме (декартово) твір графів.
Прямим твором множин Х {x 1 ....... x n } і Y називається безліч Z, елементами якого є всілякі пари виду x i , y j , де x i ГЋX, y j ГЋY. Позначають: Z = X x Y.
G 3 (X 3 , Гх 3 ) = G 1 (X 1 , Г1х 1 ) Г‡ G 2 ( X 2 , Г2х 2 ) , де X 3 = X1 Г‡ X2, а Гx 3 = Г1х1 Г‡ Г2х2
Приклад. (Рис 2.3)
G 1 (X, Гх) = G 1 (X 1 , Гх 1 ) G 2 (Y, Гy) = G 2 (X 2 , Гх 2 )
X = {x 1 x 2 x 3 } Y = {y 1 y 2 }
Гх 1 = 0 Гу 1 = {y 1 y 1 }
Гх 2 = {x 1 x 3 } Гу 2 = {y 1 }
Гх 3 = 0
Z = X x Y = {x 1 y 1 , x 1 y 2 , x 2 y 1 , x 2 y 2 , x 3 y 1 , x 3 y 2 }
Z = {z 1 z 2 z 3 z 4 z 5 z 6 }
В
Рис 2.3
7. Розширення графа. p> Розширення графа - це перетворення, лінії, що з'єднує будь-які дві вершини графа в елементарний шлях введенням нових проміжних вершин на цій лінії.
8. Стиснення графа. p> Стиснення графа - це перетворення елементарного шляху, що з'єднує дві будь-які вершини графа, в лінію. br/>
9. Стягання графа. p> Якщо граф містить вершини Х 1 і Y 1 , то операцією стягання називається виключення всіх дуг між вершинами Х 1 і Y 1 і перетворення всіх вершин в одну загальну вершину Х.
Деякі числа теорії графів
Нехай існує мультіграф з b вершинами, p ребрами, і R компонентами зв'язності, тоді цикломатичне число мультіграф визначається рівністю:
V = p-b + R
Матриці для графів
В
Матрицею суміжності графа G (X, Гх) , містить n ...
