Grafų spalvinimas, poravimas ir tinklai

Keturiems užsiėmimams pakanka dviejų laiko intervalų

Užsiėmimus A ir B veda tas pats vedėjas, B ir C naudojama ta pati įranga, o C ir D veda tas pats vedėjas. Tai vieninteliai nesuderinamumai. Priskirkite A,C laiko intervalui 1, o B,D – laiko intervalui 2. Kiekviena nesuderinamų užsiėmimų pora vyksta skirtingais laiko intervalais; suderinama pora A,C gali vykti tuo pačiu laiko intervalu.

Užsiėmimus vaizduokite pažymėtomis viršūnėmis, o nesuderinamumus AB, BC, CD – neorientuotomis briaunomis. Spalvos numeris reiškia laiko intervalą, o ne tikrus dažus. Vieno laiko intervalo nepakanka, nes AB yra briauna. Mūsų paskirstymas į du laiko intervalus tinka, taigi du yra mažiausias galimas skaičius. Briauna yra apribojimas: ji nereiškia, kad du užsiėmimai turi vykti vienas po kito.

Prieš paskirstydami apibrėžkite objektus

„Skaičiavimas, nulis ir natūralieji skaičiai“ parengia darbui su baigtiniais objektų rinkiniais; „Sudėtis ir atimtis“ parengia balanso skaičiavimams; „Pavyzdžiai, paaiškinimai ir kontrpavyzdžiai“ parengia suprasti skirtumą tarp konstrukcijos ir įrodymo. Grafai ir aibių žymėjimas apibrėžiami čia. Pirmiausia perskaitykite užsiėmimų, poravimo ir srauto nukreipimo kitu keliu pavyzdžius; prie lyginumo, Hallo teoremos ir pjūvio įrodymų grįžkite, kai šie atvejai taps aiškūs ir konkretūs.

Spalvinant ir poruojant, grafas yra baigtinis, neorientuotas ir paprastasis: viršūnių žymenys skirtingi, kiekviena briauna jungia skirtingas viršūnes ir nė viena pora nesikartoja. Viršūnės v kaimynė su v sujungta briauna; viršūnės laipsnis yra jos kaimynių skaičius. Kelias yra skirtingų viršūnių seka, kurioje gretimos viršūnės sujungtos briauna, o jo ilgis yra briaunų skaičius. Vienos viršūnės kelio ilgis lygus nuliui. Ciklas turi bent tris briaunas ir grįžta į pradinę viršūnę, nekartodamas kitų viršūnių.

Maršrute viršūnės ir briaunos gali kartotis. Jungumo komponentė yra maksimali tarpusavyje pasiekiamų viršūnių grupė; izoliuota viršūnė pati sudaro komponentę. Brėžinyje susikertančios briaunos nesukuria viršūnių. Linijų ilgiai čia nėra atstumai, pralaidumai ar sąnaudos.

Aibę sudaro skirtingi objektai. Žymėjimas x ∈ S reiškia, kad x priklauso S; S ⊆ L reiškia, kad kiekvienas S elementas priklauso L. Skaičius |S| nurodo jos elementų skaičių, o ∅ yra tuščioji aibė. Skaidinys suskirsto visus objektus į nesikertančias grupes, kurių sąjunga yra visa aibė. Aprašant dvidalį grafą, leidžiamos ir tuščios grupės.

Nuspalvinimas įrodo viršutinį rėžį, apribojimas – apatinį

Taisyklingai spalvinant viršūnes, kiekvienai viršūnei priskiriama spalva taip, kad kiekvienos briaunos galai būtų skirtingų spalvų. Spalvos klasė yra vienos spalvos viršūnių aibė; ji nepriklausoma, tai yra nėra briaunos, kurios abu galai priklausytų tai pačiai klasei. Ir atvirkščiai: suskaidžius viršūnes į nepriklausomas klases, gaunamas taisyklingas nuspalvinimas.

Chromatinis skaičius χ(G) yra mažiausias reikalingas spalvų skaičius. Tuščiojo grafo χ = 0, nes nėra nė vienos viršūnės, kuriai reikėtų spalvos. Netuščio grafo be briaunų χ = 1. Bet kuriam netuščiam paprastajam grafui su n viršūnių galioja 1 ≤ χ ≤ n: būtina bent viena spalva, o kiekvienai viršūnei priskirti atskirą spalvą visada galima.

Klika yra viršūnių aibė, kurioje kiekvieną skirtingų viršūnių porą jungia briauna. q dydžio klikai būtinos q skirtingos spalvos, todėl χ ≥ q. Pateiktas nuspalvinimas k spalvų įrodo tik χ ≤ k. Norint įrodyti χ = k, reikia pateikti ir taisyklingą nuspalvinimą k spalvų, ir pagrindimą, kodėl mažesnio spalvų skaičiaus nepakanka.

Trikampyje yra trijų viršūnių klika, ir jį galima nuspalvinti trimis spalvomis, todėl χ = 3. Penkių viršūnių cikle A,B,C,D,E,A nėra trikampio: didžiausios jo klikos dydis yra 2, tačiau jam reikia 3 spalvų. Pakaitomis naudojant dvi spalvas išilgai penkių briaunų, paskutinė briauna neišvengiamai sujungia vienodos spalvos viršūnes. Nuspalvinimas A:1,B:2,C:1,D:2,E:3 yra taisyklingas. Klikos duodamas apatinis rėžis gali būti griežtai mažesnis už chromatinį skaičių.

Godusis spalvinimas taisyklingas, bet dėl eilės gali prireikti papildomos spalvos

Pasirinkite visų viršūnių eilę. Kiekvienai viršūnei priskirkite mažiausią teigiamu skaičiumi žymimą spalvą, kurios nenaudoja nė viena jau nuspalvinta gretima viršūnė. Kiekviena briauna patikrinama spalvinant vėlesnį jos galą, todėl gautas nuspalvinimas yra taisyklingas. Tegul Δ yra didžiausias netuščio grafo viršūnės laipsnis. Kiekviename žingsnyje draudžiama ne daugiau kaip Δ spalvų, todėl bent viena iš 1,…,Δ+1 yra galima. Tai įrodo χ ≤ Δ+1, bet neteigia, kad godžiuoju būdu gaunamas mažiausias spalvų skaičius.

Kai briaunos yra AB,BC,CD, eilė A,B,C,D duoda spalvas 1,2,1,2. Eilė A,D,B,C duoda A:1,D:1,B:2,C:3: viršūnės C kaimynė B turi spalvą 2, o kaimynė D – spalvą 1. Grafas nepasikeitė, ir mažiausias jo spalvų skaičius tebėra 2. Godusis algoritmas dėl pasirinktos eilės panaudojo 3 spalvas.

Godusis spalvinimas leidžia greitai rasti kokį nors leistiną paskirstymą. Norint patvirtinti, kad spalvų skaičius mažiausias, reikia jį atitinkančio apatinio rėžio arba išsamaus metodo, kuris atmestų kiekvieną mažesnį spalvų rinkinį. Baigtinių variantų tyrimo įrankis gali patikrinti visus priskyrimus pateiktiems mažiems grafams; ši nedidelė paieška nėra bendras greito optimizavimo pažadas.

Dvi dalys galimos tada ir tik tada, kai nėra nelyginio ciklo

Dvidalio grafo viršūnės suskirstytos į dalis L ir R taip, kad kiekviena briauna jungia skirtingų dalių viršūnes. Nuspalvinę L spalva 1, o R spalva 2, gauname taisyklingą spalvinimą ne daugiau kaip dviem spalvomis. Ir atvirkščiai, taisyklingo spalvinimo ne daugiau kaip dviem spalvomis klasės sudaro tokį padalijimą į dvi dalis. Taigi dvidalio grafo, turinčio bent vieną briauną, χ = 2, o tuščio grafo ir grafo be briaunų atvejais lieka anksčiau nustatytos vertės.

Spalvinant dviem spalvomis, spalvos išilgai ciklo kaitaliojasi. Kai briaunų skaičius nelyginis, grįžus į pradinę viršūnę jai reikėtų priešingos spalvos, o tai neįmanoma. Todėl dvidalis grafas neturi nelyginio ciklo.

Norėdami įrodyti atvirkštinį teiginį, kiekvienoje komponentėje pasirenkame šaknį ir kiekvienai viršūnei priskiriame trumpiausio kelio nuo šaknies iki tos viršūnės ilgio lyginumą: lyginis arba nelyginis. Komponentėje tokie baigtiniai trumpiausi keliai egzistuoja. Tarkime, briauna uv jungia vienodo lyginumo viršūnes. Einame trumpiausiu keliu nuo šaknies iki u, tada briauna uv ir galiausiai atvirkščia kryptimi trumpiausiu keliu nuo šaknies iki v. Tai nelyginio ilgio uždaras maršrutas, nes jo ilgis yra d(u)+1+d(v). Jame viršūnės gali kartotis, todėl reikia dar vieno argumento.

Kiekviename nelyginiame uždarame maršrute grafe be kilpų yra nelyginis paprastasis ciklas. Iš dalių, gaunamų skaidant maršrutą ties pasikartojančiomis viršūnėmis, pasirenkame mažiausio teigiamo ilgio nelyginį uždarą maršrutą. Pasikartojanti vidinė viršūnė padalija jį į du trumpesnius uždarus maršrutus; jų ilgių suma yra nelyginė, todėl vienas iš jų yra nelyginis, o tai prieštarauja minimalumui. Jei vidinės viršūnės nesikartoja, jo ilgis negali būti 1, nes kilpų nėra, arba 2, nes ilgis nelyginis. Taigi tai nelyginio ilgio ciklas, kurio ilgis ne mažesnis kaip 3. Vadinasi, mūsų briauna, jungianti vienodo lyginumo viršūnes, sudarytų nelyginį ciklą, priešingai prielaidai.

Todėl kiekviena briauna turi jungti skirtingų lyginumo klasių viršūnes. Atlikę tai kiekvienoje komponentėje, gauname padalijimą į dvi dalis, apimantį ir izoliuotas viršūnes. Keturių viršūnių ciklas ir žvaigždė turi briaunų, todėl jiems reikia 2 spalvų; penkių viršūnių ciklui reikia 3. Bendrasis įrodymas apima ir nejungius grafus, ir parodytus atvejus.

Poravimas parenka nesikertančias poras

Poravimas M yra briaunų aibė, kurioje jokios dvi briaunos neturi bendros galinės viršūnės. Viršūnė, priklausanti vienai iš šių briaunų, yra suporuota; bet kuri kita viršūnė yra nesuporuota. Tobulasis poravimas apima visas viršūnes. Dvidalio priskyrimo atveju poravimas prisotina L, kai apima visas kairiosios dalies viršūnes, net jei kai kurios dešiniosios dalies viršūnės lieka nepanaudotos.

Maksimalaus poravimo negalima padidinti tiesiog pridedant dar vieną briauną. Didžiausio dydžio poravimas turi didžiausią įmanomą briaunų skaičių iš visų poravimų. Didžiausias poravimas yra maksimalus, nes pridėjus tinkamą briauną jis taptų didesnis. Atvirkštinis teiginys negalioja: grafe su briaunomis AB,BC,CD poravimas {BC} yra maksimalus, nes abi kitos briaunos turi su juo bendrą viršūnę, tačiau {AB,CD} dydis yra 2.

Čia siekiama didinti porų skaičių, o briaunos neturi svorių. Kaštų ar pageidavimų sumos maksimizavimas yra kitas uždavinys. Panašiai, spalvinant viršūnes objektams priskiriamos klasės, o poravimu parenkamos poros. Jei spalvos priskiriamos pačioms briaunoms taip, kad bendrą viršūnę turinčios briaunos būtų skirtingų spalvų, kiekviena vienos spalvos briaunų klasė yra poravimas; tai briaunų spalvinimas, o ne mūsų viršūnių spalvinimo uždavinys. Trijų briaunų žvaigždei reikia dviejų viršūnių spalvų, bet trijų briaunų spalvų.

Pakaitinis kelias gali pakeisti trukdantį pasirinkimą

Poravimą M didinantis kelias yra kelias, kurio galinės viršūnės nesuporuotos, o briaunos pakaitomis nepriklauso M, priklauso M, nepriklauso M ir taip toliau iki M nepriklausančios briaunos kitame gale. Jo ilgis nelyginis. Šio kelio briaunas, priklausančias M, pakeičiame jo briaunomis, nepriklausančiomis M. Kiekviena vidinė viršūnė netenka vienos pasirinktos briaunos ir gauna vieną naują, o kiekviena galinė viršūnė gauna po vieną. Jokia kita pasirinkta briauna nėra incidentiška nesuporuotai galinei viršūnei ir neužima jau suporuotos vidinės viršūnės vietos. Naujoji aibė yra poravimas, turintis viena briauna daugiau.

Pradėjus nuo {BC}, kelyje A,B,C,D briaunos kaitaliojasi: AB nepriklauso poravimui, BC priklauso, CD nepriklauso. Sukeitus jų priklausomybę, gaunamas {AB,CD}. Norint pagerinti poravimą, reikėjo pašalinti anksčiau pasirinktą briauną ir tik tada pridėti dvi; tikrinant maksimalumą buvo tikrinta tik galimybė tiesiogiai pridėti vieną briauną.

Poravimas yra didžiausias tada ir tik tada, kai nėra jį didinančio kelio. Viena implikacija išplaukia iš ką tik įrodyto pagerinimo. Kitai implikacijai įrodyti tarkime, kad egzistuoja didesnis poravimas M′. Palikime briaunas, priklausančias tik vienam iš poravimų M, M′; tai jų simetrinis skirtumas. Kiekvienos viršūnės laipsnis šiame grafe yra ne didesnis kaip du, ir su ja incidenti ne daugiau kaip viena kiekvieno poravimo briauna. Kiekviena netriviali komponentė yra kelias arba ciklas, kurio briaunos pakaitomis priklauso abiem poravimams. Tai matyti pradėjus nuo pirmojo laipsnio galinės viršūnės arba einant per komponentę, sudarytą iš antrojo laipsnio viršūnių, kol kelias užsidaro.

Pakaitiniame cikle abiejų poravimų briaunų yra po lygiai. Kelyje jų skaičiai yra lygūs arba vieno poravimo briaunų yra viena daugiau. Kadangi visas poravimas M′ yra didesnis, bent viename kelyje M′ briaunų yra viena daugiau. Jis prasideda ir baigiasi M′ briaunomis. Jo galinės viršūnės poravime M yra nesuporuotos: ten esanti M briauna pratęstų komponentę; abiem poravimams bendra briauna negali turėti bendros viršūnės su M′ briauna, nes tai pažeistų poravimo sąlygą. Šis kelias didina M. Taip kriterijus įrodomas baigtiniams paprastiesiems grafams, ne tik dvidaliams.

Pradėję nuo tuščio poravimo ir jį vis didindami, būtinai sustosime: jo dydis kaskart padidėja vienetu ir negali viršyti pusės viršūnių skaičiaus, suapvalintos žemyn. Kai nebelieka didinančių kelių, kriterijus patvirtina, kad poravimas yra didžiausias. Ieškant tokių kelių bendruosiuose grafuose reikia atidumo; dvidaliam grafui pakanka kryptinės pakaitinės paieškos, pateikiamos kitame įrodyme.

Hallo sąlyga tikrina grupes, ne tik pavienius elementus

Tarkime, dvidalio grafo dalys yra L ir R. Kai S ⊆ L, žymėkime N(S) visas dešiniąsias viršūnes, gretimas bent vienai S viršūnei. Hallo sąlyga yra |N(S)| ≥ |S| kiekvienam L poaibiui S. Jei poravimas prisotina L, visos skirtingos su S viršūnėmis suporuotos viršūnės priklauso N(S), taigi ši sąlyga yra būtina. Tuščiasis poaibis neturi kaimynių ir tenkina 0 ≥ 0.

Baigtiniams grafams ši sąlyga yra ir pakankama. Pasirinkime didžiausią poravimą; jis egzistuoja, nes briaunų poaibių yra baigtinis skaičius. Tarkime, kad kairioji viršūnė u lieka nesuporuota. Nuo u ieškokime eidami nepasirinktomis briaunomis iš kairės į dešinę, o pasirinktomis – iš dešinės į kairę. Bet kuri pasiekta nesuporuota dešinioji viršūnė duotų didinantį kelią: pašalinus pasikartojančias kryptinės paieškos maršruto dalis, gautas pakaitinis kelias prasideda ir baigiasi nesuporuotomis viršūnėmis. Didžiausias poravimo dydis tokią galimybę atmeta.

Tegu S yra pasiektų kairiųjų viršūnių aibė, o T – pasiektų dešiniųjų viršūnių aibė. Kiekviena S viršūnės kaimynė priklauso T. Nepasirinkta briauna pereinama pirmyn; jei pasiekta kairioji viršūnė turi pasirinkta briauna sujungtą kaimynę, ta kaimynė jau buvo pasiekta prieš pereinant pasirinktą briauną, kuria aptikta ši kairioji viršūnė. Pradinė viršūnė u neturi pasirinkta briauna sujungtos kaimynės. Ir atvirkščiai, kiekviena pasiekta dešinioji viršūnė yra pasiektos kairiosios viršūnės kaimynė. Taigi T = N(S).

Kiekviena T viršūnė yra suporuota, o su ja suporuota viršūnė pasiekiama aibėje S. Kiekviena pasiekta kairioji viršūnė, išskyrus u, buvo aptikta einant tokia pasirinkta briauna, todėl šios poros nustato abipus vienareikšmę atitiktį tarp T ir S be u. Vadinasi, |S| = |T|+1, o tai prieštarauja Hallo sąlygai aibei S. Todėl nė viena kairioji viršūnė nelieka nesuporuota. Taip įrodomas pakankamumas; vienodi dalių dydžiai čia nelaikomi prielaida.

Kai L = {A,B,C}, R = {X,Y,Z}, imkime briaunas AX,AY,BX,CY,CZ. Priskyrimas AY,BX,CZ prisotina L. Jei kiekviena kairioji viršūnė būtų gretima tik X,Y, kiekvienas vienaelementis poaibis turėtų kaimynių, tačiau aibei S = L galiotų |N(S)| = 2 < 3. Pilnas priskyrimas neegzistuoja, nors nė viena kairiosios dalies viršūnė nėra izoliuota.

Orientuotasis tinklas paskirsto kiekius

Dabar briaunos turi kryptis ir pralaidumus. Baigtinis srautų tinklas turi skirtingas viršūnes – šaltinį s ir santaką t – bei orientuotus lankus u→v, kurių pralaidumai c(u→v) ≥ 0. Mūsų tinklų pralaidumai yra sveikieji skaičiai; juose nėra kilpų, pasikartojančių ar priešingų lankų, į s įeinančių lankų ir iš t išeinančių lankų. Šie susitarimai supaprastina apskaitą; atgaliniai judėjimai liekamajame tinkle nebus papildomi pradinio tinklo lankai.

Srautas kiekvienam pradinio tinklo lankui priskiria f(u→v), tenkinantį 0 ≤ f ≤ c. Kiekvienoje viršūnėje, išskyrus s,t, įeinančių srautų suma lygi išeinančių srautų sumai. Tai yra tvermė: tarpinė viršūnė srauto nei sukuria, nei kaupia. Srauto vertė |f| yra visas iš s išeinantis srautas; ji lygi visam į t įeinančiam srautui, nes sudėjus tvermės lygybes visi tarpiniai perdavimai panaikinami. Brūkšniai čia žymi srauto vertę, o ne aibės dydį.

Naudokite viršūnes s,a,b,t ir lankus s→a, s→b, a→b, a→t, b→t, kurių kiekvieno pralaidumas yra 1. Vieną vienetą siųsti keliu s,a,b,t galima: tiek a, tiek b gauna ir perduoda po 1. Šio srauto vertė yra 1, tačiau dar galima perduoti ir antrą vienetą. Lankų žymose nurodomas srautas / pralaidumas; jų padėtys ir ilgiai neatspindi nė vieno iš šių skaičių.

Pralaidumų neviršijantis skaičių sąrašas nebūtinai yra leistinas srautas. Pavyzdžiui, lankui s→a priskyrus srautą 1, o visiems kitiems lankams – srautą 0, viršūnėje a įtekančio ir ištekančio srauto skirtumas yra 1. Visada tikrinkite ne tik kiekvieno lanko pralaidumą, bet ir srauto tvermę.

Atgalinis žingsnis liekamajame tinkle atšaukia ankstesnį perdavimą

Jei pradinio lanko u→v srautas yra f, o pralaidumas – c, tiesioginiam žingsniui u→v liekamajame tinkle galima panaudoti kiekį c−f, kai jis teigiamas. Atgaliniam žingsniui v→u galima panaudoti kiekį f, kai jis teigiamas. Atgalinis žingsnis reiškia srauto atėmimą iš to pradinio lanko srauto. Tai nereiškia, kad medžiaga juda nauju atvirkštinės krypties pradiniu lanku.

Pasirinkite paprastą kelią nuo šaltinio iki santakos, sudarytą iš žingsnių su teigiamais liekamaisiais kiekiais. Tegul δ yra mažiausias liekamasis kiekis šiame kelyje. Prie kiekvieno tiesiogine kryptimi pereinamo pradinio lanko srauto pridėkite δ, o iš kiekvieno atgaline kryptimi pereinamo lanko srauto atimkite δ. Po kiekvieno pakeitimo srautas lieka tarp nulio ir pralaidumo. Vidinėje viršūnėje du liekamojo tinklo žingsniai vienodai padidina grynąjį įtekėjimą ir ištekėjimą, todėl srauto tvermė išlieka; šaltinis išsiunčia δ daugiau, o santaka gauna δ daugiau. Taigi srauto vertė padidėja δ.

Pirmąjį vienetą perdavus keliu s,a,b,t, pradinio lanko a→b srautas yra 1. Liekamojo tinklo kelio s,b,a,t kiekiai yra 1,1,1: tiesioginis žingsnis s→b, atgalinis žingsnis b→a, atitinkantis pradinį lanką a→b, ir tiesioginis žingsnis a→t. Šio kelio ribojantis kiekis yra δ = 1. Pridėkite jį prie s→b ir a→t srautų ir atimkite iš a→b srauto. Galutiniai pradinių lankų srautai yra s→a:1, s→b:1, a→b:0, a→t:1, b→t:1, o srauto vertė – 2.

Jei po pirmojo pasirinkimo algoritmas ieškotų tik nepanaudotų tiesioginių kelių, jis nepastebėtų šios galimybės padidinti srautą. Liekamojo tinklo kelias nusako leistinus esamo paskirstymo pakeitimus. Kas iš tikrųjų buvo atšaukta, patikrinama pagal visą pradinių lankų srautų lentelę, o ne vien pagal atvirkštinių rodyklių brėžinį.

Srauto ir pjūvio lygybė įrodo, kad srauto padidinti nebegalima

Šaltinį ir santaką skiriantis pjūvis yra visų tinklo viršūnių skaidinys S,T, kuriame s ∈ S ir t ∈ T. Jo pralaidumas yra pradinių lankų, nukreiptų iš S į T, pralaidumų suma. Pradiniai lankai, nukreipti iš T atgal į S, į šį pralaidumą neįskaičiuojami. Susumavus srauto tvermės lygybes visose S viršūnėse, vidinių lankų srautai susiprastina ir gaunama: |f| = per pjūvį ištekantis srautas minus per jį įtekantis srautas. Kadangi ištekantis srautas neviršija atitinkamo pralaidumo, o įtekantis srautas yra neneigiamas, kiekvienam leistinam srautui ir kiekvienam tokiam pjūviui galioja |f| ≤ pjūvio pralaidumas.

Galutiniame keturių viršūnių pavyzdyje |f| = 2, o pjūvio S = {s} pralaidumas yra 1+1 = 2. Šis rėžis ir leistinas paskirstymas įrodo, kad maksimalus srautas yra 2, o minimalus pjūvio pralaidumas – 2. Tarpinis srautas 1 su tuo pačiu pjūviu optimalumo neįrodytų.

Bendruoju atveju pradėkite nuo nulinio srauto ir pakartotinai didinkite jį išilgai liekamojo tinklo kelių su teigiamais liekamaisiais kiekiais, kol tokių kelių nebeliks. Kai pralaidumai sveikieji, visi srautai ir liekamieji kiekiai išlieka sveikieji. Kiekvienas δ yra bent 1, o srauto vertė negali viršyti baigtinės iš s išeinančių lankų pralaidumų sumos. Taigi procedūra baigiasi po ne daugiau nei tiek srauto didinimo žingsnių. Šis baigtinumo argumentas taikomas sveikiesiems pralaidumams; jis nepriklauso nuo toliau pateikiamos pjūvio lygybės.

Procedūrai pasibaigus, tegul S yra visos viršūnės, pasiekiamos iš s liekamojo tinklo žingsniais su teigiamais liekamaisiais kiekiais; t nepasiekiama. Kiekvienas pradinis lankas iš S į jos papildinį turi būti prisotintas: kitaip jo tiesioginis žingsnis liekamajame tinkle leistų pasiekti dar vieną viršūnę. Kiekvieno pradinio lanko, nukreipto atgal į S, srautas turi būti nulinis: kitaip tą patį leistų padaryti jo atgalinis žingsnis liekamajame tinkle. Todėl pjūvio tapatybė tampa |f| = iš jo išeinančių lankų pralaidumų suma. Tuomet bendrasis pjūvio rėžis įrodo, kad šis srautas yra maksimalus, o šis pjūvis – minimalus. Tai maksimalaus srauto ir minimalaus pjūvio išvada nurodytiems baigtiniams tinklams su sveikaisiais pralaidumais.

Tarpinio liekamojo tinklo pasiekiamų viršūnių aibėje gali būti t, todėl ji tuomet neapibrėžia šaltinį nuo santakos atskiriančio pjūvio. Naudokite ją kaip optimalumo liudijimą tik tada, kai nebelieka srautą didinančio kelio. Pasirinktas pjūvis gali apriboti bet kurią tarpinę srauto vertę, tačiau būtent lygybė patvirtina sėkmę.

Vienetiniai pralaidumai paverčia srautą atskirų porų parinkimu

Prie dvidalio grafo pridėkite šaltinį ir santaką. Nubrėžkite 1 pralaidumo lankus iš s į kiekvieną kairiąją viršūnę, iš kairiosios viršūnės į kiekvieną jai gretimą dešiniąją viršūnę ir iš kiekvienos dešiniosios viršūnės į t. Dydžio k poravimas duoda sveikaskaitį srautą, kurio vertė k: kiekvienu pasirinktu maršrutu s, kairioji viršūnė, dešinioji viršūnė, t siunčiama 1.

Ir atvirkščiai, sveikaskaičio leistino srauto vertė kiekviename lanke yra tik 0 arba 1. Šaltinio ir santakos lankai, kurių pralaidumas 1, kartu su srauto tvermės sąlyga leidžia ties kiekviena kairiąja ar dešiniąja viršūne naudoti ne daugiau kaip vieną lanką iš kairės į dešinę. Todėl šie naudojami lankai sudaro poravimą, kurio dydis lygus srauto vertei. Sveikaskaitė srauto didinimo procedūra pateikia tokį sveikaskaitį didžiausią srautą, taigi randa didžiausio dydžio dvidalio grafo poravimą. Vien trupmeninis leistinas srautas nėra pasirinktų porų sąrašas.

Kai A yra gretima X ir Y, o B – tik X, porų AY, BX parinkimas apima abi kairiąsias viršūnes. Jei abiem paliekamas tik X, lankas X→t apriboja srautą iki 1; nepakankamo dydžio kaimynų grupė paaiškina tą pačią kliūtį pagal Hallo sąlygą.

Šie modeliai išlaiko tiksliai užfiksuotus apribojimus. Viršūnių spalvos vaizduoja pakartotinai naudojamas klases, poravimai – atskiras poras, o srautai – tveriančius dydžius su pralaidumo apribojimais. Papildomoms trukmėms, pageidavimams, nedaliems siuntų dydžiams ar pokyčiams laike reikia papildomų prielaidų; vien nubrėžtų viršūnių perkėlimas jų neužkoduoja.

Numatykite, atskleiskite ir peržiūrėkite visą įrašą

Pakeiskite spalvinimo tvarką, poravimą, kairiųjų viršūnių poaibį, srauto etapą arba pjūvį. Įvesties įrašas nurodo pasirinktą klausimą prieš atskleidžiant rezultatą. Tada palyginkite savo prognozę su tiksliu spalvinimu, briaunų pasirinkimu, kaimynų sąrašu, pradinių lankų balansais arba pjūvio lentele.

Baigtinė paieška patikrina kiekvieną pateiktą atvejį ir gali atmesti siūlomą paskirstymą. Pirmiau pateiktos bendrosios išvados kyla iš jų įrodymų su nurodytomis sąlygomis, o ne vien iš šių mažų diagramų tikrinimo.

Išnagrinėti pavyzdžiai

Pabandykite patys

1. Nurodykite tuščiojo grafo ir grafo iš trijų izoliuotų viršūnių χ.

   Rodyti atsakymą ir paaiškinimą

   Atitinkamai 0 ir 1.

   Tuščiasis grafas neturi viršūnių, kurias reikėtų nuspalvinti. Netuščiam grafui be briaunų reikia vienos spalvos, ir nėra jokio konflikto, trukdančio ja nuspalvinti visas viršūnes.

2. Penkių viršūnių ciklo didžiausios klikos dydis yra 2. Ar tai įrodo, kad χ = 2?

   Rodyti atsakymą ir paaiškinimą

   Ne; χ = 3.

   Klika leidžia teigti tik tai, kad χ ≥ 2. Dviejų spalvų nepakanka, nes jas kaitaliojant nelyginiame cikle kyla konfliktas, o spalvos 1,2,1,2,3 išilgai ciklo duoda taisyklingą spalvinimą trimis spalvomis.

3. Žvaigždės centre esanti viršūnė sujungta su trimis lapais. Kiek spalvų reikia jos viršūnėms ir kiek – briaunoms nuspalvinti?

   Rodyti atsakymą ir paaiškinimą

   Viršūnėms – 2 spalvų, briaunoms – 3 spalvų.

   Visus lapus galima nuspalvinti viena spalva, o centre esančią viršūnę – kita. Visos trys briaunos turi bendrą viršūnę centre, todėl spalvinant briaunas kiekvienai reikia skirtingos spalvos.

4. Netuščio paprastojo grafo didžiausias viršūnės laipsnis yra 4. Kokia bendroji viršutinė riba iš to išplaukia ir ar ji įrodo lygybę?

   Rodyti atsakymą ir paaiškinimą

   χ ≤ 5; tai neįrodo, kad χ = 5.

   Kiekviename godžiojo algoritmo žingsnyje gretimų viršūnių spalvos neleidžia pasirinkti daugiausia keturių spalvų, todėl iš penkių lieka bent viena galima spalva. Vis dėlto gali pakakti ir mažiau spalvų.

5. Kodėl didžiausio dydžio poravimas būtinai yra maksimalus?

   Rodyti atsakymą ir paaiškinimą

   Jei būtų galima pridėti briauną, poravimo dydis padidėtų, o tai prieštarautų tam, kad jo dydis yra didžiausias.

   Čia tiesioginis pridėjimas naudojamas tik vienai implikacijai įrodyti. Maksimalų poravimą vis tiek gali būti įmanoma padidinti pakaitomis keičiant briaunas, kaip rodo keturių viršūnių kelias.

6. Kodėl Hallo sąlyga turi apimti kiekvieną poaibį, įskaitant ∅ ir visą kairiąją dalį?

   Rodyti atsakymą ir paaiškinimą

   ∅ tenkina 0 ≥ 0; didelė grupė gali netenkinti sąlygos, net jei kiekviena atskira viršūnė turi kaimynų.

   Jei trys kairiosios viršūnės turi kaimynų tik tarp dviejų dešiniųjų viršūnių, vienaelementės aibės tenkina sąlygą, tačiau visa kairiųjų viršūnių aibė turi tik dvi galimas skirtingas porininkes.

7. Ar vektorius 1,0,0,0,0 yra leistinas penkiuose lankuose s→a,s→b,a→b,a→t,b→t, kurių kiekvieno pralaidumas yra 1?

   Rodyti atsakymą ir paaiškinimą

   Ne.

   Jo reikšmės neviršija atskirų lankų pralaidumų, tačiau į a įteka 1, o išteka 0. Šioje tarpinėje viršūnėje netenkinama srauto tvermės sąlyga.

8. Pradinio lanko u→v pralaidumas yra 7, o srautas – 4. Nurodykite jo teigiamus liekamuosius pralaidumus tiesiogine ir atgaline kryptimis.

   Rodyti atsakymą ir paaiškinimą

   Tiesiogine kryptimi u→v:3; atgaline kryptimi v→u:4.

   Judant tiesiogine kryptimi galima pridėti 7−4 = 3. Judant atgaline kryptimi galima panaikinti daugiausia jau priskirtą srautą 4; tai nėra pradinis priešingos krypties lankas.

9. Pjūvyje yra iš S išeinantys pradiniai lankai, kurių pralaidumai yra 3 ir 4, ir vienas į S įeinantis lankas, kurio pralaidumas yra 9. Koks šio pjūvio pralaidumas?

   Rodyti atsakymą ir paaiškinimą

   7.

   Skaičiuojant orientuoto pjūvio pralaidumą, įskaitomi tik pradiniai lankai iš S į jo papildinį: 3+4 = 7. Įeinančio lanko pralaidumas 9 nepridedamas. Srauto vertės tapatybėje atimamas faktinis įeinantis srautas.

10. Leistinojo srauto vertė yra 5, o kurio nors šaltinį nuo santakos atskiriančio pjūvio pralaidumas yra 5. Ką tai įrodo?

    Rodyti atsakymą ir paaiškinimą

    Srautas yra maksimalus, o pjūvis – minimalus; abiejų vertė yra 5.

    Šio pjūvio pralaidumas yra kiekvieno leistinojo srauto vertės viršutinis rėžis, o šio srauto vertė yra kiekvieno pjūvio pralaidumo apatinis rėžis. Vienodos vertės patvirtina abiejų sprendinių optimalumą.

11. Iš s išeinančių lankų sveikųjų pralaidumų suma yra 8. Kodėl, pradėjus nuo nulinio srauto, srauto didinimo liekamajame tinkle procedūrai gali prireikti ne daugiau kaip aštuonių didinimų?

    Rodyti atsakymą ir paaiškinimą

    Kiekvienas didinimas padidina sveikąją srauto vertę bent 1, o jokia leistinoji vertė neviršija 8.

    Teigiami mažiausieji liekamieji pralaidumai išlieka sveikieji. Baigtinis pralaidumo rėžis įrodo procedūros baigtinumą nepriklausomai nuo įrodymo, grindžiamo galutiniu pjūviu.

Ką verta įsidėmėti

• Taisyklingasis spalvinimas yra paskirstymo sertifikatas; jo spalvų skaičius yra viršutinis rėžis, kol apatinis rėžis neįrodo, kad šis skaičius minimalus.
• Godusis spalvinimo algoritmas netuščiam paprastajam grafui naudoja ne daugiau kaip Δ+1 spalvų, tačiau skirtinga viršūnių tvarka gali lemti skirtingą spalvų skaičių.
• Baigtinis paprastasis grafas yra dvidalis tada ir tik tada, kai jame nėra nelyginio ilgio ciklo; jei yra briauna, būtinos dvi spalvos, o tuščio grafo ir grafo be briaunų kraštiniai atvejai skiriasi.
• Maksimaliojo poravimo negalima tiesiogiai papildyti; didžiausio dydžio poravimas neturi nė vieno didinančio kelio.
• Hallo sąlyga tikrina visus kairiosios dalies poaibius ir apibūdina poravimą, apimantį visas tos dalies viršūnes, nereikalaudama, kad abi dalys būtų vienodo dydžio.
• Srauto leistinumui būtina laikytis ir tvermės, ir pralaidumo apribojimų. Žingsnis atgal liekamajame tinkle panaikina pradinį srauto perdavimą.
• Baigtiniuose tinkluose su sveikaisiais pralaidumais srauto didinimas baigiasi, o galutiniame liekamajame tinkle pasiekiamų viršūnių aibė duoda didžiausią srautą ir mažiausią pjūvį, kurių vertės sutampa.