Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
2.4.KONTUR(CYKL)
Rozwiązanied
węzłów,żepomiędzyparamiwęzłówwybranymizposzczególnychpodzbiorów
nieistniejedroga.Tepodzbioryto:{A}–węzełodosobniony,{B,C,D}–podgraf
silniespójny,{E,F,G,H,I}–podgrafsłabospójny(zwęzłemprzegubowymG).
Zatemgrafmatrzyskładowe.
Rozwiązaniee
należydodaćprzynajmniejdwiegałęzie,abystałsięgrafemspójnym–niekoniecznie
silniespójnym.PołączeniewęzłówBiA(gałąźm),anastępnieAiG(gałąźn)
zapewniaspójnośćgrafu.PododaniugałęzipowstajegrafG
!
GrafG
!
2jestterazgrafemsłabospójnym,bezwęzłówwiszących,zawiera
natomiastdwawierzchołkiprzegubowe(tj.B,G).Należydodaćkolejnegałęzie,
takabywymienionewęzłyniebyływęzłamiprzegubowymi.
C
b
d
;
c
m
D
G2
'
A
n
E
f
G
g
j
h
F
i
I
k
H
C
b
d
;
c
m
D
G2
''
A
o
n
E
f
g
G
j
h
F
i
I
I
k
H
Rys020110KolejnegrafypowstałepododaniudoG2gałęziwceluzapewnieniasilnejspójności
Pododaniugałęzio(łączącejwęzłyDiE)orazp(łączącejFiH)grafG
!!
2staje
sięsilniespójny.ŁączniedografuG2dodanoczterygałęzie.
UWAGA:IstniejemożliwośćzapewnieniaspójnościsilnejgrafuG2zapomocą
trzechgałęzi.Abytobyłomożliwe,gałąźnpowinnałączyćwierzchołkiAiI,
dziękiczemuwęzełGprzestajebyćwęzłemprzegubowym.Wówczaspozostaje
dodać,takjakpoprzednio,gałąźoigrafstajesięsilniespójny.
.
K
2040Kontur(cykl)
utworzonyprzezgałęzie,incydentnezwęzłamistopnia2.Zwrot(orientacja)
konturu,jeżelijestistotny,określonyjestprzezkolejnośćgałęziwtymzbiorze
występujących.
9Kontur,wodróżnieniuodprzekroju,jestgrafem(podgrafem),stądróżnicawczcionkachużywanych
dooznaczaniakonturu(czcionkaprosta)iprzekroju(czcionkapochyła),któryjestzbioremgałęzi.
Dojednoznacznegoprzedstawieniakonturu(zewzględunajegodefinicję),takjakwprzypadku
przekroju,koniecznejestwypisaniejegogałęzi.Konturjednak,jakograf,zawieratakżewęzły(wdomyśle
incydentneztymigałęziami).
55
