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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

5. Построить граф G = (X, A),
где
Х={х
i
}, i=1, 2, ..., 5, A={a
i
},
i=1,2,...,8,
a
1
=(x
1
,x
2
), a
2
=(x
2
,x
3
), a
3
=(x
2
,x
5
),
a
4
=(x
3
,x
5
), a
5
=(x
3
,x
1
), a
6
=(x
4
,x
5
),
a
7
=(x
4
,x
1
), a
8
=(x
5
,x
1
).
6. Построить граф G=(X, Г),
где X={x
i
}, i=1, 2, ..., 6, Г ={
Г(x
i
)
} – множество
отображений,
Г(х
1
) = {х
1
, х
3
, х
4
},
Г(х
2
) = {х
2
, х
4
, х
6
},
Г(х
3
)={х
3
, х
6
}, Г(х
4
)={х
5
, х
6
},
Г(х
5
)={х
2
, х
6
}, Г(х
6
)={х
1
, х
3
}.
7. Для графа,
изображенного на рисунке дать
возможные варианты его
описания матрицей смежности и
инциденций.
Ответ: Матрица смежности
X
1
X
2
X
3
X
4
X
5
X
1
X
2
X
3
X
4
X
5
Матрица
инциденций
a
1
a
2
a
3
a
4
a
5
a
6
X
1
X
2
X
3
X
4
X
5
8. По матрице инциденций найти полустепени исхода и захода для X
2 ,
построить
матрицу смежности и граф.
a
1
a
2
a
3
a
4
a
5
a
6
a
7
a
8
a
9
a
10
X
1
2 -1 1 0 1 0 1 0 0 0
X
2
0 1 -1 1 0 0 0 0 0 0
X
3
0 0 0 -1 -1 1 0 1 0 0
x
1
x
2
x
3
x
4
x
5
x
6
Ответ: d
o
(x
2
)= . . .,
d
t
(x
2
)= . . . .
x
1
x
2
x
3
x
4
x
5
x
6
5. Построить граф G = (X, A),                    x1              x2
   где
Х={хi}, i=1, 2, ..., 5, A={ai},                                            x3
i=1,2,...,8,
                                            x6
a1=(x1,x2), a2=(x2,x3), a3=(x2,x5),
a4=(x3,x5), a5=(x3,x1), a6=(x4,x5),                       x5          x4
a7=(x4,x1), a8=(x5,x1).


6. Построить граф G=(X, Г),                      x1              x2
   где X={xi}, i=1, 2, ..., 6, Г ={
   Г(xi ) } – множество
   отображений,                                                            x3
Г(х1) = {х1, х3, х4},
                                            x6
Г(х2) = {х2, х4, х6},
Г(х3)={х3, х6}, Г(х4)={х5, х6},                           x5          x4
Г(х5)={х2, х6}, Г(х6)={х1, х3}.
  7. Для графа,
изображенного на рисунке дать
возможные варианты его
описания матрицей смежности и
инциденций.
Ответ: Матрица смежности
           X1 X2 X3 X4         X5
       X1
       X2
       X3
       X4
       X5

              Матрица
                    инциденций
            a1 a2 a3 a4 a5 a6
         X1
         X2
         X3
         X4
         X5
8. По матрице инциденций найти полустепени исхода и захода для X2 , построить
матрицу смежности и граф.
                                 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10
   Ответ: do(x2)= . . .,    X1 2     -1   1   0    1   0    1   0     0    0
    dt(x2)= . . . .         X2 0      1  -1   1    0   0    0   0     0    0
                            X3 0      0   0   -1 -1    1    0   1     0    0

Страницы