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

UptoLike

ВУЗ: 

МУМ | Москва

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

Рубрика: 

При мер (ри су нок 1.4.7):
a) мар шрут v
1
x
1
v
2
x
3
v
4
x
4
v
3
— про стая цепь дли ны 3; все реб ра и
вер ши ны по пар но раз лич ны;
б) v
2
x
2
v
3
x
4
v
4
v
2
— замк ну тый мар шрут дли ны 3; это про стой цикл;
в) v
1
x
1
v
2
x
2
v
3
x
4
v
4
x
3
v
2
— не про стая цепь дли ны 4, со еди няю щая
вер ши ны v
1
и v
2
. Она не про стая, по то му, что вер ши на v
2
встре ча ет ся
дважды.
В псев до га фе G из вся ко го цик ла мож но вы де лить про стой цикл.
В ори ен ти ро ван ном псев до гра фе D из вся ко го замк ну то го пу ти
мож но вы де лить простой контур.
Из вся ко го не замк ну то го мар шру та (пу ти) мож но вы де лить про -
стую цепь с те ми же на чаль ны ми и ко неч ны ми вершинами.
10) Пусть да ны два пу ти в орг ра фе D:
p
1
= v
1
x
1
v
2
... x
k–1
v
k
; p
2
= v
k
x
k
v
k+1
... x
n–1
v
n
.
Путь p
1
o
p
2
= v
1
x
1
v
2
... x
k–1
v
k
x
k
v
k+1
... x
n–1
v
n
на зы ва ет ся ком по зи ци ей
пу тей p
1
и p
2
. Ана ло гич но оп ре де ля ет ся ком по зи ция мар шру тов.
1.4.2 Мат ри цы гра фов
1) Мат ри цей смеж но сти орг ра фа D на зы ва ет ся квад рат ная мат ри -
ца:
A D a
ij
( ) =
по ряд ка n, у ко то рой мат рич ные эле мен ты рав ны:
a
v v X
v v X
ij
i j
i j
=
< >Î
< >Ï
ì
í
î
1
0
,
,
если
если
.
При мер. Рас смот рим орг раф D, изо бра жен ный на ри сун ке 1.4.8.
19
Рис. 1.4.8
      Пример (рисунок 1.4.7):
      a) маршрут v1 x1 v2 x3 v4 x4 v3 — простая цепь длины 3; все ребра и
вершины попарно различны;
      б) v2 x2 v3 x4 v4 v2 — замкнутый маршрут длины 3; это простой цикл;
      в) v1 x1 v2 x2 v3 x4 v4 x3 v2 — непростая цепь длины 4, соединяющая
вершины v1 и v2. Она непростая, потому, что вершина v2 встречается
дважды.
      В псевдогафе G из всякого цикла можно выделить простой цикл.
      В ориентированном псевдографе D из всякого замкнутого пути
можно выделить простой контур.
      Из всякого незамкнутого маршрута (пути) можно выделить про-
стую цепь с теми же начальными и конечными вершинами.

      10) Пусть даны два пути в орграфе D:
      p1 = v1 x1 v2 ... xk–1 vk; p2 = vk xk vk+1 ... xn–1 vn.
      Путь p1 o p2 = v1 x1 v2 ... xk–1 vk xk vk+1 ... xn–1 vn называется композицией
путей p1 и p2. Аналогично определяется композиция маршрутов.

      1.4.2 Матрицы графов

      1) Матрицей смежности орграфа D называется квадратная матри-
ца: A(D) = aij порядка n, у которой матричные элементы равны:

                                 ì1, если < v i v j >Î X
                           aij = í                       .
                                 î0, если < v i v j >Ï X
      Пример. Рассмотрим орграф D, изображенный на рисунке 1.4.8.




                                     Рис. 1.4.8


                                                                                 19

Страницы