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

UptoLike

ВУЗ: 

МУМ | Москва

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

Рубрика: 

по сле до ва тель но го при ме не ния опе ра ции под раз бие ния дуг. Опе ра ция
под раз бие ния ду ги (u, v) со сто ит в уда ле нии из X ду ги (u, v), до бав ле нии
к V но вой вер ши ны w и до бав ле нии к X = (u, v) двух дуг (u, w) и (w, v).
9) По сле до ва тель ность v
1
x
1
v
2
x
2
v
3
... x
k
v
k+1
, в ко то рой че ре ду ют ся
вер ши ны и реб ра на зы ва ет ся мар шру том, со еди няю щим вер ши ну v
1
с вер ши ной v
k+1
.
Для орг ра фа мар шрут на зы ва ет ся пу тем. v
1
на зы ва ет ся на чаль ной
вер ши ной; v
k+1
— ко неч ной вер ши ной. Ос таль ные вер ши ны на зы ва ют ся
внут рен ни ми.
Од на и та же вер ши на мо жет од но вре мен но ока зать ся на чаль ной,
ко неч ной и внут рен ней. По сле до ва тель ность вер шин в мар шру те оп ре -
де ля ет его ориентацию.
При мер. Рас смот рим граф G, изо бра жен ный на ри сун ке 1.4.7. По -
сле до ва тель ность v
1
x
1
v
2
x
3
v
4
x
4
v
3
— это мар шрут, со еди няю щий вер ши -
ны v
1
и v
3
.
Мар шрут v
1
x
1
v
2
x
2
v
3
...x
k
v
k+1
мож но за пи сать ко ро че: x
1
x
2
... x
k
. Ес ли
же все крат но сти x
i
рав ны 1, то мож но за пи сать по сле до ва тель ность вер -
шин: v
1
v
2
...v
k+1
.
Число ре бер в мар шру те на зы ва ет ся дли ной мар шру та. Мар шрут на -
зы ва ет ся замк ну тым, ес ли его на чаль ная вер ши на сов па да ет с ко неч ной:
v
1
= v
k+1
. При замк ну том мар шру те мо гут ис поль зо вать ся раз лич -
ные за пи си: x
1
x
2
...x
k
; x
2
x
3
...x
k
x
1
; x
k
x
1
x
2
...x
k-1
и так далее.
Не замк ну тый мар шрут, в ко то ром все реб ра по пар но раз лич ны,
на зы ва ет ся це пью. Цепь, в ко то рой все вер ши ны по пар но раз лич ны на -
зы ва ет ся про стой це пью. Замк ну тый мар шрут, в ко то ром все реб ра по -
пар но раз лич ны, на зы ва ет ся цик лом. Для орг ра фа цикл на зы ва ет ся кон -
ту ром. Цикл (кон тур), в ко то ром все вер ши ны по пар но раз лич ны на зы -
ва ет ся про стым.
18
Рис. 1.4.7
последовательного применения операции подразбиения дуг. Операция
подразбиения дуги (u, v) состоит в удалении из X дуги (u, v), добавлении
к V новой вершины w и добавлении к X = (u, v) двух дуг (u, w) и (w, v).
      9) Последовательность v1 x1 v2 x2 v3 ... xk vk+1, в которой чередуются
вершины и ребра называется маршрутом, соединяющим вершину v1
с вершиной vk+1.
      Для орграфа маршрут называется путем. v1 называется начальной
вершиной; vk+1 — конечной вершиной. Остальные вершины называются
внутренними.
      Одна и та же вершина может одновременно оказаться начальной,
конечной и внутренней. Последовательность вершин в маршруте опре-
деляет его ориентацию.
      Пример. Рассмотрим граф G, изображенный на рисунке 1.4.7. По-
следовательность v1 x1 v2 x3 v4 x4 v3 — это маршрут, соединяющий верши-
ны v1 и v3.




                                   Рис. 1.4.7
      Маршрут v1 x1 v2 x2 v3...xk vk+1 можно записать короче: x1 x2... xk. Если
же все кратности xi равны 1, то можно записать последовательность вер-
шин: v1 v2...vk+1.
      Число ребер в маршруте называется длиной маршрута. Маршрут на-
зывается замкнутым, если его начальная вершина совпадает с конечной:
      v1 = vk+1. При замкнутом маршруте могут использоваться различ-
ные записи: x1 x2...xk; x2 x3...xk x1; xk x1 x2...xk-1 и так далее.
      Незамкнутый маршрут, в котором все ребра попарно различны,
называется цепью. Цепь, в которой все вершины попарно различны на-
зывается простой цепью. Замкнутый маршрут, в котором все ребра по-
парно различны, называется циклом. Для орграфа цикл называется кон-
туром. Цикл (контур), в котором все вершины попарно различны назы-
вается простым.
18

Страницы