Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
2.TEORIAGRAFÓW
Rozwiązaniea
WgrafieG1występujączterywęzłyprzegubowe,których
usunięciewrazzgałęziamiznimiincydentnymipowoduje,żegrafstajesię
niespójny(sątowęzły:B,D,E,G).Poszczególnefragmentygrafupousunięciu
C
b
d
;
c
D
a
A
e
C
b
d
;
c
D
a
A
e
E
f
g
D
e
E
f
g
G
j
i
F
h
e
E
f
g
G
j
h
F
i
I
k
H
Rys02080WęzłyprzeguboweoznaczonewwyróżnionychfragmentachgrafuG1
Wartowtymmiejscuzwrócićuwagęnato,dlaczegonp.węzłyCiAniesą
węzłamiprzegubowymi.Poichusunięciuwrazzodpowiednimi(incydentnymi)
!
1iG
!!
1niestająsięgrafaminiespójnymi–niemożna
wtymprzypadkuwyróżnićdwóchskładowychtakpowstającychgrafów.
G1
C
'
;
c
D
a
A
e
E
f
G
g
j
i
F
h
I
k
H
C
G1
b
''
d
;
c
D
A
e
E
f
G
g
j
h
F
i
I
k
H
Rys02090Węzłyniespełniającekryteriówwęzłówprzegubowych
Rozwiązanieb
GrafG1zawierawęzłyprzegubowe,cojestwarunkiem
wystarczającymdostwierdzenia,żejestgrafemsłabospójnym.
Rozwiązaniec
GrafG1zawieradwaprzekroje,któretworzonesąprzez
jednągałąź–sątozbiory{a}oraz{e}.Dodatkowogałąź{a},jakoincydentnaz
węzłemstopnia1(tj.węzłemA),jestgałęziąwiszącą–szczególnymprzypadkiem
powstałypousunięciuwymienionychprzekrojów.Jesttografniespójny.
C
G1
b
d
;
c
D
a
A
e
E
f
G
g
j
F
i
h
I
k
H
E
f
g
G
j
F
i
h
I
k
H
b
c
C
d
D
Rys020100GrafG1zwyróżnionymiprzekrojamiorazpodgrafG2
G2
;
A
54
