Keliai, jungumas ir ciklai

Ar galite pasiekti laboratoriją per tris žingsnius?

Įsivaizduokite šešias vietas: vartus A, salę B, sodą C, kavinę D, laboratoriją E ir namelį F. Vienintelės tiesioginės jungtys yra AB, AC, BC, BD, CD ir DE. Kiekviena jungtimi galima judėti abiem kryptimis. Šiame modelyje namelis neturi jokių jungčių.

Maršrutas A,B,D,E eina trimis briaunomis: AB, BD ir DE. Maršrutas A,C,D,E taip pat eina trimis briaunomis. Tiesioginės jungties AE nėra, todėl užrašas A,E nesukuria vieno žingsnio kelionės. Sekite išvardytas jungtis, o ne spręskite pagal tai, kurie apskritimai brėžinyje atrodo arti vienas kito.

Naudokitės pasirengimo nuorodomis, kad galėtumėte skaičiuoti žingsnius, pateikti apibrėžimus ir patikrinti, ar paveikslas atitinka jo duomenis. Ankstesnė pamoka apie grafus, jei ji prieinama, gali suteikti papildomos praktikos; visos būtinos grafų sąvokos apibrėžtos čia. Vėlesnių pamokų apie algoritmus ar medžius žinių nereikalaujama.

Skaitydami pirmą kartą, sekite maršrutų palyginimus, komponentes ir atstumo sluoksnius. Prie pasikartojančių viršūnių apėjimų šalinimo ir tiltų įrodymų grįžkite, kai galėsite paaiškinti šešių vietų pavyzdį. Įrodymai paaiškina, kodėl metodas veikia ne tik šiame konkrečiame brėžinyje.

Grafą ir maršrutą apibrėžkite atskirai

Grafą sudaro viršūnių aibė V ir briaunų aibė E. Čia viršūnės žymi vietas, o briauna {u,v} nurodo tiesioginę jungtį. Riestiniai skliaustai reiškia, kad {u,v} ir {v,u} yra ta pati neorientuota briauna. Dvi viršūnės, kurias jungia briauna, yra gretimos.

Šioje pamokoje nagrinėjami baigtiniai paprastieji neorientuotieji grafai: jie turi baigtinį viršūnių skaičių, neturi briaunų iš viršūnės į ją pačią, o kiekvieną nesutvarkytą skirtingų viršūnių porą jungia ne daugiau kaip viena briauna. Brėžinys vaizduoja šiuos duomenis. Linijų susikirtimo vietoje nauja viršūnė neatsiranda, nebent ji ten aiškiai pažymėta.

Viršūnių seka v₀,v₁,…,vₘ nusako siūlomą maršrutą. Ji yra maršrutas tada ir tik tada, kai visos jos viršūnės priklauso V ir kiekvieną gretimų sekos viršūnių porą jungia briauna. Jo ilgis yra m – žingsnių briaunomis skaičius, o ne m+1 – sekos narių skaičius. Pasikartojantys nariai taip pat užima vietas sekoje.

Viena grafo viršūnė pati savaime yra nulinio ilgio maršrutas. Tuščia seka čia nelaikoma maršrutu, nes joje nėra pradinės viršūnės. Seka, kurioje trūksta briaunos, nėra maršrutas, net jei tuos pačius galus jungia kitas galiojantis maršrutas.

Kokie pasikartojimai leidžiami?

Maršrute viršūnės ir briaunos gali kartotis. Grandinė yra maršrutas, kuriame nesikartoja nė viena briauna. Kelias yra maršrutas, kuriame nesikartoja nė viena viršūnė. Taigi kiekvienas kelias yra grandinė, o kiekviena grandinė yra maršrutas. Atvirkštinės implikacijos nebūtinai galioja.

Tame pačiame tinkle A,B,A,C,D yra maršrutas, bet ne grandinė: AB dar kartą naudojama kaip BA, nes kryptis nepaverčia neorientuotosios briaunos kita briauna. Seka B,A,C,B,D yra grandinė: jos briaunos BA, AC, CB ir BD visos skirtingos. Ji nėra kelias, nes B pasirodo du kartus.

A,B,D,E yra kelias, nes visos keturios jo viršūnės skirtingos. Vienos viršūnės seka F taip pat yra nulinio ilgio kelias ir grandinė. Kad maršrutas būtų kelias, jis neprivalo eiti per kiekvieną viršūnę ar kiekviena briauna.

Skirtingose knygose terminai vartojami nevienodai. Visoje šioje pamokoje kelias reiškia, kad visos jo sekos viršūnės yra skirtingos. Ciklas atskirai apibrėžiamas toliau ir pagal šį susitarimą keliu nevadinamas. Prieš lygindami maršrutų pavadinimus, nurodykite taikomą susitarimą.

Vien grįžti į pradžią nepakanka

Uždaro maršruto pirmoji ir paskutinė viršūnės sutampa. Kontūru čia vadinama uždara grandinė, turinti bent vieną briauną. Ciklas yra bent trijų briaunų ilgio uždaras maršrutas, kurio visos viršūnės iki galutinio grįžimo yra skirtingos. Paprastajame neorientuotajame grafe toks ciklas eina skirtingomis briaunomis, todėl jis yra kontūras.

A,B,C,A yra trijų briaunų ilgio ciklas. Paskutinė A žymi grįžimą; jokia kita viršūnė nesikartoja. A,B,A yra dviejų briaunų ilgio uždaras maršrutas, bet ne kontūras: ta pačia briauna AB einama du kartus. Tai nėra ciklas. Viena viršūnė yra nulinio ilgio uždaras maršrutas, bet nei kontūras, nei ciklas.

Kontūras gali eiti per tą pačią viršūnę daugiau nei vieną kartą. Pavyzdžiui, du trikampiai, turintys tik vieną bendrą viršūnę, leidžia sudaryti uždarą grandinę, kuri apeina abu trikampius ir pakartotinai aplanko bendrą viršūnę. Toks kontūras nėra ciklas. Taigi briaunų ir viršūnių apribojimai atsako į skirtingus klausimus.

Maršrute tarp dviejų viršūnių yra kelias

Pradiniame tinkle A,B,C,B,D yra 4 ilgio maršrutas. Dalis B,C,B grįžta į B. Pašalinkite C ir vėlesnę B, palikdami ankstesnę B: A,B,D yra 2 ilgio kelias. Briauna BD vis dar jungia paliktą pradinę dalį su D. Greta pateikta sekos diagrama rodo, kurie viršūnių pasikartojimai pašalinami.

Tarkime, baigtiniame maršrute iš u į v kartojasi viršūnė: pozicijose i<j yra ta pati viršūnė. Pašalinkite dalį po pozicijos i iki pozicijos j imtinai. Palikta pradinė dalis baigiasi ta pačia viršūne, todėl ją galima sujungti su palikta galine dalimi per pradinę kitą galinės dalies briauną. Galinės viršūnės lieka u ir v, net jei kartojasi viena iš jų.

Taip pašalinama j−i briaunų, o šis skaičius yra teigiamas. Kartokite veiksmą, kol yra pasikartojančių viršūnių. Ilgis negali mažėti be galo ir tapti neigiamas, todėl procedūra baigiasi maršrutu, kurio visos viršūnės yra skirtingos: keliu su tomis pačiomis galinėmis viršūnėmis. Jei u=v, procedūra baigiasi nulinio ilgio keliu viršūnėje u.

Taigi maršrutas tarp dviejų viršūnių egzistuoja tada ir tik tada, kai egzistuoja kelias. Ši procedūra negarantuoja trumpiausio kelio: pašalinus vieną pasirinktą apėjimą, gali likti kitų ilgesnių variantų. Tačiau ji įrodo, kad trumpiausiame maršrute negali būti pasikartojančios viršūnės, nes pašalinus tokį apėjimą maršrutas sutrumpėtų.

Grupuokite viršūnes pagal pasiekiamumą

Viršūnė v yra pasiekiama iš u, kai iš u į v eina maršrutas arba, lygiavertiškai, kelias. Kiekviena viršūnė pasiekia save nulinio ilgio keliu. Neorientuotajame grafe pasiekiamumas yra simetrinis, nes maršrutu galima eiti priešinga kryptimi. Jis yra tranzityvus, nes du suderinamus maršrutus galima sujungti; jei reikia kelio, pasikartojančią viršūnę sujungtame maršrute galima pašalinti.

Jungumo komponentė yra maksimali viena iš kitos pasiekiamų viršūnių grupė. Maksimali reiškia, kad kiekviena viršūnė, pasiekiama iš kurios nors grupės viršūnės, jau priklauso tai grupei. Komponentės sudaro V skaidinį: kiekviena viršūnė priklauso vienai komponentei, skirtingos komponentės negali persidengti ir jokia briauna nejungia skirtingų komponenčių. Jei dvi tokios grupės turėtų bendrą viršūnę, sujungę per ją einančius maršrutus galėtume sujungti jų viršūnes; dėl maksimalumo šios grupės būtų ta pati grupė.

Mūsų tinklo komponentės yra {A,B,C,D,E} ir {F}. Jungčių neturintis namelis pati sudaro komponentę. Iš A jos pasiekti negalima, tačiau iš F ją galima pasiekti per nulį žingsnių. Negalėjimas pasiekti tikslo nėra tas pats, kas pasiekti jį įveikus nulinį atstumą.

Čia grafas vadinamas jungiu, jei jis turi bent vieną viršūnę ir lygiai vieną komponentę. Lygiavertiškai, jis yra netuščias ir kiekvieną viršūnių porą jungia kelias. Grafas su viena viršūne yra jungus. Grafas be viršūnių neturi komponenčių ir pagal mūsų aiškiai pasirinktą susitarimą nėra jungus; kai kuriuose tekstuose šiam ribiniam atvejui taikomas kitoks susitarimas.

Minimizuoti nurodytą dydį

Kai viršūnės u ir v yra pasiekiamos viena iš kitos, nesvertinis atstumas d(u,v) yra mažiausias briaunų skaičius kelyje iš u į v. Minimumas egzistuoja: ilgiai yra neneigiami sveikieji skaičiai ir egzistuoja bent vienas kelias. Trumpiausias kelias turi ne daugiau kaip |V|−1 briaunų, nes jame negali kartotis viršūnė. Minimumą gali pasiekti keli keliai.

Mūsų tinkle d(A,E)=3. Šį minimumą pasiekia ir A,B,D,E, ir A,C,D,E. Maršrutas A,B,C,D,E turi keturias briaunas ir taip pat yra kelias, tačiau ilgesnis. Be to, d(F,F)=0, o baigtinis atstumas iš A į F nepriskiriamas, nes kelio nėra.

Atstumai skaičiuoja jungtis, o ne nubrėžtų atkarpų ilgius. Jei tikrų kelių įveikimo laikas ar ilgis skiriasi, maršrutas su mažiausiu briaunų skaičiumi nebūtinai minimizuoja šiuos svorius. Orientuotuose grafuose taip pat reikia tikrinti leistinas kryptis. Šie kitokie modeliai nepatenka į šioje pamokoje nagrinėjamos paieškos nesvertiniame neorientuotame grafe sritį.

Pirmiausia tikrinti vieno žingsnio tęsinius, tada – dviejų

Pradėkite nuo sluoksnio L₀={A}. Visas dar neįtrauktas A kaimynes įrašykite į L₁={B,C}. Tada patikrinkite kiekvieną L₁ viršūnę; jos kaimynės, kurių nėra ankstesniuose sluoksniuose, sudaro L₂={D}. Tęsdami gauname L₃={E}. Toliau neatsiranda jokios naujos viršūnės, todėl paieška baigiasi. F nė karto nepasirodė ir yra nepasiekiama.

Ši procedūra vadinama paieška į plotį. Kiekvieną aptiktą viršūnę įtraukite tik kartą ir kaip jos tėvinę viršūnę užrašykite vieną ankstesnio sluoksnio viršūnę, iš kurios ji buvo aptikta. Sekant tėviniais ryšiais atgal sudaromas kelias į pradžią. Kaimynių tikrinimo tvarka gali pakeisti pasirinktą tėvinę viršūnę ir tai, kuris trumpiausias kelias bus grąžintas, tačiau atstumų ji nekeičia.

Norėdami pagrįsti sluoksnius, tarkime, kad ankstesniuose sluoksniuose yra būtent tos viršūnės, kurių mažiausi atstumai atitinka nurodytuosius. Naujai į Lₖ₊₁ įtraukta viršūnė briauna sujungta su Lₖ, todėl ją pasiekia k+1 ilgio maršrutas. Trumpesnio maršruto būti negali: priešpaskutinė trumpesnio maršruto viršūnė jau būtų ankstesniame sluoksnyje ir būtų ją aptikusi anksčiau. Ir atvirkščiai, bet kuri viršūnė, kurios atstumas yra k+1, turi priešpaskutinę viršūnę, kurios atstumas yra k, todėl ji bus įtraukta. Pradėdami nuo L₀, teiginį įrodome sluoksnis po sluoksnio.

Kai nebelieka naujų viršūnių, kiekvienos pasiektos viršūnės kiekviena kaimynė jau yra pasiekta. Maršrute iš pradžios į nepasiektą viršūnę turėtų būti pirmoji briauna, išeinanti iš pasiektų viršūnių grupės, o tai prieštarautų šios grupės uždarumui. Taip nepasiekiamumas įrodomas, o ne spėjamas iš brėžinio. Baigtinė paieška baigiasi aptikus ne daugiau kaip |V| viršūnių.

Ciklas leidžia apeiti briauną

Jungumas ir ciklų buvimas yra skirtingos savybės. Grandinė A–B–C–D–E yra jungi ir neturi ciklų. Mūsų pradinis tinklas turi ciklų, bet yra nejungus, nes F yra izoliuota viršūnė. Jungus grafas taip pat gali turėti ciklą.

Briauna yra tiltas, jei ją pašalinus ir palikus visas viršūnes padidėja komponenčių skaičius. Pradiniame tinkle DE yra tiltas: E praranda vienintelę savo jungtį. BC nėra tiltas: ją pašalinus, B ir C lieka sujungtos per A arba D, o abi pradinės komponentės nesuskyla.

Baigtiniame paprastajame neorientuotajame grafe briauna yra tiltas tada ir tik tada, kai ji nepriklauso jokiam ciklui. Jei ji priklauso ciklui, likusi to ciklo dalis sujungia jos galines viršūnes be šios briaunos. Kiekvieną perėjimą pašalinta briauna pakeiskite tuo alternatyviu maršrutu, išlaikydami pasiekiamumą. Todėl pašalinus tokią briauną komponentė negali suskilti.

Ir atvirkščiai: jei pašalinus briauną jos galinės viršūnės lieka pasiekiamos viena iš kitos, likusiame grafe pasirinkite jas jungiantį kelią. Grąžinus briauną, šis kelias uždaromas į ciklą. Kelias turi bent dvi briaunas, nes paprastajame grafe nėra antros briaunos tarp tų pačių galinių viršūnių. Taigi jokiam ciklui nepriklausančios briaunos galinės viršūnės ją pašalinus atskiriamos, todėl ši briauna yra tiltas. Ši išvada remiasi nurodytu paprastojo neorientuotojo grafo modeliu.

Patikrinkite samprotavimą konkrečiu pavyzdžiu

Pasirinkite siūlomą maršrutą ir numatykite jo klasifikaciją bei paskirties viršūnės pasiekiamumą. Atverkite visą žingsnių lentelę, komponentes, mažiausius briaunų skaičius ir visus trumpiausius kelius tarp tų galinių viršūnių. Rėmeliais pažymėti atstumų langeliai vaizduoja sluoksnius, o ne kitą geografinį žemėlapį. Paprastieji ciklai pateikiami tik po vieną kartą, neatsižvelgiant į pradinės viršūnės pasirinkimą ir kryptį, nes taip aprašomas tas pats neorientuotasis ciklas.

Pateikti grafai turi ne daugiau kaip šešias viršūnes. Baigtiniai jų elementų sąrašai leidžia atlikti išsamią patikrą; įrodymai paaiškina bendrąsias išvadas apie baigtinius grafus. Netinkama siūloma seka nepanaikina kito tinkamo kelio, o tinkama seka gali baigtis ne toje paskirties viršūnėje, kurios prašoma. Patikrinkite ir seką, ir klausime nurodytas galines viršūnes.

Išnagrinėti pavyzdžiai

Pabandykite patys

1. Kodėl A,B,D,E ilgis yra 3, o ne 4?

   Rodyti atsakymą ir paaiškinimą

   Šioje sekoje yra keturi viršūnių įrašai ir trys nuoseklūs žingsniai briaunomis.

   Trys žingsniai atliekami briaunomis AB, BD ir DE. Ilgis skaičiuojamas pagal žingsnius, įskaitant pasikartojančius, o ne pagal įrašus.

2. Ar A,B,A yra grandinė arba ciklas pradiniame neorientuotajame grafe?

   Rodyti atsakymą ir paaiškinimą

   Nei grandinė, nei ciklas. Tai uždaras maršrutas, kurio ilgis yra 2.

   AB ir BA žymi tą pačią neorientuotą briauną, todėl briauna kartojasi. Čia ciklo ilgis yra bent 3, ir iki galutinio grįžimo nė viena viršūnė nesikartoja.

3. Ar tai, kad siūloma seka A,E nėra maršrutas, reiškia, kad E nepasiekiama iš A?

   Rodyti atsakymą ir paaiškinimą

   Ne. A,B,D,E ir A,C,D,E yra keliai.

   Seka A,E nėra maršrutas, nes nėra briaunos AE. Pasiekiamumas reiškia, kad egzistuoja bent vienas maršrutas, o ne kad viena pasirinkta seka yra maršrutas.

4. Du keliai susitinka bendroje galinėje viršūnėje. Ar juos sujungus būtinai gaunamas kelias?

   Rodyti atsakymą ir paaiškinimą

   Ne; visada gaunamas maršrutas, tačiau jame gali kartotis viršūnė.

   Mūsų grafe sujunkime kelius A,B,C ir C,B,D. Gautame maršrute A,B,C,B,D kartojasi B ir briauna BC. Pašalinus uždarą apėjimą, lieka A,B,D.

5. Grafas turi viršūnes A,B,C,D,E ir tik briaunas AB bei CD. Išvardykite jo jungumo komponentes ir nustatykite, ar jis jungus.

   Rodyti atsakymą ir paaiškinimą

   Jungumo komponentės yra {A,B}, {C,D} ir {E}; grafas nejungus.

   E yra izoliuota vienos viršūnės jungumo komponentė. Jokia briauna nejungia šių trijų grupių, todėl joks maršrutas nejungia skirtingų grupių viršūnių.

6. Ar pagal šioje pamokoje taikomą susitarimą vienos viršūnės grafas ir grafas be viršūnių yra jungūs?

   Rodyti atsakymą ir paaiškinimą

   Vienos viršūnės grafas yra jungus; tuščiasis grafas nėra jungus.

   Vienos viršūnės grafas turi vieną jungumo komponentę ir nulinio ilgio kelią iš savo viršūnės į ją pačią. Tuščiasis grafas neturi nė vienos jungumo komponentės, o jungumo apibrėžime aiškiai reikalaujama, kad viršūnių aibė būtų netuščia.

7. Ar paieška į plotį, kuri C nagrinėja prieš B, galėtų rasti kitą trumpiausią kelią iš A į E? Ar ji galėtų gauti kitą atstumą?

   Rodyti atsakymą ir paaiškinimą

   Ji gali pasirinkti pagal tėvines viršūnes sudarytą kelią A,C,D,E, o ne A,B,D,E. Atstumas lieka 3.

   Ir B, ir C yra sluoksnyje 1 ir gali aptikti D sluoksnyje 2. Pasirinkimas tarp lygiaverčių tėvinių viršūnių nekeičia pirmojo aptikimo sluoksnio, nustatyto atstumo įrodymu.

8. Pateikite jungų grafą be ciklo ir nejungų grafą su ciklu.

   Rodyti atsakymą ir paaiškinimą

   Grandinė A–B–C–D–E yra jungi ir neturi ciklo. Pradiniame šešių vietų grafe yra ciklas A,B,C,A, tačiau dėl izoliuotos viršūnės F jis yra nejungus.

   Jungumas susijęs su kiekviena viršūnių pora, o ciklas – su konkrečiu uždaru maršrutu. Nė viena iš šių savybių nenulemia kitos.

9. Ar ciklui priklausanti briauna gali būti tiltas paprastajame neorientuotajame grafe?

   Rodyti atsakymą ir paaiškinimą

   Ne. Pašalinus šią briauną, likusi ciklo dalis suteikia maršrutą tarp jos galinių viršūnių.

   Pašalintos briaunos panaudojimą pakeiskite tuo alternatyviu maršrutu. Pasiekiamumas pradinėje jungumo komponentėje išlieka, todėl pašalinimas nepadidina jungumo komponenčių skaičiaus.

10. Tiesioginiu keliu važiuoti trunka 20 minučių; dviejų briaunų maršrutu važiuoti trunka po 5 minučių kiekviena briauna. Kuris maršrutas turi mažiau briaunų, o kuris yra greitesnis?

    Rodyti atsakymą ir paaiškinimą

    Tiesioginis kelias turi mažiau briaunų: 1, o ne 2. Maršrutas iš dviejų briaunų yra greitesnis: 10, o ne 20 minučių.

    Atstumas nesvertiniame grafe minimizuoja briaunų skaičių. Skirtingi svoriai, nusakantys kelionės laiką, apibrėžia kitą tikslą, kuriam vien šio paieška į plotį gauto atstumo rezultato nepakanka.

Ką verta įsidėmėti

• Maršrutas eina nurodytomis briaunomis; grandinėje nė viena briauna nesikartoja; kelyje pagal čia taikomą susitarimą nė viena viršūnė nesikartoja.
• Ciklas grįžta į pradinę viršūnę tik pabaigoje ir paprastajame neorientuotajame grafe turi bent tris briaunas; ėjimas viena briauna pirmyn ir atgal nėra ciklas.
• Nulinio ilgio keliai užtikrina, kad kiekviena viršūnė pasiekiama iš savęs, įskaitant izoliuotas viršūnes. Nepasiekiama paskirties viršūnė nėra tas pats, kas nulinis atstumas.
• Jungumo komponentės yra maksimalios tarpusavyje pasiekiamų viršūnių grupės. Čia grafas yra jungus tada ir tik tada, kai jis yra netuščias ir turi vieną komponentę.
• Paieškos į plotį sluoksniai nusako mažiausią briaunų skaičių nesvertiniame grafe; skirtingai pasirinkus pirmtaką iš lygiaverčių variantų, galima gauti skirtingus trumpiausius kelius.
• Nurodytame baigtinio paprastojo neorientuotojo grafo modelyje briauna yra tiltas tada ir tik tada, kai ji nepriklauso jokiam ciklui.