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

UptoLike

ВУЗ: 

МУМ | Москва

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

Рубрика: 

При мер а): Рас смот рим граф G, изо бра жен ный на ри сун ке 1.4.4:
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
1
= (v
1
, v
2
);
x
2
= (v
1
, v
4
); x
3
= (v
5
, v
6
); x
4
= (v
1
, v
2
); x
5
= (v
5
, v
5
).
При мер б): Рас смот рим граф D, изо бра жен ный на ри сун ке 1.4.5
V={v
1
, v
2
, v
3
, v
4
}; X = {x
1
, x
2
, x
3
, x
4
}, при чем x
1
= <v
1
, v
2
>, x
2
= <v
1
, v
2
>,
x
3
=<v
2
, v
2
>, x
4
= <v
3
, v
2
>. Это ори ен ти ро ван ный псев до граф.
5) Ес ли x = (v,w) — реб ро гра фа, то вер ши ны v, w на зы ва ют ся кон -
ца ми реб ра x. Го во рят, что реб ро х со еди ня ет вер ши ны v и w.
Ес ли x = (v,w) — ду га орг ра фа, то вер ши на v на зы ва ет ся на ча лом,
а вер ши на w — кон цом ду ги x. Го во рят, что ду га x ис хо дит из вер ши ны v и
за хо дит в вер ши ну w.
Ес ли вер ши на v яв ля ет ся кон цом (или на ча лом) реб ра (ду ги) x,
то го во рят, что v и x ин ци дент ны. Вер ши ны v, w гра фа G = (V, X) на зы ва -
ют ся смеж ны ми, ес ли {v, w} Î X. Два реб ра на зы ва ют ся смеж ны ми, если
они имеют общую вершину.
При мер а) (ри су нок 1.4.4): x
1
— ин ци дент но v
1
и v
2
; v
1
и v
4
— смеж -
ные; x
1
и x
2
— смеж ные.
16
Рис. 1.4.5
Рис. 1.4.4
      Пример а): Рассмотрим граф G, изображенный на рисунке 1.4.4:




                                      Рис. 1.4.4
      V = {v1, v2, v3, v4, v5, v6}; X = {x1, x2, x3, x4, x5}, причем x1 = (v1, v2);
      x2= (v1, v4); x3 = (v5, v6); x4 = (v1, v2); x5 = (v5, v5).
      Пример б): Рассмотрим граф D, изображенный на рисунке 1.4.5
V={v1, v2, v3, v4}; X = {x1, x2, x3, x4}, причем x1 = , x2 = ,
x3=, x4 = . Это ориентированный псевдограф.




                                      Рис. 1.4.5

      5) Если x = (v,w) — ребро графа, то вершины v, w называются кон-
цами ребра x. Говорят, что ребро х соединяет вершины v и w.
      Если x = (v,w) — дуга орграфа, то вершина v называется началом,
а вершина w — концом дуги x. Говорят, что дуга x исходит из вершины v и
заходит в вершину w.
      Если вершина v является концом (или началом) ребра (дуги) x,
то говорят, что v и x инцидентны. Вершины v, w графа G = (V, X) называ-
ются смежными, если {v, w} Î X. Два ребра называются смежными, если
они имеют общую вершину.
      Пример а) (рисунок 1.4.4): x1 — инцидентно v1 и v2; v1 и v4 — смеж-
ные; x1 и x2 — смежные.
16

Страницы