Élszínező algoritmus Misra és Gris számára

A Misra és Gris élszínező algoritmus egy polinomiális idő algoritmus a gráfelméletben , amely bármely gráf élszínezését megtalálja . A színezéshez maximum szín szükséges, ahol a grafikon maximális foka . Ez az érték néhány gráf esetében optimális, és a Vizing-tétel szerint egy színnel több, mint a többi gráf optimális színezése. $\Delta +1$ $\Delta$

Az algoritmust 1992-ben publikálta Jayadev Misra és David Gries [1] . Bolobash Béla [2] algoritmusának egyszerűsítése .

Ez az algoritmus a leggyorsabb az ismert, közel optimális élszínező algoritmusok közül, időben végrehajtva . Egy gyorsabb algoritmust végül Gabov és munkatársai egy 1985-ös technikai jelentésben jelentettek be, de soha nem publikálták [3] . $O(|E||V|)$ $O(|E|{\sqrt {|V|\log |V|)))$

Általános szabály, hogy az optimális élszínezés NP-teljes probléma, ezért nem valószínű, hogy létezik polinomiális idő algoritmus erre a problémára. Léteznek azonban olyan algoritmusok az élek pontos színezésére, amelyek exponenciális futási idővel optimális megoldást adnak.

Rajongók

Azt mondjuk, hogy egy x szín hiányzik az u csúcsból , ha minden (u, z) E(G) esetén. $c(u,z)\neq x$ $\ban ben$

Az u csúcsban lévő legyező az F[1:k] csúcsok sorozata, amely teljesíti a következő feltételeket:

F[1:k] u különböző szomszédjainak nem üres sorozata
Az (F[1], u) E(G) él nem színezett $\ban ben$
Az él színe (F[i+1], u) hiányzik az F[i] csúcsnál $1\leqslant i<k$

Adott egy F ventilátor, bármely él (F[i], X) a ventilátor éle . Legyen c és d két szín. A cd X útvonal az az útvonal, amely áthalad az X csúcson, csak c és d színű éleket tartalmaz , és maximális ({c, d} színnel nem adhatunk élt). Figyeljük meg, hogy X-nek csak egy ilyen útja van, mivel minden színnek legfeljebb egy éle lehet egy adott csúcsgal szomszédos. $1\leqslant i\leqslant k$

Ventilátor forgása

Adott egy X csúcs F [1: k ] ventilátora, a "ventilátorforgatás" művelet a következőket teszi (egyidejűleg):

c(F[i],X)=c(F[i+1],X)
Elszínteleníti az élt (F[k],X)

Ez a művelet helyesen hagyja a színezést, mert minden i -nél hiányzott a szín a -ból . $c(F[i+1],X)$ ${\megjelenítési stílus (F[i],X)}$

Útváltás

A "cd X elérési út újraszínezése" művelet az elérési út összes c színét d-re és d színt c - re változtat . Az útvonal megfordítása hasznos lehet egy szín felszabadításához X-ben, ha X az útvonal végső csúcsa - ha az X csúcs szomszédos volt a c színnel, de nem a d színnel , akkor most szomszédos lesz a d színnel, de nem a c színnel, ami felszabadítja a színt c egy másik X-szel szomszédos élre. A művelet alkalmazása nem sérti a színezés megengedhetőségét, mivel a végcsúcsoknál a {c, d} színek közül csak az egyik lehet szomszédos a csúcsgal, és az útvonal többi eleme esetén a művelet csak az élek színét váltja, új szín nem kerül hozzáadásra.

Algoritmus

Belépő: Gróf.

Kimenet: A G gráf éleinek megfelelő színezése

Legyen U := E(G)

Amíg U ≠ ∅ végrehajtódik

Vegyünk egy élt (u, v) U-ból.
Legyen F[1:k] az F[1]=v-től kezdődő maximális u ventilátor.
Legyen c az u-ban nem szereplő szín, d pedig az F[k]-ban nem szereplő szín.
Az útvonal megfordítása cd u
Legyen olyan, hogy ez egy ventilátor, és d hiányzik a w-ből. $w\in V(G)$ $w\in F,F'=[F[1]\dots w]$
Forgassa el az F'-et, és állítsa be c(u, w)=d.
U := U - {(u, v)}

vége viszlát

A helyesség igazolása

Az algoritmus helyességét három lépésben bizonyítjuk. Először is megmutatjuk, hogy a cd u útvonal átszínezése garantálja a w csúcsot úgy, hogy az egy rajongó, és d hiányzik w -ből . Akkor ez az élszínezés helyes és nem igényel több színt. $w\in F,F'=[F[1]\dots w]$ $\Delta +1$

Útvonal inverzió

Az útvonal újrafestése előtt két eset van:

A ventilátornak nincsenek d -vel színezett élei . Mivel F egy maximális ventilátor, és d hiányzik F [ k ]-ból, ebből következik, hogy nincs u mellett d színű él . Ellenkező esetben, ha létezne ilyen él, akkor F [ k ]-hez kapcsolódhatna, mivel d hiányzik F [ k ]-ból, de F maximális, ellentmondást kapunk. Ekkor d hiányzik u -ból , és mivel c is hiányzik u -ból, a cd u út üres, és az inverzió nem befolyásolja a gráfot. Hadd . $w=F[k]$
A ventilátor egyik éle d színű . Legyen (u,F[x+1]) ez az él. Vegye figyelembe, hogy mivel (u,F[1]) nem színezett. Ekkor az F [ x ] -ből hiányzik a d szín. Továbbá , mivel a ventilátor k hosszúságú , de létezik . Most megmutathatjuk, hogy az egyes elemek átszínezése után az F[y]-ben nincs szín . Vegye figyelembe, hogy az átszínezés előtt a szín nem egyezik sem c -vel, sem d -vel , mert a c nincs u -ban, de a d színt tartalmazza , és a színezés helyes. A megfordítás csak a c -vel vagy d - vel festett élekre vonatkozik , így az (1) érvényes. $x+1\neq 1$ $x\neq k$ $F[x+1]$ ${\displaystyle y\in \{1,\dots ,x-1,x+1,\dots ,k\))$ ${\megjelenítési stílus (F[y+1],u)}$ ${\megjelenítési stílus (u,F[y+1])}$ ${\megjelenítési stílus (u,F[x+1])}$

F [ x ] lehet , vagy nem szerepel a cd u útvonalban . Ha az elérési út nem tartalmazza, akkor az átszínezés nem befolyásolja az F [ x ] hiányzó színkészletét, és d hiányzik belőle. feltehetjük . Ellenkező esetben megmutathatjuk, hogy F fan marad, d pedig hiányzik F [ k ]-ból. Mivel d hiányzott az F [ x ]-ből az átszínezés előtt, és F [ x ] az útvonalon van, ezért F [ x ] a cd u útvonal végső csúcsa, és c hiányozni fog az F [ x ]-ből az átszínezés után . Az átfestés színe d -ről c -re változik . Aztán mivel c most hiányzik az F [ x ]-ből és az (1) teljesül, F ventilátor marad. Továbbá d hiányzik F [ k ]-ben, mert F [ k ] nincs a cd u útvonalon (feltételezve, hogy az úton van, de mivel d hiányzik az F [ k ]-ból, ez kell, hogy legyen az út végpontja, de a végpontok u és F [ x ]). Válasszunk . $w=F[x]$ ${\megjelenítési stílus (u,F[x+1])}$ $w=F[k]$

Mindenesetre a ventilátor az F előtagja , ami azt jelenti, hogy az is ventilátor. $F'$ $F'$

A szélek színezése megfelelő

Ez a színes élek számának matematikai indukciójával kimutatható . Indukciós alap: nincsenek színes élek, a színezés megfelelő. Indukciós lépés: Tegyük fel, hogy a színezés helyes volt az előző iterációban. Az aktuális iterációnál az útvonal átszínezése után d hiányzik u -ból , és az előző eredmény szerint w -ből hiányzik . A forgatás nem rontja el a megfelelő színezést. Ezután a beállítás után a színezés megfelelő marad. $F'$ $c(u,w)=d$

Az algoritmus maximum színt igényel $\Delta +1$

Egy adott lépésben csak c és d színek használhatók . Mivel u legalább egy színtelen éllel szomszédos, és foka korlátos , legalább egy szín elérhető c számára . d esetén F [ k ]-nek lehet foka , és nem lehetnek színezetlen szomszédos élei. Akkor szükséged lehet virágokra. $\Delta$ $\{1,\dots ,\Delta \}$ $\Delta$ $\Delta +1$

Nehézség

A forgatás minden lépésben eltávolítja az él színezését (u, w), míg a korábban színtelen éleket (u,F[1]) és (u, v) színezi. Így egy további színes él jelenik meg. Ezért a ciklus egyszer végrehajtásra kerül. A maximális ventilátor, c és d színek megtalálása és a cd u útvonal átszínezése időben elvégezhető . A w megtalálása és az F' elforgatása időbe telik. Egy él (u, v) megkeresése és törlése történhet egy veremmel konstans időben (az utolsó elem lekérésének művelete), és ez a verem időben kitölthető . Így a hurok minden egyes művelete időt vesz igénybe, és az algoritmus teljes futási ideje . $O(|E|)$ $O(|V|)$ $O(\deg(u))\in O(|V|)$ $O(|E|)$ $O(|V|)$ $O(|E|+|E||V|)=O(|E||V|)$

Jegyzetek

↑ Misra, Gries, 1992 , p. 131–133.
↑ Bollobás, 1982 , p. 94.
↑ Gabow, Nishizeki, Kariv, Leven, Terada, 1985 .

Irodalom

Jayadev Misra, David Gries . A Vizing-tétel konstruktív bizonyítása // Információfeldolgozási levelek . - 1992. - T. 41 , sz. 3 . - doi : 10.1016/0020-0190(92)90041-S .
Bollobas Béla. gráfelmélet. – Elsevier, 1982.
Harold N. Gabow, Takao Nishizeki, Oded Kariv, Daniel Leven, Osamu Terada. Algoritmusok élszínező gráfokhoz. - Tohoku Egyetem, 1985. - (TRECIS-8501 műszaki jelentés).