Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
2.TEORIAGRAFÓW
Składowagrafuniespójnego–topodgrafspójnyrozłącznyzwszystkimi
pozostałymiwęzłamiigałęziamigrafuniespójnego,którenienależądodanej
składowej.Grafniespójnyzawieraprzynajmniejdwieskładowe–dwapodgrafy,
takie,żepomiędzywęzłamidotychpodgrafównależącyminieistniejeścieżka.
Węzełizolowanyjestrównieżuważanyzapodgrafbędącyskładowągrafu
niespójnego.
Liczbaskładowychgrafuniespójnegojestrównapowiększonejojeden,
najmniejszejliczbiegałęzi,któremuszązostaćdografudodane,abystałsięgrafem
spójnym.
Węzełprzegubowy(wierzchołekrozcinający)–towierzchołekgrafuspój-
nego,któregousunięcie(wrazzgałęziamiznimincydentnymi)powoduje,żegraf
stajesięniespójny.
Grafsilniespójny–tografspójny,któryniezawierawęzłaprzegubowego
(rozcinającego).
Grafsłabospójny–totakigrafspójny,wktórymmożnawybraćparęwęzłów
wtakisposób,żekażdamożliwaścieżkatewęzłyłączącazawierachoćjedeniten
samwęzeł.Inaczej:grafspójny,któryniejestgrafemsilniespójnym.Inaczej:graf
spójny,któryzawierawęzełprzegubowylubwęzełwiszący.
Gałąźwisząca–togałąź,którejusunięciepowoduje,żewgrafiewystąpi
węzełizolowany.Inaczej:gałąźincydentnazwęzłemwiszącym.
2030Przekrójgrafu
Przekrójgrafu(inaczej:rozcięciegrafu)–tozbiórgałęzi,którychusunięcie
powoduje,żegrafstajesięniespójny,podwarunkiemżeżadenzpodzbiorówtego
zbioruniematejwłaściwości.
Naprzykład:wszystkiegałęzieincydentnezwęzłemtworząprzekrój,oile
węzełniejestwęzłemprzegubowym.
zbiegającychsięwwęźleC,asątogałęzie:{b,c,d}.GrafG2(podgrafgrafuG1),
pousunięciutychgałęzistałsięniespójny,ztym,żematrzyskładowe(podgrafy).
Takzaproponowanyzbiórgałęziniejestprzekrojem,gdyżzezbiorugałęzimożna
wyodrębnićpodzbiór,któryrównieżpowoduje,żegrafG1stajesięniespójny.
Tęwłaściwośćmająpodzbiory{b,c}oraz{d},akażdyznichspełniakryteria
przekroju.
tj.{e,d,g},powoduje,żegrafG3stajesięniespójny(możnawyróżnićdwie
składowewgrafieG4).Natomiastpodzbiórgałęzi{e,d}takżepowoduje,żetak
52
