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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

V {v
1
, v
2
, v
3
, v
4
, v
5
}.
V
(2)
.
V
(2)
= {{v
1
, v
2
}, {v
1
, v
3
}, {v
1
, v
4
}, {v
1
, v
5
},
{v
2
, v
3
}, {v
2
, v
4
}, {v
2
, v
5
},
{v
3
, v
4
}, {v
3
, v
5
},
{v
4
, v
5
}}
E ⊆ V
(2)
,
E = {{v
1
, v
2
}, {v
1
, v
3
}, {v
1
, v
4
},
{v
2
, v
3
}, {v
2
, v
5
},
{v
3
, v
4
},
{v
4
, v
5
}}
hV, Ei G,
V E
V
(2)
.
hV, Ei
V
E
V,
V G V (G)
EG E(G) G
   1. Ââåäåíèå
   1.1. Îïðåäåëåíèå ãðàôà
   Òåîðåòèêî-ìíîæåñòâåííîå îïðåäåëåíèå ãðàôà.Ïóñòü
V  íåïóñòîå ìíîæåñòâî, íàïðèìåð {v1 , v2 , v3 , v4 , v5 }. Çàïè-
øåì ìíîæåñòâî âñåõ åãî äâóõýëåìåíòíûõ ïîäìíîæåñòâ V (2) .
Äëÿ íàøåãî ïðèìåðà ýòî ìíîæåñòâî
         V (2) = {{v1 , v2 }, {v1 , v3 }, {v1 , v4 }, {v1 , v5 },
                              {v2 , v3 }, {v2 , v4 }, {v2 , v5 },
                                          {v3 , v4 }, {v3 , v5 },
                                                      {v4 , v5 }} .
Âîçüìåì ïðîèçâîëüíî íåêîòîðîå E ⊆ V (2) , íàïðèìåð,
         E = {{v1 , v2 }, {v1 , v3 }, {v1 , v4 },
                          {v2 , v3 },             {v2 , v5 },
                                      {v3 , v4 },
                                                  {v4 , v5 }} .
Ïàðó hV, Ei íàçûâàþò íåîðèåíòèðîâàííûì ãðàôîì G, â êî-
òîðîì V ýòî ìíîæåñòâî âåðøèí, à E  ìíîæåñòâî ðåáåð, ÿâ-
ëÿþùååñÿ ïîäìíîæåñòâîì ìíîæåñòâà V (2) .
    áîëåå êîìïàêòíîé ôîðìå ýòî îïðåäåëåíèå îáû÷íî ôîð-
ìóëèðóåòñÿ òàê: ïàðà hV, Ei íàçûâàåòñÿ íåîðèåíòèðîâàííûì
ãðàôîì, åñëè V  íåïóñòîå ìíîæåñòâî ýëåìåíòîâ, íàçûâàåìûõ
âåðøèíàìè, à E  ìíîæåñòâî íåóïîðÿäî÷åííûõ ïàð ðàçëè÷-
íûõ ýëåìåíòîâ èç V, íàçûâàåìûõ ðåáðàìè.
   Ïðè çàïèñè ðàçëè÷íûõ ñîîòíîøåíèé â òåîðèè ãðàôîâ ïîëü-
çóþòñÿ îáîçíà÷åíèÿìè V G èëè V (G) äëÿ ìíîæåñòâà âåðøèí
è EG èëè E(G) äëÿ ìíîæåñòâà ðåáåð ãðàôà G .
   Íàãëÿäíûì ñïîñîáîì ïðåäñòàâëåíèÿ ãðàôà ÿâëÿåòñÿ ðèñó-
íîê (äèàãðàììà), íà êîòîðîì âåðøèíû èçîáðàæàþòñÿ òî÷êà-
ìè, êðóæî÷êàìè èëè äðóãèìè ôèãóðêàìè, à ðåáðà  ëèíèÿìè,
ñîåäèíÿþùèìè èçîáðàæåíèÿ âåðøèí ðåáåðíîé ïàðû.1 Ôîðìà
  1 Èíîãäà   ãðàôîì íàçûâàþò èìåííî òàêîé ðèñóíîê (äèàãðàììó).


                                     5

Страницы