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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

g
n
g
10
=12 005 168.
l
10
,
g
n
∼ 2
C
2
n
/n!
n!
n!
n n=4
2
C
2
4
/4!=8/3,
n=10
n=12
∼1, 54 · 10
11
, ∼1, 65 · 10
11
,
n=15
G
0
(V
0
, E
0
) G(V, E),
V
0
⊆V E
0
⊆E {v, u}
E
0
v∈V
0
u∈V
0
G G
0
G
0
(V, E
0
),
G(V, E).
ãðàôàìè â ýòèõ òðîéêàõ èñ÷åçíóò. Ïîýòîìó åñòåñòâåííî ïîÿâ-
ëåíèå òàêîãî ïîíÿòèÿ êàê íåïîìå÷åííûé (àáñòðàêòíûé) ãðàô,
â îòëè÷èå îò ïîìå÷åííîãî (èìåþùåãî ìåòêè âåðøèí). ßñíî,
÷òî ëþáîé íåïîìå÷åííûé ãðàô ïðåäñòàâëÿåò ìíîæåñòâî èçî-
ìîðôíûõ ïîìå÷åííûõ ãðàôîâ.
     Çàäà÷à îïðåäåëåíèÿ êîëè÷åñòâà íåïîìå÷åííûõ ãðàôîâ gn
ñóùåñòâåííî ñëîæíåå çàäà÷è î êîëè÷åñòâå ïîìå÷åííûõ.  [2]
ïðèâåäåíû äàííûå î ÷èñëå íåïîìå÷åííûõ ãðàôîâ äî 24-ãî ïî-
ðÿäêà âêëþ÷èòåëüíî. Òàê, ÷èñëî ãðàôîâ ñ äåñÿòüþ âåðøèíàìè
g10 =12 005 168. Ýòà âåëè÷èíà íà øåñòü ïîðÿäêîâ ìåíüøå, ÷åì
l10 , íî âñå åùå âåñüìà çíà÷èòåëüíà.
     Ñóùåñòâóåò äîñòàòî÷íî ïðîñòàÿ ôîðìóëà Ïîéà, äàþùàÿ
àñèìïòîòè÷åñêóþ îöåíêó ÷èñëà íåïîìå÷åííûõ ãðàôîâ:
                                    2
                          gn ∼ 2Cn /n!
Ñîãëàñíî ôîðìóëå êîëè÷åñòâî íåïîìå÷åííûõ ãðàôîâ ïðèáëè-
çèòåëüíî â n! ðàç ìåíüøå êîëè÷åñòâà ïîìå÷åííûõ. Äåéñòâè-
òåëüíî, â áîëüøèíñòâå ñëó÷àåâ (íî íå âñåãäà) ðàçìåòêó âåð-
øèí íåïîìå÷åííîãî ãðàôà ìîæíî âûïîëíèòü n! ñïîñîáàìè.
Ïðè ìàëûõ n ôîðìóëà "íå ðàáîòàåò". Òàê, äëÿ n=4 ïîëó÷àåì
   2
2C4 /4!=8/3, òîãäà êàê èìååòñÿ 11 ÷åòûðåõâåðøèííûõ ãðàôîâ,
ò. å. íàëèöî ÷åòûðåõêðàòíîå çàíèæåíèå èõ ÷èñëà. Ïðè n=10
ôîðìóëà äàåò 9 696 000, ÷òî óæå â 1,238 ìåíüøå ôàêòè÷åñêî-
ãî ÷èñëà 12 005 168, íî îøèáêà åùå ñóùåñòâåííà. Ïðè n=12
ïîëó÷àåì ∼1, 54 · 1011 , âìåñòî ∼1, 65 · 1011 , ò. å. â 1,072 ðàçà
ìåíüøå. Íàêîíåö, ïðè n=15 ðàçíèöà ñîêðàùàåòñÿ äî îäíîãî
ïðîöåíòà.

   1.2. Ïîäãðàôû
     Ãðàô G0 (V 0 , E 0 ) íàçûâàþò ïîäãðàôîì ãðàôà G(V, E), åñëè
V 0 ⊆V è E 0 ⊆E , ïðè÷åì òàêèå, ÷òî ðåáðî {v, u} ñîäåðæèòñÿ â
E 0 òîëüêî òîãäà, êîãäà v∈V 0 è u∈V 0 .  ñâîþ î÷åðåäü, ãðàô
G ïî îòíîøåíèþ ê ñâîåìó ïîäãðàôó G0 ÿâëÿåòñÿ íàäãðàôîì.
     Îñòîâíûì íàçûâàþò ïîäãðàô G0 (V, E 0 ), âêëþ÷àþùèé â
ñåáÿ âñå âåðøèíû íàäãðàôà G(V, E).  êà÷åñòâå ïðèìåðà íà


                               10

Страницы