4760
.pdf
21
Рис. 23
Матрица инцидентности имеет вид: |
|
|
|
|
|
|
|
u1 |
u2 |
u3 |
u4 |
|
|
х1 |
|
1 |
1 |
0 |
0 |
|
В х2 |
|
1 |
0 |
1 |
0 |
|
|
. |
|||||
х |
|
0 |
1 |
1 |
1 |
|
3 |
|
|
|
|
|
|
х4 |
|
0 |
0 |
0 |
1 |
|
|
|
|||||
Пример 3. Построить матрицы смежности и инцидентности для графа G (рис.
24).
Рис. 24
22
Решение. Составим матрицы смежности и инцидентности для заданного графа
G.
Матрица смежности имеет вид:
|
|
x1 |
x1 |
|
0 |
А x2 |
|
0 |
|
||
x |
|
0 |
3 |
|
|
|
|
|
x4 |
0 |
|
x5 |
|
0 |
|
||
Матрица инцидентности имеет вид:
x2 |
x3 |
x4 |
x5 |
|
1 |
1 |
0 |
0 |
|
|
|
|
|
|
0 |
1 |
0 |
0 |
. |
0 |
0 |
1 |
0 |
|
|
|
|
|
|
0 |
0 |
0 |
1 |
|
0 |
1 |
0 |
0 |
|
|
|
u1 |
u2 u3 u4 u5 u6 |
|||||||
x |
|
1 |
1 |
0 |
0 |
0 |
0 |
|
|
1 |
|
|
|
|
|
|
|
|
|
B x2 |
|
1 |
0 |
1 0 |
0 |
0 |
|
||
x3 |
|
0 |
1 |
1 |
1 |
1 |
0 |
. |
|
|
|
||||||||
x |
|
0 |
0 |
0 |
0 |
1 |
1 |
|
|
4 |
|
|
|||||||
|
|
|
|
|
|
||||
x5 |
|
|
|
|
|
|
|||
|
0 |
0 |
0 |
1 0 |
1 |
||||
Пример 4. Изобразить орграф G , если его матрица смежности имеет вид:
|
1 |
0 |
0 |
1 |
1 |
|
|
0 |
0 |
0 |
0 |
0 |
|
|
|
|||||
А |
1 |
1 |
0 |
1 |
0 |
. |
|
|
|
|
|
|
|
0 |
0 |
0 |
0 |
0 |
|
|
|
0 |
1 |
1 |
0 |
0 |
|
|
|
|||||
Решение. Орграф G с такой матрицей смежности представлен на рис. 25.
23
Рис. 25
Пример 5. Найти два разных остовных дерева в графе G (рис. 26).
Рис. 26
Решение. В этом графе существует несколько остовных деревьев.
Одно из них получается последовательным выбором ребер: а, в, d и f. Другое - в, c, e и g.
Названные деревья показаны на рис. 27.
Рис. 27
24
Пример 6. Построить кратчайший остов графа, представленного на рис. 28.
Рис. 28
Решение.
1.Изобразим отдельно все семь вершин заданного графа.
2.Перечислим все ребра графа в порядке не убывания их длин (см. табл. 2):
|
Таблица 2 |
Длина ребра |
Ребра |
|
|
1 |
x1,x2 , x5,x7 |
|
|
2 |
x2,x7 , x3,x7 , x3,x5 |
|
|
3 |
x3,x4 , x5,x6 , x2,x6 |
|
|
4 |
x1,x6 , x4,x5 |
|
|
5 |
x2,x3 |
|
|
6 |
x6,x7 |
|
|
Заданный граф имеет семь вершин, поэтому кратчайший его остов, согласно алгоритму Краскала, будет состоять из шести ребер, представленных на рис. 29.
25
Рис. 29
Отметим, что сначала при построении искомого остова графа были |
||||||||
последовательно отобраны ребра |
x1,x2 , x5,x7 , x2,x7 |
, x3,x7 |
. Затем |
|||||
ребро |
x3,x5 |
было пропущено, т.к. оно образовывало цикл с ранее |
||||||
отобранными |
ребрами |
x3,x7 |
, |
x5 |
,x7 . Остальными |
двумя |
ребрами |
|
кратчайшего остова графа стали |
x3,x4 |
, x5,x6 . |
|
|
||||
3. Варианты расчетно-графической работы
ЗАДАНИЕ № 1. Для заданного орграфа:
1)вычислите степени всех его вершин;
2)приведите по одному примеру пути и контура;
3)постройте матрицы смежности и инцидентности.
Вариант |
Граф |
1
2
|
26 |
|
|
Вариант |
Граф |
3
4
5
6
|
27 |
|
|
Вариант |
Граф |
7
8
9
10
11
|
28 |
|
|
Вариант |
Граф |
12
13
14
15
29
ЗАДАНИЕ № 2. Изобразите орграф по его матрице смежности А.
Вариант |
|
|
А |
|
|
Вариант |
|
|
А |
|
|
|
|
|
|
|
|
||||
1 |
|
1 0 1 |
|
2 |
|
0 1 1 |
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 1 1 |
|
|
|
0 |
1 1 |
||
|
|
1 1 0 |
|
|
|
1 0 0 |
||||
|
|
|
|
|
|
|
|
|||
3 |
|
1 |
1 |
0 |
0 |
4 |
0 1 0 0 |
|||
|
|
|
|
|
|
|
|
|
|
|
|
1 0 1 1 |
|
1 0 1 1 |
|||||||
|
|
0 |
1 |
1 |
1 |
|
|
1 1 0 1 |
||
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
1 |
0 |
0 |
|
1 0 0 0 |
|||
|
|
|
|
|
|
|
|
|
|
|
Вариант |
|
|
А |
|
|
Вариант |
|
|
А |
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
||||
5 |
|
1 1 0 |
|
6 |
|
0 0 1 |
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
1 1 |
1 |
|
|
|
|
1 |
1 1 |
|
|
|
1 0 0 |
|
|
|
1 1 0 |
||||
|
|
|
|
|
|
|
|
|
||
7 |
|
1 |
1 |
0 |
1 |
8 |
|
1 1 0 1 |
||
|
|
|
|
|
|
|
|
|
|
|
|
1 0 1 0 |
|
0 1 1 1 |
|||||||
|
|
1 |
1 |
0 |
1 |
|
|
|
0 1 0 1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
1 |
0 |
1 |
|
|
|
1 1 0 0 |
|
|
|
|
|
|
|
|
||||
9 |
|
1 1 0 |
|
10 |
|
0 1 0 |
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
1 0 1 |
|
|
|
|
1 |
1 1 |
||
|
|
1 1 0 |
|
|
|
1 1 1 |
||||
|
|
|
|
|
|
|
|
|
|
|
30
11 |
|
1 |
1 |
1 0 |
12 |
|
1 0 1 1 |
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
0 |
0 1 |
1 |
|
|
|
1 1 1 0 |
||||||||
|
|
1 |
1 |
1 |
1 |
|
|
|
1 1 0 1 |
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 1 0 1 |
|
|
0 1 1 0 |
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
13 |
|
|
0 |
1 |
|
0 |
|
14 |
|
|
0 |
1 |
1 |
|
|
|
|
|
1 |
1 |
|
1 |
|
|
|
|
1 |
1 |
1 |
|
|
||
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
0 |
1 |
|
0 |
|
|
|
|
1 |
1 |
0 |
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
15 |
|
1 |
1 |
|
1 |
|
0 |
|
|
|
|
|
|
|
|
|
|
1 |
0 |
|
1 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
1 |
1 |
|
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
1 |
|
0 |
1 |
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ЗАДАНИЕ № 3. Найдите остов минимального веса, применив алгоритм
|
Краскала. |
Вариант |
Граф |
1