Компьютерная математика: Часть 2. Теория графов. Волченская Т.В - 12 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

Составители: 

Рубрика: 

когда дуга образует петлю, то каждый столбец либо содержит один элемент,
равный 1 и один - равный -1, либо все элементы столбца равны 0.
Для неориентированного графа, матрица инциденций определяется так же,
за исключением того ,что все элементы, равные -1, заменяются на 1.
. Упражнения к п. 1.2 .
1. Для графа, изображенного на рисунке, дать описание
перечислением и с помощью отображений.
Ответ: G=(Х, А),
где Х = { х
i
}, i=1, 2, 3, 4 - множество вершин;
А = { a
i
}, i=1,2,...,5 - множество дуг, причем
А={(x
2
, x
1
), (x
..
, x
. .
), (x.., x. .), (x. ., x . ), (x. . , x. .) }.
G=(X, Г)), где X={x
i
}, i=1,2,...,4 - множество
вершин, Г ={ Г(x
i
)
} – множество отображений, Г(х
1
)={ . . .
}, Г(x
2
)={ . . . . }, Г(x
3
)={ . .
. . .}, Г(x
4
)={ . . . } - отображения.
2. Для графа, представленного на рисунке, построить матрицы
смежности и инциденций.
Ответ: Матрица смежности
X
1
X
2
X
3
X
4
X
1
X
2
X
3
X
4
Матрица инциденций
a
1
a
2
a
3
a
4
a
5
a
6
a
7
X
1
X
2
X
3
X
4
3. Построить граф, заданный матрицей
смежности.
1 0 1 1 0 0
0 1 0 1 0 1
0 0 0 1 0 1
0 0 1 0 0 1
1 0 0 0 0 0
0 1 0 0 0 1
4. По матрице смежности, данной в
предыдущей задаче, подсчитать:
а) количество петель графа - . . .
.,
б) полустепень исхода второй вершины d
o
(х
2
)=. . . . ,
в) полуступень захода второй вершины d
t
(x
2
)=. . . . . .
2
1
4
3
a
1
a
1
a
2
a
3
a
4
a
5
a
6
a
7
x
1
x
2
x
3
x
4
x
5
x
6
когда дуга образует петлю, то каждый столбец либо содержит один элемент,
равный 1 и один - равный -1, либо все элементы столбца равны 0.
      Для неориентированного графа, матрица инциденций определяется так же,
за исключением того ,что все элементы, равные -1, заменяются на 1.


.     Упражнения к п. 1.2                                                              .
                                                                        2
1. Для графа, изображенного на рисунке, дать описание
перечислением и с помощью отображений.
       Ответ: G=(Х, А),
где Х = { хi }, i=1, 2, 3, 4 - множество вершин;
       А = { ai }, i=1,2,...,5 - множество дуг, причем 1                           3
А={(x2, x1), (x.. , x . .), (x.., x. .), (x. ., x . ), (x. . , x. .) }.
        G=(X, Г)),          где X={xi}, i=1,2,...,4 - множество           4
вершин, Г ={ Г(xi ) } – множество отображений, Г(х1)={ . . . }, Г(x2)={ . . . . }, Г(x3)={ . .
. . .}, Г(x4)={ . . . } - отображения.

2. Для графа, представленного на рисунке, построить матрицы
   смежности и инциденций.
Ответ: Матрица смежности                                       a1
                                                                             a2
           X1 X2 X3 X4
       X1                                                               a1
                                                                        a3
       X2                                                a7                                a5
       X3                                                                         a4
       X4
       Матрица инциденций                                                a6
             a1   a2   a3        a4    a5    a6     a7
        X1
        X2
        X3
        X4

3. Построить граф, заданный матрицей
смежности.                                                    x1                       x2
        1 0 1 1 0 0
      0 1 0 1 0 1
      0 0 0 1 0 1                                                                                    x3
      0 0 1 0 0 1
      1 0 0 0 0 0                                     x6
      0 1 0 0 0 1
4. По матрице смежности, данной в                                            x5                 x4
предыдущей задаче, подсчитать:
    а) количество петель графа - . . .
.,
    б) полустепень исхода второй вершины             do(х2)=. . . . ,
    в) полуступень захода второй вершины           dt(x2)=. . . . . .

Страницы