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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

d,
v
5
,
n. n C
2
n
n
C
2
n
n
l
n
=2
C
2
n
. n=10 l
10
=2
C
2
10
,
2
45
'3, 518 · 10
13
.
G
1
s
v
1
s
v
2
s
v
3
G
2
s
v
1
s
v
2
s
v
3
G
3
s
v
1
s
v
2
s
v
3
@
@
G
4
s
v
1
s
v
2
s
v
3
G
5
s
v
1
s
v
2
s
v
3
@
@
G
6
s
v
1
s
v
2
s
v
3
G
7
s
v
1
s
v
2
s
v
3
@
@
G
8
s
v
1
s
v
2
s
v
3
@
@
l
3
=2
C
2
3
=8
G
2
∼
=
G
3
∼
=
G
4
G
5
∼
=
G
6
∼
=
G
7
È òîëüêî åñëè âûáðàííàÿ ñèñòåìà èíâàðèàíòîâ íå ïîçâîëè-
ëà óñòàíîâèòü íåèçîìîðôíîñòü ãðàôîâ, ñëåäóåò ïðèñòóïàòü ê
ïåðåáîðó. Ïðè ýòîì êîëè÷åñòâî ïåðåáèðàåìûõ âàðèàíòîâ íó-
ìåðàöèè âåðøèí ìîæåò îêàçàòüñÿ ñóùåñòâåííî ìåíüøèì. Åñ-
ëè, íàïðèìåð, ïðè ñîâïàäåíèè ñòåïåííûõ ïîñëåäîâàòåëüíîñòåé
äâóõ ãðàôîâ â êàæäîì èç íèõ åñòü îäíà âåðøèíà ñòåïåíè d,
îáîçíà÷åííàÿ â ïåðâîì ãðàôå êàê v5 , òî èç âñåõ âîçìîæíûõ
íóìåðàöèé âåðøèí âòîðîãî ãðàôà ñëåäóåò ðàññìîòðåòü òîëüêî
òå, â êîòîðûõ âåðøèíà ýòîé ñòåïåíè èìååò òîò æå íîìåð.
    Ê ñîæàëåíèþ, ïîêà íå èçâåñòíà (âîçìîæíî è íå ñóùåñòâó-
åò) ñèñòåìà èíâàðèàíòîâ, ïîçâîëÿþùàÿ ðåøàòü çàäà÷ó èçî-
ìîðôèçìà äëÿ âñåõ âèäîâ ãðàôîâ.
   Êîëè÷åñòâî ãðàôîâ. Îïðåäåëèì ÷èñëî ãðàôîâ ïîðÿäêà
n. ßñíî, ÷òî íà ìíîæåñòâå èç n âåðøèí ìîæíî îáðàçîâàòü Cn2
ðàçëè÷íûõ íåóïîðÿäî÷åííûõ ïàð, ñîîòâåòñòâóþùèõ âñåì âîç-
ìîæíûì ðåáðàì ãðàôà. Ïîýòîìó ëþáîìó n-âåðøèííîìó ãðà-
ôó ìîæíî ñîîïîñòàâèòü Cn2 -ðàçðÿäíûé äâîè÷íûé êîä, êàæäûé
ðàçðÿä êîòîðîãî ñîîòâåòñòâóåò îïðåäåëåííîìó ðåáðó: åñëè ðàç-
ðÿä ðàâåí 1, ãðàô ñîäåðæèò ýòî ðåáðî, åñëè 0  íå ñîäåðæèò.
Ñëåäîâàòåëüíî, êîëè÷åñòâî ãðàôîâ ïîðÿäêà n ìîæíî îïðåäå-
                2                         2
ëèòü êàê ln =2Cn . Ïðè n=10 èìååì l10 =2C10 , ÷òî ñîñòàâëÿåò
âíóøèòåëüíóþ âåëè÷èíó 245 èëè '3, 518 · 1013 . Îäíàêî, åñ-
ëè íå ó÷èòûâàòü ðàçìåòêó âåðøèí, êîòîðàÿ ïðèíöèïèàëüíîãî
çíà÷åíèÿ íå èìååò, à ëèøü ïîçâîëÿåò îïèñàòü ñâÿçè ìåæäó âåð-
øèíàìè, íå âñå ýòè ãðàôû ðàçëè÷íû. Íàïðèìåð, ñóùåñòâóåò
    G1      G2      G3       G4      G5       G6      G7       G8
  v1 v2   v1 v2   v1 v2    v1 v2   v1 v2    v1 v2   v1 v2    v1 v2
   s s     s s     s s      s s     s s      s s     s s      s s
                   @                @                @        @
      s       s      @s        s      @s        s      @s       @s
     v3      v3       v3      v3       v3      v3       v3       v3

                              Ðèñ. 1.3
     2
l3 =2C3 =8 òðåõâåðøèííûõ ãðàôîâ. Âñå îíè ïðåäñòàâëåíû íà
ðèñ. 1.3. Ëåãêî çàìåòèòü, ÷òî ôàêòè÷åñêè åñòü ëèøü ÷åòûðå
ðàçëè÷íûõ òðåõâåðøèííûõ ãðàôà, ïîñêîëüêó G2 ∼   =G3 ∼
                                                    =G4 è
   ∼    ∼
G5 =G6 =G7 è, åñëè óáðàòü ìåòêè âåðøèí, ðàçëè÷èÿ ìåæäó



                               9

Страницы