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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

1. Дан граф.
♦ Какие из приведенных ниже графов
являются его подграфами?
♦ Какие из приведенных ниже графов
являются его остовными подграфами?
♦ Какие из приведенных ниже графов
являются для него порожденными
подграфами?
Ответ: подграфами являются . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . остовными
подграфами являются. . . . . . . . . . . . . . . . . . . . . . . . . . . .
порожденными подграфами являются . . . . . . . . . . . . . . . . . . . . . . .
2. Для графа G=(X,A), представленного на рисунке,
описать матрицей смежности:
а) порожденный подграф <{x
1
,x
2
,x
4
,x
5
}>,
б) остовный подграф (X, A’), где '),( Axx
ji
∈
тогда и
только тогда, когда i+j нечетно,
в) остовный подграф подграфа из (а), определенный так
же, как в пункте (б).
b
a c
d
e
x
8
x
3
x
5
x
7
x
6
x
4
x
2
x
1
d
c
b
e
a
d
c
b
e
a
e
d
a
d
c
b
e
a
e
d
a
a) b) c)
d
c
b
e
a
e
d
a
d
c
b
e
a
e
d
a
d) e) f)
b
a c
d
e 
    1. Дан граф.
          ♦ Какие из приведенных ниже графов
             являются его подграфами?                                                                    b
          ♦ Какие из приведенных ниже графов
             являются его остовными подграфами?                                 a                                           c
          ♦ Какие из приведенных ниже графов
             являются для него порожденными
             подграфами?

                                                                                                                                d
                     b                                         b                    e                        a

                                   c                                       c
        a                                          a
                                                                                                                                d
                                                                                               e
    e                                  d       e                               d

                a)                                        b)                                                     c)



                     b                                                                                       a
                                                               b
                                   c
        a                                  a                                   c
                                                                                                                                d
                                                                                               e
    e                                  d
                                                                                 d
                                      e
          d)
Ответ: подграфами  являются . . . . . . . . . e)     . . . . . . . . . . . . . . . . . . . . . . . . . . . . .f). . остовными
подграфами являются. . . . . . . . . . . . . . . . . . . . . . . . . . . .
порожденными подграфами являются . . . . . . . . . . . . . . . . . . . . . . .

2. Для графа G=(X,A), представленного на рисунке,                                         x1                           x2
описать матрицей смежности:
а) порожденный подграф <{x1,x2,x4,x5}>,
б) остовный подграф (X, A’), где ( xi , x j ) ∈ A' тогда и
только тогда, когда i+j нечетно,                                                                    x7            x5
                                                                                    x8                                          x3
в) остовный подграф подграфа из (а), определенный так
же, как в пункте (б).

                                                                                                                                x4
                                                                                                   x6

Страницы