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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

G
1
G
2
G
1
s
v
1
sv
2
s
v
3
s
v
4
sv
5
c
c
c
c
B
B
B
B
B
#
#
#
#
s
v
6
s
v
7
s
v
8
s
v
9
s
v
10
B
B
B
B
B
c
c
c
c #
#
#
#
J
J
X
X
G
2
s
v
1
s
v
2
s
v
3
s
v
10
s
v
9
s
v
4
s
v
5
s
v
8
s
v
7
s
v
6
@
@
A
A
A
A
@
@
G
3
s
v
1
s
v
2
s
v
3
s
v
10
s
v
9
s
v
4
s
v
5
s
v
8
s
v
7
s
v
6
@
@
Q
Q
Q
Q
Q
Q
@
@
A
A
A
A
10!
G
1
G
3
G,
G.
èçîìîðôíû.  äàííîì ñëó÷àå ãðàôû äåéñòâèòåëüíî èçîìîðô-
íû, ïðè÷åì èõ ýêâèâàëåíòíûå âåðøèíû îáîçíà÷åíû (ïðîíóìå-
ðîâàíû) îäèíàêîâî. Çàäà÷à óñëîæíÿåòñÿ, åñëè ýêâèâàëåíòíûå
âåðøèíû ãðàôîâ èìåþò ðàçíûå íîìåðà.  êà÷åñòâå ïðèìåðà
ìîæíî ïðèâåñòè äâà èçîìîðôíûõ ãðàôà G1 è G2 , èçîáðàæåí-
íûå íà ðèñ. 1.2. Äëÿ íèõ îïèñàííóþ âûøå ïðîöåäóðó ðàáîòû
                vs1           v1           v2       v      v1          v2      v
                                  s         s       s3        s         s      s3
          # #c                  @                            @
        # sv6cc                     v@4
                                        s      sv5              v@4
                                                                    s     sv5
v5 s#
    XXs8v       B    v sv2
                       s9c              @                           @
    B c   c #     B #              v6 s @  s sv8
                                          v7                  v6 Qs @s sv8
                                                                      v
     B      c B                           A                      Q 7 AA
                                                                  
       B #s # cB s                           A                       Q A
            v      v                            AAs                     Q
        Bs 10 7 Js              s                          s             Q
                                                                            Q As
      v4                v3    v9                     v10   v9                  v10
                G1                        G2                           G3
                                     Ðèñ. 1.2
ñî ñïèñêàìè ïðèäåòñÿ ïîâòîðÿòü íåîäíîêðàòíî, êàæäûé ðàç
ìåíÿÿ íóìåðàöèþ âåðøèí îäíîãî èç ãðàôîâ, ïîêà íå áóäåò îá-
íàðóæåí èçîìîðôèçì, ò. å. ïîëó÷åíû èäåíòè÷íûå ñïèñêè âåð-
øèí.  ëó÷øåì ñëó÷àå ôàêò èçîìîðôíîñòè ãðàôîâ ìîæíî
óñòàíîâèòü ñ ïåðâîé ïîïûòêè, â õóäøåì ïîòðåáóåòñÿ ïðîâå-
ðèòü 10! âàðèàíòîâ íóìåðàöèè âåðøèí. Äîêàçàòü íåèçîìîðô-
íîñòü ãðàôîâ G1 è G3 ìîæíî, òîëüêî âûïîëíèâ âñå ïðîâåðêè.
Ñóùåñòâåííî ñîêðàòèòü èõ êîëè÷åñòâî ìîæíî, åñëè èñïîëüçî-
âàòü èíâàðèàíòû.
    Èíâàðèàíòîì íàçûâàþò íåêîòîðóþ õàðàêòåðèñòèêó ãðàôà
G, êîòîðàÿ ïðèíèìàåò îäíî è òî æå çíà÷åíèå äëÿ ëþáîãî ãðà-
ôà, èçîìîðôíîãî G.
    Èíâàðèàíòàìè ÿâëÿþòñÿ: ÷èñëî âåðøèí è ÷èñëî ðåáåð ãðà-
ôà, ÷èñëî âåðøèí ÷åòíîé è íå÷åòíîé ñòåïåíè, ñòåïåííàÿ ïîñëå-
äîâàòåëüíîñòü è äðóãèå ÷èñëîâûå õàðàêòåðèñòèêè.  êà÷åñòâå
èíâàðèàíòîâ ìîãóò âûñòóïàòü ñâîéñòâà è îñîáåííîñòè ãðàôà
(ñâÿçíîñòü, äâóäîëüíîñòü, íàëè÷èå èëè îòñóòñòâèå öèêëîâ è
ò. ï.), ðàññìàòðèâàåìûå äàëåå.
    Àíàëèç ãðàôîâ íà èçîìîðôíîñòü öåëåñîîáðàçíî íà÷èíàòü
ñî ñðàâíåíèèÿ çíà÷åíèé íåêîòîðîãî ìíîæåñòâà èíâàðèàíòîâ,
ïåðåõîäÿ îò ïðîñòûõ êî âñå áîëåå ñëîæíûì è òðóäîåìêèì.


                                             8

Страницы