Математика. Раздел 1. Дискретная математика. Тетрадь 1.2. Казанцев Э.Ф. - 25 стр.

UptoLike

ВУЗ: 

МУМ | Москва

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

Рубрика: 

2) По стро ить граф G(V,X), где
V = {v
1
v
2
v
3
v
4
v
5
v
6
}, X = {x
1
x
2
x
3
x
4
x
5
x
6
x
7
x
8
} и x
1
=(v
1
v
2
); x
2
=(v
2
v
1
);
x
3
=(v
1
v
3
); x
4
=(v
2
v
4
); x
5
=(v
3
v
4
); x
6
=(v
3
v
4
); x
7
=(v
3
v
5
); x
8
=(v
5
v
4
).
3) По стро ить орг раф D(V,X), где
V = {v
1
v
2
v
3
}, X = {x
1
x
2
x
3
x
4
x
5
x
6
} и x
1
=<v
1
v
2
>; x
2
=<v
2
v
1
>; x
3
=<v
2
v
2
>;
x
4
=<v
2
v
3
>; x
5
=<v
3
v
1
>; x
6
=<v
3
v
3
>.
4) По стро ить граф по мат ри це ин ци дент но сти:
x
1
x
2
x
3
x
4
x
5
x
6
x
7
v
1
0 1 0 1 0 1 0
v
2
1 1 1 0 1 0 1
v
3
1 0 1 0 0 1 0
v
4
0 0 0 1 1 1 0
5) По ка зать, что из вся ко го замк ну то го мар шру та не чет ной дли ны
мож но вы де лить про стую цепь.
6) По ка зать, что реб ро, вхо дя щее в цикл гра фа, вхо дит в не ко то -
рый его про стой цикл.
7) По ка зать, что лю бая вер ши на, вхо дя щая в цикл, не яв ля ет ся ви -
ся чей.
8) До ка зать, что в связ ном гра фе, со дер жа щем, по край ней ме ре,
две вер ши ны, най дет ся вер ши на, не яв ляю щая ся точ кой со чле не ния.
9) До ка зать, что ес ли в орг ра фе D от сут ст ву ют вер ши ны с ну ле вой
по лу сте пе нью ис хо да (за хо да), то в D име ет ся про стой кон тур.
25
      2) Построить граф G(V,X), где
      V = {v1 v2 v3 v4 v5 v6}, X = {x1 x2 x3 x4 x5 x6 x7 x8} и x1=(v1v2); x2=(v2v1);
x3=(v1v3); x4=(v2v4); x5=(v3v4); x6=(v3v4); x7=(v3v5); x8=(v5v4).

      3) Построить орграф D(V,X), где
      V = {v1 v2 v3}, X = {x1 x2 x3 x4 x5 x6} и x1=; x2=; x3=;
x4=; x5=; x6=.

       4) Построить граф по матрице инцидентности:

                         x1    x2    x3     x4    x5    x6    x7
                   v1    0     1     0      1     0     1     0
                   v2    1     1     1      0     1     0     1
                   v3    1     0     1      0     0     1     0
                   v4    0     0     0      1     1     1     0

    5) Показать, что из всякого замкнутого маршрута нечетной длины
можно выделить простую цепь.

     6) Показать, что ребро, входящее в цикл графа, входит в некото-
рый его простой цикл.

      7) Показать, что любая вершина, входящая в цикл, не является ви-
сячей.

      8) Доказать, что в связном графе, содержащем, по крайней мере,
две вершины, найдется вершина, не являющаяся точкой сочленения.

     9) Доказать, что если в орграфе D отсутствуют вершины с нулевой
полустепенью исхода (захода), то в D имеется простой контур.




                                                                                 25

Страницы