Элементы теории графов. Домнин Л.Н. - 6 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

V E
s
v
1
s
v
2
s
v
3
s
v
4
s
v
5
Z
Z
Z
B
B
B
B
B
B
B
B
s
v
1
s
v
2
s
v
3
s
v
4
s
v
5
@
@
@
s
v
1
s
v
2
s
v
3
s
v
4
s
v
5
@
@
@
@
@
A
A
A
A
A
s
v
1
s
v
2
s
v
3
s
v
4
s
v
5
{v
i
, v
j
},
v
i
v
j
.
v
i
v
j
v
1
v
2
v
3
v
5
{v
1
, v
2
} {v
1
, v
3
}
{v
4
, v
5
} {v
2
, v
3
} v
3
{v
2
, v
3
}
v,
deg v.
deg v
1
= deg v
2
= deg v
3
= deg v
4
=3, deg v
5
=2.
v deg v=0,
deg v=1.
v
adj v. adj v
1
= {v
2
, v
3
, v
4
}.
n=|V |,
m=|E|. n m
(n, m)
è ðàçìåðû èçîáðàæåíèÿ çíà÷åíèÿ íå èìåþò. Âàæíî òîëüêî,
÷òîáû îíî ñîîòâåòñòâîâàëî ìíîæåñòâàì V è E . Íà ðèñ. 1.1
äàíû âàðèàíòû òàêîãî ïðåäñòàâëåíèÿ âûøåîïèñàííîãî ãðàôà.
              vs1          vs5      vs2          vs1      vs2
              Z
               B                                  A@                   vs1
  v5 s        BZ   Zsv2      v1 s                  A@          v5 s         sv2
     B  B                      @                   A @
      B
        Bs      BBs     s      @
                                   @s              s AAs @
                                                         @s        s    s
        v4         v3      v4       v3           v5 v4 v3         v4   v3
                                          Ðèñ. 1.1

Îáðàòèòå âíèìàíèå íà ñóùåñòâåííîå ðàçëè÷èå èçîáðàæåíèé
è âìåñòå ñ òåì ïîëíîå ñîîòâåòñòâèå äðóã äðóãó è îïèñàíèþ
ãðàôà íà ñòð. 5.
    Îñíîâíûå õàðàêòåðèñòèêè ãðàôà è åãî ýëåìåíòîâ.
Äâå âåðøèíû, îáðàçóþùèå ðåáðî {vi , vj }, íàçûâàþò åãî êîí-
öàìè, à ïðî ðåáðî ãîâîðÿò, ÷òî îíî ñîåäèíÿåò vi è vj . Ãîâîðÿò
òàêæå, ÷òî âåðøèíû vi è vj ñìåæíû. Ñìåæíûìè íàçûâàþò è
ðåáðà ñ îáùåé âåðøèíîé. Ïðî ðåáðî è âåðøèíó, êîòîðàÿ ÿâëÿ-
åòñÿ åãî êîíöîì, ãîâîðÿò, ÷òî îíè èíöèäåíòíû. Òàê, íàïðèìåð,
â ãðàôå íà ðèñ. 1.1 âåðøèíû v1 è v2 ñìåæíû, à âåðøèíû v3
è v5 íå ñìåæíû. Ðåáðà {v1 , v2 } è {v1 , v3 } ñìåæíû, à ðåáðà
{v4 , v5 } è {v2 , v3 } íå ñìåæíû. Íàêîíåö, âåðøèíà v3 è ðåáðî
{v2 , v3 } èíöèäåíòíû.
    ×èñëî ðåáåð, èíöèäåíòíûõ âåðøèíå v, îïðåäåëÿåò ñòå-
ïåíü âåðøèíû, êîòîðàÿ îáîçíà÷àåòñÿ deg v. Òàê, â ãðàôå íà
ðèñ. 1.1 deg v1 = deg v2 = deg v3 = deg v4 =3, à deg v5 =2. Âåðøè-
íó v íàçûâàþò èçîëèðîâàííîé, åñëè deg v=0, è êîíöåâîé, åñëè
deg v=1. Ðåáðî, èíöèäåíòíîå êîíöåâîé âåðøèíå, òàêæå íàçû-
âàþò êîíöåâûì. Ñïèñîê ñòåïåíåé âñåõ âåðøèí íàçûâàþò ñòå-
ïåííîé ïîñëåäîâàòåëüíîñòüþ ãðàôà.
    Ìíîæåñòâî âåðøèí, ñìåæíûõ ñ âåðøèíîé v , îáîçíà÷àþò
êàê adj v. Íàïðèìåð, â ãðàôå íà ðèñ. 1.1 adj v1 = {v2 , v3 , v4 }.
    Âàæíåéøèìè êîëè÷åñòâåííûìè õàðàêòåðèñòèêàìè ãðàôà
ÿâëÿþòñÿ: ÷èñëî âåðøèí n=|V |, îïðåäåëÿþùåå ïîðÿäîê ãðà-
ôà, è ÷èñëî ðåáåð m=|E|. Ãðàô ñ n âåðøèíàìè è m ðåáðàìè
íàçûâàåòñÿ (n, m)-ãðàôîì.


                                             6

Страницы