> 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 вершин називається квадратна бінарна матриця А (G) n x n , c нулями на діагоналі. Число одиниць в рядку дорівнює ступеня відповідної вершини. p> Матрицею інціденцій орієнтованого графа G (X, U) називається прямокутна матриця порядку [m x n] n - потужність множини Х, m - потужність множини U. Кожен елемент якої визначається наступним чином:
1, якщо х i - початок дуги U j
a ij = -1, якщо х i - кінець дуги U j
0, якщо х i - не інцидентна дузі U j
В
Приклад.
Побудуємо матриці суміжності (М1) і інціденцій (М2) для графа G (X, U) (рис 2.1). br/>В
Рис 2.1
Додаткова матриця графа G (X, U) являє собою квадратну матрицю А 1 , яка виходить з матриці суміжності цього графа шляхом заміни всіх нулів одиницями і навпаки.
Дерева і прадеревья
В
Деревом називається неорієнтоване зв'язний граф з числом вершин не менше двох, що не містить петель і циклів. Вершини, інціден...
