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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

Аналогично знаком "-" вершина x
ik
помечается вдоль некоторого маршрута М2.
Например
M
2
: x
1
→ x
4
→ x
6
→ x
2
.
"+" "-" "+" "-"
Пусть x* - предпоследняя (последней является x
ik
) общая вершина
маршрутов M
1
и M
2
. Если вершина x* помечена знаком "+", то участок от x* до x
ik
маршрута М
1
должен быть четным, а участок от х
*
до х
ik
маршрута M
2
должен
быть нечетным. Если же вершина x* помечена знаком "-", то участок маршрута
M
1
будет нечетным, а маршрута M
2
-четным. Следовательно, цикл, состоящий
из участка маршрута М1, от x* до x
ik
, и соответствующего участка маршрута M
2
, от
X
ik
до x*, имеет нечетную длину. Это противоречит предположению, что граф не
содержит циклов нечетной длины, и, значит, случай (3) невозможен.
В рассматриваемом примере x* = x
4
. В маршруте M
1
длина участка от x
4
до x
2
равна 1, а в маршруте M
2
длина участка от x
4
до x
2
равна 2, что в сумме
составляет нечетное число, следовательно граф содержит цикл нечетной длины и
не является двудольным.
. Упражнения 3.1 .
1.Какие из приведенных ниже графов являются полными?
Ответ: . . . . . . . . . . . . . . . . . . .
2.По матрицам смежности определить какие из графов являются полными.
Ответ: . . . . . . . . . . . . . . . . . . .
3. Какие из приведенных ниже графов являются симметрическими?
Ответ: . . . . . . . . . . . . . . . . . . .
4. Какие из приведенных ниже графов являются антисимметрическими?
1 1 1 1 0
0 1 0 1 0
0 0 1 1 0
0 0 0 1 0
1 1 1 1 0
0 1 0 1 0
0 0 0 1 1
1 1 0 0 0
0 0 1 0 1
1 0 1 0 0
11011
11101
01111
10111
11111
0 0000
1 0000
1 1000
1 1100
1 1110
11011
11101
01111
10111
11111
0 1010
1 1101
0 1010
1 0111
0 1010
a) b) c)
d)
a) b) c)
d)
a) b) c)
d)
a)
b
)
c)
d
)
 Аналогично знаком "-" вершина xik помечается вдоль некоторого маршрута М2.
Например
 M2: x1 → x4 → x6 → x2.
     "+" "-" "+" "-"
    Пусть x* - предпоследняя (последней является         xik)  общая   вершина
маршрутов M1 и M2. Если вершина x* помечена знаком "+", то участок от x* до xik
маршрута М1 должен быть четным, а участок от х* до хik маршрута M2 должен
быть нечетным. Если же вершина x* помечена знаком "-", то участок маршрута
M1 будет нечетным, а маршрута M2 -четным. Следовательно, цикл, состоящий
из участка маршрута М1, от x* до xik, и соответствующего участка маршрута M2, от
Xik до x*, имеет нечетную длину. Это противоречит предположению, что граф не
содержит циклов нечетной длины, и, значит, случай (3) невозможен.
    В рассматриваемом примере x* = x4. В маршруте M1 длина участка от x4 до x2
равна 1, а в маршруте M2 длина участка от x4 до x2 равна 2, что в сумме
составляет нечетное число, следовательно граф содержит цикл нечетной длины и
не является двудольным.

.    Упражнения 3.1                                                      .
1.Какие из приведенных ниже графов являются полными?




         a)                                  b)     c)             d)
Ответ: . . . . . . . . . . . . . . . . . . .
2.По матрицам смежности определить какие из графов являются полными.
1 1 1 1 0                    0 1 0 1 0          1 1 0 1 1            0       0   0   0   0
0 1 0 1 0                    0 0 0 1 1          1 1 1 0 1            1       0   0   0   0
0 0 1 1 0                    1 1 0 0 0          0 1 1 1 1            1       1   0   0   0
0 0 0 1 0                    0 0 1 0 1          1 0 1 1 1            1       1   1   0   0
1 1 1 1 0                    1 0 1 0 0          1 1  1 1 1           1       1   1   1   0

         a)                   b)                     c)             d)
Ответ: . . . . . . . . . . . . . . . . . . .
3. Какие из приведенных ниже графов являются симметрическими?
                                             1   1    0   1   1          0   1   0   1   0
                                             1   1    1   0   1          1   1   1   0   1
                                             0   1    1   1   1          0   1   0   1   0
                                             1   0    1   1   1          1   0   1   1   1
                                             1   1    1   1   1          0   1   0   1   0

          a)                                 b)    c)                d)
Ответ: . . . . . . . . . . . . . . . . . . .
4. Какие из приведенных ниже графов являются антисимметрическими?




    a)                  b               c)                    d
                        )                                     )

Страницы