Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
2.TEORIAGRAFÓW
Pętlawłasna–toszczególnyprzypadekkonturu.
Oczko(lubokno)–toszczególnyprzypadekkonturu,którymożebyćtrak-
towanyjakopodgraf,któregoreprezentacjageometrycznajestbrzegiemobszaru
ograniczonego,którytoobszarniezawierażadnejgałęziwewnętrznej.
Przykład203
iG2.a)Utworzyćizapisaćkilkakonturówdlakażdegozgrafów.b)Wypisać
wszystkieoczka,któremogąbyćutworzonedlakażdegozgrafów.
G1
;
a
e
f
b
c
A
C
d
G2
b
'
;
'
a
e
f
'
'
'
c
'
A
C
'
'
d
'
Rys020120GrafyizomorficzneG1iG2
Rozwiązaniea
Przykładykonturówutworzonychzwykorzystaniemgałęzi
grafuG1to:K11{a,b},K21{a,c,e},K31{b,d,f}.Należyzauważyć,żewgra-
fieG2,izomorficznymwzględemgrafuG1,odpowiadającesobieskładowe(wę-
złyigałęzie)oznaczonotymisamymisymbolami,dodającapostrof.Przykładowe
konturywystępującewgrafieG2sąutworzoneprzezgałęziesobieodpowiadające,
możnawięczapisać:K
!
11{a
!
,b
!
},K
!
21{a
!
,c
!
,e
!
},K
!
31{b
!
,d
!
,f
!
}.
Rozwiązanieb
Przykładtenpokazuje,żespełnienieprzezkonturwymagań
postawionychoczkomzależytakżeodgraficznejreprezentacjigrafu.GrafyG1iG2
sąizomorficzne,istniejewięcwzajemnaodpowiedniośćkonturów.Wprzypadku
oczekjestinaczej.GrafG1zawieraczteryoczka.Sąto:011{a,b},021{b,c,e},
031{c,d},o41{e,f}.GrafG2zawieraczteryoczka.Posłużeniesięzbiorami
gałęzitworzącychoczkawgrafieG1niejestpoprawne.Oczko02zawieragałęzie
b,c,e.WgrafieG2gałęzie:b
!
,c
!
,e
!
tworząkontur,któryjednakniespełnia
kryteriówoczka.OczkawgrafieG2sąnastępujące:0
!
11{a
!
,b
!
},0
!
21{a
!
,c
!
,e
!
},
0
!
31{c
!
,d
!
},0
!
41{e
!
,f
!
}.
.
K
2050Drzewografu
205010Drzewografuspójnego
Drzewo–topodgrafspójnygrafuspójnego,któryzawierawszystkiejego
węzły,aniezawierakonturów.Gałęziedrzewanazywanesąkonarami.Liczba
56
