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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

10. Какие из приведенных ниже графов являются деревьями?
Ответ: . . . . . . . . . . . . . . . . . . .
. .
3.2.Виды подграфов
Пусть дан граф G = (X, A), где X = { x
i
}, i=1,2,...,n - множество вершин, A = {
a
i
}, i=1,2,...,m - множество дуг.
Подграфом G'=(X', A') исходного графа G называется такой граф G', для
которого X'
⊆ X и A'⊆A. Примеры подграфов показаны на рис.19 б), а исходный
граф - на рис.19 а).
Остовным подграфом G
p
=(X, A
p
) графа G называется граф, для которого
A
p
⊂A. Таким образом, остовный подграф имеет то же самое множество вершин,
что и исходный граф G, но множество дуг подграфа G
p
является подмножеством
множества дуг исходного графа. Примеры остовных подграфов приведены на
рис.19 в). Для графа, имеющего m дуг можно построить k остовных подграфов
kC C C
mm m
mm
=+++ =−
−12 1
21
....
Порожденным подграфом G
s
=(X
s
, Г
s
) называется граф, для которого X
s
⊂
X и для каждой вершины x
i
∈X
s
прямое отображение Г
s
( x
i
) = Г( x
i
) ∩ X
s
. Таким
образом, порожденный подграф состоит из подмножества вершин X
s
множества
вершин исходного графа и всех таких дуг графа G, у которого конечные и
начальные вершины принадлежат подмножеству X
s
. Примеры порожденных
подграфов приведены на рис. 19 г).
011100 0
000011 0
000000 1
000000 0
000000 0
000000 0
000000 0
0 1010
0 0100
0 0001
0 0000
0 0000
a) b) c)
d) 
10. Какие из приведенных ниже графов являются деревьями?
                                                            0   1    1   1   0   0   0        0   1   0   1   0
                                                            0   0    0   0   1   1   0        0   0   1   0   0
                                                            0   0    0   0   0   0   1        0   0   0   0   1
                                                            0   0    0   0   0   0   0        0   0   0   0   0
                                                            0   0    0   0   0   0   0        0   0   0   0   0
                                                            0   0    0   0   0   0   0
                                                            0   0    0   0   0   0   0


      a)                                       b)               c)                       d)
Ответ: . . . . . . . . . . . . . . . . . . .
.                                                                                    .

                                                    3.2.Виды подграфов

         Пусть дан граф G = (X, A), где X = { xi }, i=1,2,...,n - множество вершин, A = {
ai }, i=1,2,...,m - множество дуг.
         Подграфом G'=(X', A') исходного графа G называется такой граф G', для
которого X'⊆ X и A'⊆A. Примеры подграфов показаны на рис.19 б), а исходный
граф - на рис.19 а).
         Остовным подграфом Gp=(X, Ap) графа G называется граф, для которого
Ap ⊂A. Таким образом, остовный подграф имеет то же самое множество вершин,
что и исходный граф G, но множество дуг подграфа Gp является подмножеством
множества дуг исходного графа. Примеры остовных подграфов приведены на
рис.19 в). Для графа, имеющего m дуг можно построить k остовных подграфов
k    = C 1m + C m2 +....+C mm −1 = 2m − 1

      Порожденным подграфом Gs=(Xs, Гs) называется граф, для которого Xs ⊂
X и для каждой вершины xi ∈Xs прямое отображение Гs ( xi ) = Г( xi ) ∩ Xs. Таким
образом, порожденный подграф состоит из подмножества вершин Xs множества
вершин исходного графа и всех таких дуг графа G, у которого конечные и
начальные вершины принадлежат подмножеству Xs. Примеры порожденных
подграфов приведены на рис. 19 г).

Страницы