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

UptoLike

ВУЗ: 

МУМ | Москва

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

Рубрика: 

Чис ло ин ци дент ных вер ши не v ре бер на зы ва ет ся сте пе нью вер ши -
ны и обо зна ча ет ся d(v).
При мер б) (ри су нок 1.4.4): d(v
1
) = 3, d(v
2
) = 2, d(v
3
) = 0, d(v
4
) = 1,
d(v
5
) = 3, d(v
6
) = 1.
Ино гда сте пень вер ши ны на зы ва ет ся ее ва лент но стью. Вер ши на
сте пе ни 1 на зы ва ет ся ви ся чей вер ши ной. Вер ши на сте пе ни 0 на зы ва ет ся
изо ли ро ван ной.
При мер в) (ри су нок 1.4.4): v
3
— изо ли ро ван ная вер ши на, v
4
и v
6
—
ви ся чие вер ши ны, x
2
— ви ся чее ребро.
6) Ко ли че ст во вер шин и ре бер гра фа G обо зна ча ет ся со от вет ст вен -
но n(G) и m(G), а ко ли че ст во вер шин и дуг в орг ра фе D — че рез n(D)
и m(D).
Для лю бо го псев до гра фа G вы пол ня ет ся ра вен ст во:
d( ) ( )v m G
v VÎ
å
= 2
.
По лу сте пе нью ис хо да (за хо да) вер ши ны v орг ра фа D на зы ва ет ся
чис ло d
+
(v) (d
–
(v)) дуг орг ра фа D, ис хо дя щих из вер ши ны v (заходящих).
Для лю бо го ори ен ти ро ван но го псев до гра фа D вы пол ня ет ся ра -
вен ст во
d d
+
Î
-
Î
å å
= =
v V v V
v v m D( ) ( ) ( )
.
Чис ло вер шин не чет ной сте пе ни в лю бом гра фе четно.
7) Гра фы G
1
= (V
1
X
1
) и G
2
(V
2
X
2
) на зы ва ют ся изо морф ны ми, ес ли су -
ще ст ву ет би ек тив ное (вза им но од но знач ное) ото бра же ние f:V
1
®V
2
, со -
хра няю щие смеж ность, то есть {v, w} Î X
1
<=> {f(v), f(w)} Î X
2
. То же са -
мое вер но и для орг ра фов D
1
и D
2
. Дру ги ми сло ва ми, изо морф ные гра фы
(орг ра фы) от ли ча ют ся лишь обо зна че ния ми вер шин.
При мер:
8) Орг раф D
1
(или граф G
1
) на зы ва ет ся под раз бие ни ем орг ра фа D
2
(или гра фа G
2
), ес ли орг раф D
1
(граф G
1
) мож но по лу чить из D
2
(G
2
) пу тем
17
изо морф ные гра фы неи зо морф ный граф
Рис. 1.4.6
       Число инцидентных вершине v ребер называется степенью верши-
ны и обозначается d(v).
       Пример б) (рисунок 1.4.4): d(v1) = 3, d(v2) = 2, d(v3) = 0, d(v4) = 1,
d(v5) = 3, d(v6) = 1.
       Иногда степень вершины называется ее валентностью. Вершина
степени 1 называется висячей вершиной. Вершина степени 0 называется
изолированной.
       Пример в) (рисунок 1.4.4): v3 — изолированная вершина, v4 и v6 —
висячие вершины, x2 — висячее ребро.
     6) Количество вершин и ребер графа G обозначается соответствен-
но n(G) и m(G), а количество вершин и дуг в орграфе D — через n(D)
и m(D).
     Для любого псевдографа G выполняется равенство:

                                  åd( v) = 2 m(G ).
                                  v ÎV

     Полустепенью исхода (захода) вершины v орграфа D называется
число d+(v) (d–(v)) дуг орграфа D, исходящих из вершины v (заходящих).
     Для любого ориентированного псевдографа D выполняется ра-
венство åd + ( v) = åd - ( v) = m(D).
        v ÎV         v ÎV

      Число вершин нечетной степени в любом графе четно.
      7) Графы G1 = (V1X1) и G2(V2X2) называются изоморфными, если су-
ществует биективное (взаимно однозначное) отображение f:V1®V2, со-
храняющие смежность, то есть {v, w} Î X1<=> {f(v), f(w)} Î X2. То же са-
мое верно и для орграфов D1 и D2. Другими словами, изоморфные графы
(орграфы) отличаются лишь обозначениями вершин.
      Пример:




               изоморфные графы                       неизоморфный граф

                                         Рис. 1.4.6

      8) Орграф D1 (или граф G1) называется подразбиением орграфа D2
(или графа G2), если орграф D1 (граф G1) можно получить из D2 (G2) путем
                                                                          17

Страницы