Élszínezés

Innen: testwiki
Ugrás a navigációhoz Ugrás a kereséshez
Fájl:Desargues graph 3color edge.svg
A Desargues-gráf 3-élszínezése.

A matematika, azon belül a gráfelmélet területén egy gráf élszínezése során színeket rendelnek hozzá a gráf éleihez. Általában jó élszínezésekkel foglalkoznak, melyek során az ugyanabból a csúcsból kiinduló élek mindig különböző színűek. Például a jobb oldali ábrán látható élszínezés három színt (piros, kék, zöld) használ. Az élszínezés a gráfok lehetséges színezéseinek csak egyetlen típusa.

Az élszínezési probléma azt vizsgálja, hogy jól színezhetők-e adott gráf élei legfeljebb Sablon:Mvar különböző színnel, adott Sablon:Mvar-ra, illetve a lehető legkevesebb szín felhasználásával. Az adott gráf éleihez szükséges minimális színek számát a gráf élkromatikus számának vagy kromatikus indexének nevezik. Az illusztráción látható gráf élei kiszínezhetők három színnel, de kettővel nem, ezért a gráf élkromatikus száma három.

A Vizing-tétel értelmében az egyszerű gráf élszínezéséhez szükséges színek száma vagy a maximális fokszáma, Sablon:Math vagy Sablon:Math. Egyes gráfok esetében, mint a páros gráfok vagy magas fokszámú síkbarajzolható gráfok, a kromatikus index mindig Sablon:Math, multigráfok esetén pedig akár Sablon:Math is lehet. Léteznek polinom idejű algoritmusok páros gráfok optimális színezésének, illetve nem páros egyszerű gráfok legfeljebb Sablon:Math-színezésének előállítására; az optimális élszínezés általános esetben azonban NP-nehéz feladat és a legjobb ismert algoritmusok is exponenciális idejűek. Az élszínezési problémának számos olyan változatát tanulmányozták, ahol a színek hozzárendelésekor a szomszédosság elkerülése mellett egyéb feltételeknek is teljesülniük kell. Az élszínezések gyakorlati szerepet kapnak az ütemezési problémákban és az optikai hálózatok frekvenciakiosztásában.

Példák

Egy páros hosszúságú körgráf élei két színnel kiszínezhetők, egyszerűen a két színt váltakozva kell a kör éleihez hozzárendelni. Ha azonban a kör páratlan hosszúságú, egy harmadik színre is szükség van.[1]

Fájl:Complete-edge-coloring.svg
A Sablon:Math teljes gráf 7-élszínezésének mértani konstrukciója. A hét színosztály mindegyikéhez tartozik egy-egy él a középpontból a sokszög egy csúcsához, és három, az elsőre merőleges él.

Egy Sablon:Mvar teljes gráf Sablon:Math-élszínezhető, amennyiben Sablon:Mvar páros; ez a Baranyai-tétel speciális esete. Sablon:Harvtxt a következő geometriai konstrukciót adja a színezésre: helyezzünk el Sablon:Mvar pontot egy Sablon:Math-oldalú szabályos sokszög csúcsaiba és középpontjába. Minden színosztályhoz adjunk hozzá egy a középpontból a sokszög valamely csúcsába menő élt, és a rá merőleges éleket. Ha azonban Sablon:Mvar páratlan, Sablon:Mvar színre van szükség: az egyes színek csak Sablon:Math élhez tartozhatnak, az összes él Sablon:Math részéhez.[2]

Több szerző tanulmányozta a páratlan gráfok élszínezéseit. A páratlan gráfok olyan Sablon:Mvar-reguláris gráfok, melyeknek csúcsai Sablon:Mvar méretű játékoshalmazból kiválasztott Sablon:Math játékost jelképez, és melyek élei ezen csapatok összes lehetséges párosítását jelképezi (ahol egy játékos páratlan marad, ő a döntőbíró). Az Sablon:Math esetnek a jól ismert Petersen-gráf felel meg. Sablon:Harvtxt az Sablon:Math esetre úgy írja le a problémát, hogy a játékosok olyan időbeosztást keresnek a párosításokhoz, hogy minden csapat az összesen hat meccsét a hét különböző napján játssza, vasárnap pedig mindenki számára pihenőnap lehessen; matematikailag leírva a 6-reguláris páratlan gráf (Sablon:Math) 6-élszínezését keresik. Ha Sablon:Mvar 3, 4 vagy 8, az Sablon:Math élszínezéséhez Sablon:Math színre van szükség, de ha 5, 6 vagy 7, elegendő Sablon:Mvar szín is.[3]

Definíciók

Ahogy az ellenpáros csúcsszínezésre is igaz, a gráf élszínezése alatt külön jelző nélkül is az élek „jó” színezése értendő, amikor a szomszédos – itt: ugyanabból a csúcsból kiinduló – élek mindig különböző színűek. A Sablon:Mvar gráf egy élszínezése ekvivalensnek tekinthető az Sablon:Math élgráf csúcsszínezésének (az élgráf csúcsai az eredeti gráf éleinek, élei pedig az eredeti gráf szomszédos élpárjainak felelnek meg).

Egy Sablon:Mvar különböző színnel történő jó élszínezést (jó) Sablon:Mvar-élszínezésnek neveznek. Az a gráf, amihez tartozik (jó) Sablon:Mvar-élszínezés, Sablon:Mvar-élszínezhető. Az a legkevesebb szín, amivel Sablon:Mvar élszínezhető, a Sablon:Mvar-hez tartozó élkromatikus szám vagy kromatikus index, Sablon:Math. Az élkromatikus számot néha Sablon:Math-vel is jelölik, az alsó indexben lévő egyessel arra utalva, hogy az élek egydimenziós objektumok. Egy gráf akkor Sablon:Mvar-élkromatikus, ha kromatikus indexe éppen Sablon:Mvar. Az élkromatikus szám nem tévesztendő össze a csúcsszínezéshez szükséges színeket számoló kromatikus számmal, melynek jele Sablon:Math vagy Sablon:Math.

Ha külön nem jelöljük, a cikkben szereplő gráfok mind egyszerűek, nem pedig multigráfok, melyekben többszörös élek, esetleg hurokélek is megengedettek. Az élszínezési problémákban az egyszerű gráfok viselkedése jelentősen eltér a multigráfokétól, így nem kevés odafigyelést igényel az élszínezési tételek kiterjesztése egyszerű gráfokról multigráfokra.

Párosítással való kapcsolata

Fájl:Class-2-planar-3-regular.svg
Ennek a 3-reguláris síkbarajzolható gráfnak 16 csúcsa és 24 éle van, de a maximális elemszámú párosításai csak 7 élt tartalmaznak. Ezért élszínezéséhez négy színre van szükség.

Egy gráfhoz tartozó párosítás az adott gráfon belül közös csúccsal nem rendelkező élek halmaz; egy teljes párosítás olyan párosítás, mely a gráf összes csúcsát lefedi, egy maximális elemszámú párosítás pedig olyan párosítás, ami a gráf lehető legtöbb élét tartalmazza. Élszínezéskor az azonos színű élek egymással nem lehetnek szomszédosak, ezért párosítást alkotnak. Tehát a gráf egy jó élszínezése ugyanazt jelenti, mint a gráf diszjunkt párosításokba particionálását.

Ha adott gráf maximális elemszámú párosítása kis méretű, sok párosításra lesz szükség a gráf összes éleinek lefedéséhez. Ebből a gondolatmenetből formálisabban az következik, hogy ha egy gráf összesen Sablon:Mvar éllel rendelkezik, melyek közül legfeljebb Sablon:Math él tartozik egy maximális elemszámú párosításhoz, akkor a gráf minden élszínezésében legalább Sablon:Math különböző színnek kell szerepelnie.[4] Például az ábrán látható 16 csúcsú síkgráfnak Sablon:Math éle van. Ebben a gráfban nem lehet szó teljes párosításról; hiszen, ha a középső csúcsot párosítjuk, a megmaradó párosítatlan csúcsok három különböző összefüggő komponensbe különülnek el, melyek négy, öt, illetve öt csúcsból állnak, a páratlan csúcsból álló komponensek pedig nem párosíthatók teljesen. A gráf maximális elemszámú párosítása hét élt tartalmaz, tehát Sablon:Math. Így a gráf élszínezéséhez legalább 24/7 szín szükséges, és mivel a színek száma csak egész szám lehet, legalább négy.

Ha egy Sablon:Mvar fokszámú reguláris gráfban nincs teljes párosítás, az iménti alsó korlát segítségével belátható, hogy legalább Sablon:Math színre lesz szükség.[4] Ha specifikusan egy páratlan számú csúccsal rendelkező reguláris gráfot tekintünk (például a páratlan teljes gráfokat), az ilyen gráfokban a kézfogási lemma miatt Sablon:Mvar-nak párosnak kell lennie. Azonban a Sablon:Math egyenlőtlenség nem magyarázza meg teljesen a reguláris gráfok kromatikus indexét, vannak ugyanis olyan reguláris gráfok, melyekben van teljes párosítás, mégsem k-élszínezhetők. Például a Petersen-gráf reguláris, Sablon:Math és Sablon:Math éllel teljes párosításaiban, mégsem létezik 3-élszínezése.

Fokszámmal való kapcsolata

Vizing-tétel

Sablon:Fő A Sablon:Mvar gráf élkromatikus száma szorosan kapcsolódik a Sablon:Math maximális fokszámhoz, ami egyben megadja a Sablon:Mvar bármely csúcsából kiinduló élek maximális számát. Az nyilvánvaló, hogy Sablon:Math, hiszen ha Sablon:Math különböző él ugyanabban a Sablon:Mvar csúcsban találkozik, akkor ezekhez az éleknek mind különböző színeket kell rendelni, ami csak akkor lehetséges, ha legalább Sablon:Math szín kiosztható. A Vizing-tétel állítása szerint ez a korlát csaknem éles: bármely gráf élkromatikus száma vagy Sablon:Math, vagy Sablon:Math. Ha Sablon:Math, G az 1. osztályba tartozik (class 1); egyébként a 2. osztályba (class 2).

Minden páros gráf,[5] és csaknem minden véletlen gráf is az 1. osztályba tartozik.[6] Annak eldöntése azonban, hogy tetszőleges gráf az 1. osztályba tartozik-e, NP-teljes nehézségű feladat.[7]

Sablon:Harvtxt bebizonyította, hogy a legalább nyolc maximális fokszámú síkbarajzolható gráfok az 1. osztályba tartoznak, és sejtése szerint ugyanez igaz azokra, melyek maximális fokszáma hat vagy hét. Másrészről léteznek olyan síkbarajzolható gráfok, melyek maximális fokszáma kettő és öt közötti, és a 2. osztályba esnek. A sejtést azóta bebizonyították a hét maximális fokszámú gráfokra.[8] Az hídmentes síkbarajzolható 3-reguláris gráfok mind az 1. osztályba tartoznak; ez a négyszíntétellel ekvivalens állítás.[9]

Reguláris gráfok

Egy k-reguláris gráf 1-faktorizációja a gráf éleit teljes párosításokba particionálja, ami megegyezik a gráf k-élszínezésével. Más szóval, egy reguláris gráfnak pontosan akkor létezik 1-faktorizációja, ha az 1. osztályba tartozik. Ennek speciális eseteként a 3-reguláris gráfok 3-élszínezését néha Tait-színezésnek is hívják.

Nem minden reguláris gráf 1-faktorizálható; például a Petersen-gráf sem. Általánosabban a snarkokat úgy definiálják, mint a gráfok, melyek a Petersen-gráfhoz hasonlóan hídmentesek, 3-regulárisok és a 2. osztályba tartoznak.

Sablon:Harvtxt tétele szerint minden páros reguláris gráfnak van 1-faktorizációja. A tételt korábban a projektív konfigurációk kontextusában Ernst Steinitz fogalmazta meg és bizonyította.

Multigráfok

Fájl:Multigraph-edge-coloring.svg
Egy Shannon-multigráf, hatos fokszámmal és hármas él-multiplicitással, aminek élszínezéséhez legalább kilenc színre van szükség

A multigráfokra, melyekben két csúcsot több, párhuzamos él is összeköthet, szintén léteznek a Vizing-tételhez hasonló, de annál gyengébb eredmények, melyek az Sablon:Math élkromatikus számot, a Sablon:Math maximális fokszámot és a Sablon:Math multiplicitást (a párhuzamos élcsomagokban lévő maximális élszámot) hozzák összefüggésbe. Az, hogy a Vizing-tétel nem általánosítható egyszerűen multigráfokra, egyszerűen belátható, ha egy Shannon-multigráfot tekintünk. Ez egy három csúcsból és három élkötegből álló multigráf, melynek három csúcsát páronként Sablon:Math párhuzamos él köti össze. Az ábrán látható példában Sablon:Math (az egyes csúcsok a háromból csak két élköteghez csatlakoznak), de az élkromatikus szám Sablon:Math (összesen Sablon:Math él van a multigráfban, és bármely két él szomszédos, ezért az összes élnek különböző színűnek kell lennie). Egy Vizinget is megihlető eredményében[10] Sablon:Harvtxt megmutatta, hogy az ábrán a legrosszabb eset látható: Sablon:Math bármely Sablon:Mvar multigráfra. Ezen felül bármely Sablon:Mvar multigráfra igaz a Sablon:Math egyenlőtlenség, ami egyszerű gráfok esetén (melyekre Sablon:Math) a Vizing-tételre redukálódik.

Algoritmusok

Mivel annak tesztelése, hogy egy gráf az 1. osztályba tartozik-e, NP-teljes, ezért nem ismert olyan polinom idejű algoritmus, ami minden gráfot optimálisan élszínezne. Léteznek azonban algoritmusok, melyek egyes kritériumok lazításával hatékonyan tudnak működni: csak bizonyos gráfosztályokon működnek, nem minden esetben használnak optimális számú színt vagy nem minden esetben futnak le polinom idő alatt.

Egyes gráfosztályok optimális színezése

Páros gráfok, illetve Sablon:Math maximális fokszámú multigráfok esetén a színek optimális száma éppen Sablon:Math. Sablon:Harvtxt megmutatta, hogy ezeknek a gráfoknak az optimális színezése Sablon:Math, azaz csaknem lineáris időben megtalálható, ahol Sablon:Mvar a gráf éleinek száma; egyszerűbb, de valamivel lassabb algoritmusokat ír le Sablon:Harvtxt és Sablon:Harvtxt. Sablon:Harvtxt algoritmusa indulásakor a bemeneti gráfot regulárissá alakítja anélkül, hogy fokszámát növelné vagy jelentősen megnövelné a méretét: a párosítás ugyanazon részébe tartozó egyes csúcspárokat összevon, néhány csúcsot és élt hozzáad a gráfhoz. Ezután ha a fokszám páratlan, Alon közel lineáris időben keres egy teljes párosítást, hozzárendel egy színt, majd eltávolítja a gráfból, ami után a fokszám párossá válik. Végül Alon alkalmazza Sablon:Harvtxt megfigyelését, miszerint a gráf Euler-útjának éleit váltakozva kiválasztva a gráfot két reguláris részgráffá lehet particionálni, ezzel az élszínezési problémát két kisebb részproblémára felosztva; algoritmusa ezután a két részproblémát rekurzív módon oldja meg. Az algoritmus teljes időigénye Sablon:Math.

A Sablon:Math maximális fokszámú síkbarajzolható gráfok esetén a színek optimális száma pontosan Sablon:Math. Ha az erősebb feltétel is teljesül, miszerint Sablon:Math, az optimális élszínezés lineáris időben megtalálható Sablon:Harv.

Az optimálisnál több színt használó algoritmusok

A Sablon:Harvtxt és Sablon:Harvtxt által leírt polinom idejű algoritmusok; lásd Misra & Gries élszínezési algoritmusa.

Multigráfok esetén Sablon:Harvtxt a következő, Eli Upfalnak tulajdonított algoritmust írja el. Alakítsuk át a bemeneti Sablon:Mvar multigráfot: a páratlan fokszámú csúcsokhoz adjunk egy vele éllel összekötött csúcsot, így lesz a gráfban Euler-séta; ezután keressünk egy Euler-sétát és válasszunk számára egy orientációt. Alakítsunk ki egy Sablon:Mvar páros gráfot, melyben Sablon:Mvar minden csúcsának két kópiája szerepel, a bipartíció mindkét oldalán egy-egy, és bipartíció bal oldalán található Sablon:Mvar csúcstól akkor vezet él a jobb oldalán található Sablon:Mvar csúcshoz, ha Sablon:Mvar orientált Euler-sétájában szerepel Sablon:Mvar-ból Sablon:Mvar-be vezető él. Alkalmazzunk egy páros gráf-élszínező algoritmust Sablon:Mvar-ra. Sablon:Mvar minden színosztálya Sablon:Mvar olyan élhalmazának felel meg, ami egy kettő maximális fokszámú részgráfot alkot; tehát utak és körök diszjunkt unióját, így Sablon:Mvar minden színosztályához lehetséges három Sablon:Mvar-beli színosztályt alkotni. Ezen algoritmus időigénye a páros gráf élszínezési idejéhez kötött, ami Sablon:Harvtxt algoritmusát használva Sablon:Math. A felhasznált színek száma legfeljebb 3⌈Δ2⌉, ami közel van, ha nem is éri el a ⌊3Δ2⌋ Shannon-korlátot. Viszonylag egyszerűen párhuzamos algoritmussá is alakítható. Ugyanebben a cikkben Karloff és Shmoys bemutatnak egy lineáris idejű algoritmust, ami három maximális fokszámú multigráfokat négy színnel élszínez (ami Shannon és Vizing korlátainak is megfelel). Ez az algoritmus hasonló elven működik: új csúcs hozzáadásával biztosítja az Euler-séta létezését, megkeresi a sétát, majd a séta váltakozó éleinek kiválasztásával a gráfot két részgráfra bontja, melyek maximális fokszáma kettő. Ezeknek a részgráfoknak az útjai és páros körei két-két színnel színezhetők. A lépést követően minden megmaradó páratlan kör tartalmaz legalább egy olyan élt, aminek színezéséhez az ellentétes részgráf valamelyik színét lehet választani. A páratlan színből ezt ez élt eltávolítva egy út marad, ami a saját részgráf két színével élszínezhető.

Egy olyan mohó színezési algoritmus, ami egyenként vizsgálja a gráf vagy multigráf éleit, és minden élhez az első elérhető színt társítja, néha akár Sablon:Math színt is felhasználhat, ami csaknem kétszerese az optimális élszínezéshez szükségesnek. Előnye viszont, hogy online algoritmusban is alkalmazható, amikor a bemeneti gráf nem ismert előre; ebben a kontextusban versenyképességi hányadosa kettő, ami optimális: egyetlen online algoritmus sem érhet el ennél jobb teljesítményt.[11] Ha azonban az élek véletlenszerűen érkeznek és a bemeneti gráf fokszáma legalább logaritmikus, akkor kisebb versenyképességi hányadosok is elérhetők.[12]

Több szerző állított fel sejtést arra nézve, hogy tetszőleges multigráf frakcionális élkromatikus száma (egy olyan szám, ami lineáris programozás segítségével polinom időben számítható) legfeljebb eggyel tér el az élkromatikus számtól.[13] Ha ezek a sejtések igaznak bizonyulnak, legfeljebb egy eltéréssel kiszámítható lenne a multigráfok élkromatikus száma, ami az egyszerű gráfok esetében a Vizing-tételnek felel meg. Általános esetben ezek a sejtéseket nem sikerült bizonyítani vagy cáfolni, biztosan igazak viszont abban az esetben, ha az élkromatikus szám legalább Δ+Δ/2, ami az elegendően nagy multiplicitású multigráfoknál előfordul.[14]

Egzakt algoritmusok

Könnyen tesztelhető, hogy egy gráf élszínezhető-e egy vagy két színnel, így az élszínezés első nem triviális esete annak vizsgálata, hogy adott gráf 3-élszínezhető-e. Ahogy Sablon:Harvtxt megmutatta, egy gráf 3-élszínezhetőségének tesztelése Sablon:Math időben és polinom tárban elvégezhető. Bár ez az idő exponenciális, még így is lényegesen gyorsabb az összes lehetséges szín-él-hozzárendelés brute force-keresésénél. Minden Sablon:Mvar csúcsú, kétszeresen összefüggő 3-reguláris gráfnak Sablon:Math 3-élszínezése van, melyek Sablon:Math időben listázhatók (valamivel lassabban egyetlen színezés megkeresésénél); Greg Kuperberg megfigyelése szerint egy Sablon:Math-oldalú sokszög alapú hasáb gráfjának Sablon:Math színezése van (az O jelölés szerint itt alsó, nem pedig felső korlátról van szó), amiből következik, hogy ez a korlát éles.[15]

A bemeneti gráf élgráfjára egzakt csúcsszínezési algoritmusokat alkalmazva bármely Sablon:Mvar élű gráf optimális élszínezése lehetséges, a szükséges színek számától függetlenül, Sablon:Math időben és exponenciális tárban, vagy Sablon:Math időben és csak polinom tárban Sablon:Harv.

Mivel az élszínezés már három szín esetén is NP-teljes, valószínűtlen, hogy a színek száma szerint paraméterezve rögzített paraméter mellett kezelhető lenne. Kezelhető azonban más paramétereket választva. Sablon:Harvtxt megmutatta, hogy Sablon:Mvar favastagságnál az optimális élszínezés Sablon:Math időben kiszámítható, ami Sablon:Mvar-től ugyan szuperexponenciálisan függ, de a gráf csúcsainak Sablon:Mvar számának csak lineáris függvénye.

Sablon:Harvtxt az élszínezési problémát egészértékű programozási eszközökkel definiálta és leírta tapasztalatait, amit egészértékű megoldóprogrammal szerzett gráfok élszínezésében. Nem végzett azonban bonyolultsági vizsgálatot a felhasznált algoritmusokon.

További tulajdonságok

Fájl:Generalized Petersen 9 2 Hamiltonicity.svg
Az egyedi 3-színezéssel rendelkező Sablon:Math általánosított Petersen-gráf. A három színosztály egyikét a világos élek jelölik, a másik kettő megkapható vagy a világos élek 40°-os pozitív, illetve negatív irányú elforgatásával, vagy a sötét Hamilton-kör alternáló élekre particionálásával.

Egy gráf egyedi Sablon:Mvar-élszínezéssel rendelkezik ha pontosan egyféleképpen lehet az éleit Sablon:Mvar színosztályba particionálni, nem tekintve a színek Sablon:Math lehetséges permutációját (permutáció erejéig). A Sablon:Math esetben egyedi Sablon:Mvar-élszínezéssel kizárólag utak, körök és csillagok rendelkeznek, de a Sablon:Math esetben néhány további gráf is egyedileg Sablon:Mvar-élszínezhető. Minden egyedi 3-élszínezhető gráfnak pontosan három Hamilton-köre van (melyek a három színosztály valamelyikének törlésével állnak elő), de léteznek 3-reguláris gráfok három Hamilton-körrel, melyek nem egyedileg 3-élszínezhetők: ilyenek például a Sablon:Math általánosított Petersen-gráfok bármely Sablon:Math-re. Az egyetlen ismert nem síkbarajzolható egyedi 3-élszínezhető gráf a Sablon:Math általánosított Petersen-gráf, és egy sejtés szerint nincs is több ilyen.[16]

Hiba a bélyegkép létrehozásakor:
A K3,3 teljes páros gráf, két színosztálya különálló, párhuzamos egyenes szakaszokként lerajzolva.

Sablon:Harvtxt az olyan, nem növekvő Sablon:Math számsorozatokat vizsgálta, melyekre igaz, hogy létezik Sablon:Mvar gráf jó élszínezése melyben Sablon:Math él tartozik az első színhez, Sablon:Math él a másodikhoz stb. Megfigyelték, hogy ha egy Sablon:Mvar sorozat „megvalósítható” ebben az értelemben, és lexikografikus sorrend szerint nagyobb mint az ugyanolyan összegű Sablon:Mvar sorozat, akkor Sablon:Mvar is megvalósítható. Hiszen, ha Sablon:Math a lexikografikus sorrendben, akkor Sablon:Mvar átvihető Sablon:Mvar-ba olyan lépések sorozatával, melyek mindegyike eggyel csökkenti az Sablon:Math számok valamelyikét és eggyel növeli valamely későbbi Sablon:Math számot (ahol Sablon:Math). Élszínezés tekintetében egy Sablon:Mvar-t megvalósító színezésnél ezek a lépések megfelelnek az Sablon:Mvar és Sablon:Mvar színek megcserélésével egy Kempe-láncban, ami a két szín között váltakozó maximális út. Továbbá, bármely gráf rendelkezik egyenletes élszínezéssel, tehát olyan optimális élszínezéssel, melyben bármely két színosztályba tartozó élek száma legfeljebb eggyel tér el.

A De Bruijn–Erdős-tétel segítségével a véges gráfok számos, élszínezéssel kapcsolatos tulajdonsága átfordítható végtelen gráfokra. Például a fokszám és az élkromatikus szám közötti összefüggést tárgyaló Shannon- és Vizing-tételek egyszerűen általánosíthatók végtelen gráfokra.[17]

Sablon:Harvtxt vizsgálta adott 3-reguláris gráf olyan lerajzolásának problémáját, ahol a lerajzolás minden éle három különböző lejtésszög valamelyikét veheti fel, és semelyik két él sem helyezkedik el ugyanazon az egyenesen. Ha egy ilyen lerajzolás létezik, akkor az élek lejtésszögei nyilvánvalóan egy 3-élszínezés színeiként is szolgálhatnak. Például a Sablon:Math három ház–három kút-gráf esetén egy szabályos hatszög élei és nagyátlói megfeleltethetők egy 3-élszínezésnek. Richter megmutatta, hogy 3-reguláris egyszerű páros gráfokat és adott Tait-színezést tekintve pontosan akkor létezik ilyen, az adott színezésnek megfelelő lerajzolása, ha a gráf 3-szorosan élösszefüggő. Nem páros gráfokra a feltétel kissé bonyolultabb: adott színezéshez akkor létezik lerajzolás, ha a gráf páros dupla fedése (bipartite double cover) 3-élösszefüggő, és bármelyik egyszínű élpár törlésével még mindig olyan részgráfhoz jutunk, ami nem páros. Ezek a feltételek polinom időben még mind könnyen tesztelhetők; az a probléma azonban, ahol a 4-élszínezett 4-reguláris gráfok négy lejtésszöggel való lerajzolását vizsgáljuk, teljes az existential theory of the realsSablon:Wd nagyobb osztályára nézve, ami legalább olyan nehéz bonyolultsági osztály, mint az NP-teljesség.

Amellett, hogy a gráf maximális fokszámához és maximális elemszámú párosítási számához köthető, az élkromatikus szám szoros kapcsolatban áll a Sablon:Mvar gráf Sablon:Math lineáris arboricitásával is, ami azon lineáris erdők (diszjunkt útgráfok uniója) minimális száma, melyekbe a gráf élei felbonthatók. Egy párosítás a lineáris erdők speciális fajtája, megfordítva pedig, bármely lineáris erdő 2-élszínezhető, ezért minden Sablon:Mvar-re igaz, hogy Sablon:Math. Az Akijama Dzsinről elnevezett Akijama-sejtés állítása szerint la(G)≤⌈Δ+12⌉, amiből következne az előbbinél erősebb állítás, hogy Sablon:Math. A három maximális fokszámú gráfokra Sablon:Math mindig pontosan kettő, tehát ebben az esetben a Sablon:Math korlát megegyezik a Vizing-tétel korlátjával.[18]

Az élszínezés egyéb fajtái

Hiba a bélyegkép létrehozásakor:
A K4,4 teljes páros gráf egy három erdőbe történő particionálása, ami azt mutatja, hogy a gráf arboricitása három.

Egy gráf Thue-száma az ahhoz minimálisan szükséges színek száma, hogy a jó élszínezésen belül bármely páros hosszúságú út első és második fele különböző színsorozatból álljon.

Egy gráf arboricitása az a minimális számú szín, ami szükséges ahhoz, hogy az azonos színosztályba tartozó élek ne alkossanak köröket (ellentétben a megszokott élszínezési problémával, ahol azt várjuk el, hogy ne legyenek azonos színű szomszédos élpárok). Ami megegyezik a minimális számú erdővel, melybe a gráf élei particionálhatók.[19] Az élkromatikus számtól eltérően a gráf arboricitása polinom időben kiszámítható.[20]

A lista-élszínezés az a probléma, melyben a gráf minden éléhez egy színlista van hozzárendelve, és úgy kell jó élszínezést találni, hogy minden élnél csak a lista színeiből lehet válogatni. A Sablon:Mvar gráf lista-élkromatikus száma az a legkisebb Sablon:Mvar szám, melynél bárhogy vannak pontosan az éleken a listaszínek elosztva, ha minden élnek legalább Sablon:Mvar él szerepel a listájában, garantáltan lehetséges a jó élszínezés. A lista-élkromatikus szám ezért legalább akkora, mint az élkromatikus szám. A részleges latin négyzetek kiegészítéséről szóló Dinitz-sejtés gráfelméleti átfogalmazása szerint a Kn,n teljes páros gráf lista-élkromatikus száma éppen élkromatikus számával, n-nel egyenlő. Sablon:Harvtxt általánosabb állítást bizonyít, miszerint bármely páros multigráf lista-élkromatikus száma megegyezik élkromatikus számával. Egy általánosabb lista-élszínezési sejtés szerint ugyanez nem csak páros gráfokra, hanem tetszőleges hurokmentes multigráfra igaz.

A csúcsszínezés gyakoribb változatainak jelentős részét élszínezésre is kiterjesztették. Például a teljes élszínezés a teljes színezés élszínezési változata; ez olyan jó élszínezést jelent, melyben minden színpárnak legalább egy szomszédos élpárnál jelentkeznie kell, és melyben a cél a színek számának maximalizálása.Sablon:Sfnp Az erős élszínezés az erős színezés élszínezési változata, melyben bármely két, különböző végpontokkal rendelkező élnek különböző színűnek kell lennie.[21] Az erős élszínezés alkalmazási területei közé tartoznak a vezeték nélküli hálózatok csatornakiosztási sémái.Sablon:Sfnp

Az aciklikus (körmentes) élszínezés az aciklikus színezés élszínezési változata, melyben bármely két színosztály aciklikus részgráfot (tehát erdőt) alkot.[22] A G gráf a′(G) aciklikus kromatikus száma, ami a G jó aciklikus élszínezéséhez szükséges legkisebb számú szín. Sejtések szerint a′(G)≤Δ+2, ahol Δ G maximális fokszáma.[23] A legjobb igazolt korlát jelenleg a′(G)≤⌈3,74(Δ−1)⌉.Sablon:Sfnp A probléma könnyebbé válik, amikor G girthparamétere magas. Specifikusan, létezik olyan c konstans, melynél ha G girthe legalább cΔlog⁡Δ, akkor a′(G)≤Δ+2.Sablon:Sfnp Egy hasonló eredmény szerint minden ϵ>0-hoz tartozik egy olyan g szám, melyre ha G girthparamétere legalább g, akkor a′(G)≤(1+ϵ)Δ.Sablon:Sfnp

Sablon:Harvtxt tanulmányozta a 3-reguláris gráfok olyan 3-élszínezéseit, melyekben semelyik két olyan bikromatikus (két színnel színezett) kör sem osztozik egynél több élen egymással. Megmutatta, hogy egy ilyen élszínezés létezése ekvivalens olyan, háromdimenziós egész rácsra történő lerajzolással, melyben az élek párhuzamosak a koordinátatengelyekkel és bármely tengelypárhuzamos egyenes legfeljebb két csúcsot tartalmaz. A megszokott 3-élszínezési problémához hasonlóan az ilyen xyz-lerajzolás megkeresése is NP-teljes feladat.

A totális színezés a csúcs- és élszínezést kombinálja, sem érintkező élek, sem valamely él végpontjai nem lehetnek azonos színűek. A Vizing-tétel és a Brooks-tétel kombinációjaként azt a sejtést állították fel, hogy bármely gráfnak van olyan totális színezése, melyben a színek száma legfeljebb a maximális fokszám plusz kettővel egyezik meg – χ″(G) ≤ Δ(G) + 2 – de ezt csak néhány gráfcsaládra sikerült bizonyítani, az általános esetre nem.

Ha egy felületbe ágyazott 3-reguláris gráfra 3-élszínezést alkalmazunk, duális gráfja a felület olyan háromszögelését adja, ami szintén élszínezett (de nem feltétlenül jó élszínezéssel) úgy, hogy a háromszögek pontosan 1-1 éle tartozik 1-1 színhez. Más színezések, illetve háromszögelés-orientációk, a színek a csúcsokon vagy a háromszögelés tartományain való elosztására való helyi megszorításokkal együtt, alkalmasak lehetnek több fajta geometriai objektum kódolására. Például a téglalap-felosztások (egy téglalap felosztása kisebb téglalapokra oly módon, hogy minden csúcsban három téglalap találkozzon) kombinatorikusan leírhatók egy „reguláris címkézéssel”, méghozzá a felosztással duális háromszögelés éleinek olyan 2-színezésével, ahol minden egyes csúcsból kiinduló élek négy folytonos részszekvenciát alkotnak, melyeken belül a színek megegyeznek. Ez a címkézés duálisa magának a téglalapfelosztásnak, melyben a függőleges élek az egyik színt, a vízszintesek a másik színt kapják. A színezett élek csúcsok körül való megjelenésének sorrendjére vonatkozó hasonló lokális megszorítások felhasználhatók síkbarajzolható gráfok, illetve háromdimenziós, tengelypárhuzamos oldalú testek egyenes vonalú rácsba ágyazásának kódolására is. Mindhárom fajta reguláris címkézésre igaz, hogy egy rögzített gráf reguláris címkézéseinek halmaza disztributív hálót alkot, ami felhasználható az ugyanarra a gráfra épülő geometriai struktúrák gyors listázására (például az azonos vázzal rendelkező összes tengelypárhuzamos poliéder listázására) vagy egyéb megszorításoknak megfelelő struktúrák megkeresésére.[24]

Egy determinisztikus véges állapotú gép felfogható olyan irányított gráfként, melyben minden csúcs ki-foka Sablon:Mvar, élei pedig úgy vannak Sablon:Mvar-színezve, hogy két, azonos csúcsból kiinduló élnek mindig különböző színe van. Az útszínezési probléma az azonos ki-fokú irányított gráf élszínezésének problémája, melyben az eredmény automatának van szinkronizáló szava. Sablon:Harvtxt megoldotta az útszínezési problémát azt bebizonyítva, hogy ilyen színezés mindig található, amennyiben a bemeneti gráf erősen összefüggő és aperiodikus.

A Ramsey-tétel a Sablon:Math teljes gráfok olyan Sablon:Mvar-élszínezéseivel foglalkozik, ami valamely adott Sablon:Mvar-re elkerüli az egyszínű Sablon:Math teljes részgráfokat. A tétel szerint létezik olyan Sablon:Math szám, melyre ha Sablon:Math, ilyen színezés nem létezik. Például Sablon:Math, tehát a Sablon:Math 2-élszínezésekor mindig lesz egyszínű háromszög.

Ha egy élszínezett gráf útján nem ismétlődnek a színek, szivárványútnak nevezzük. Egy gráf akkor szivárványszínezett, ha bármely két csúcsa között létezik szivárványút.

Egy G gráf 1…t színekkel való élszínezése (élcímkézése) akkor intervallum-t-színezés, ha mind a t szín felhasználásra kerül és G minden csúcsából kiinduló élek színei különbözőek és egész intervallumot alkotnak.

Alkalmazások

A teljes gráfok élszínezései felhasználhatók körmérkőzések lehető legkevesebb körben történő lebonyolítási rendjének meghatározására; itt a gráfok csúcsai a körmérkőzés résztvevőinek, az élei az egyes mérkőzéseknek, a színek pedig a mérkőzések egyes köreinek feleltethetők meg.[25] Hasonló színezési technikák olyan sportverseny-párosítások esetében is használhatók, ahol nem játszik minden résztvevő mindenkivel; például az NFL-ben az adott évben egymással játszó csapatpárosokat az előző év eredményei alapján határozzák meg, majd a párosítások gráfján egy élszínező algoritmus futtatásával rendelik hozzá a hétvégéket az egyes meccsekhez.[26] Ennél az alkalmazási területnél a Vizing-tétel biztosítja, hogy a csapatok bármilyen párosítását választják (feltéve, hogy semelyik két csapatnak nem kell egymással kétszer játszania egy évadban), mindig lehetséges olyan lebonyolítást találni, hogy legfeljebb eggyel több hétvégére legyen szükség, mint ahány meccs van csapatonként.

Az open shop-ütemezés olyan gyártásütemezési probléma, melynek szereplői a legyártandó tárgyak halmaza, minden tárgyhoz tartozik a rajta (tetszőleges sorrendben) végzendő műveletek halmaza, és minden műveletet adott munkagépen lehet elvégezni, ami alatt más műveletek nem végezhetők ugyanazon a munkagépen. Ha minden művelet ugyanannyi időt vesz igénybe, a probléma felírható egy páros multigráf élszínezéseként, melyben a bipartíció egyik felének csúcsai a legyártandó munkadaraboknak, a másik felének csúcsai a munkagépeknek, az élek az elvégzendő feladatoknak, a színek pedig az egyes időszeleteknek feleltethetők meg. Mivel a páros élszínezés polinom időben elvégezhető, ugyanez igaz az open-shop ütemezés ezen korlátozott esetére.[27]

Sablon:Harvtxt a szenzorhálózatok időosztásos többszörös hozzáférési (TDMA) kommunikációs protokolljainak kapcsolatütemezésének problémáját az élszínezés egy variánsaként tanulmányozták. Ebben a problémában a vezeték nélküli hálózati éleihez úgy kell időréseket választani, hogy a szomszédos hálózati csomópontok interferencia nélkül tudjanak egymással kommunikálni. Erős élszínezést választva (és minden színhez két időrést rendelve, az mindkét iránynak egyet-egyet) megoldható a probléma, de a szükségesnél több időrés felhasználásával. Ehelyett a hálózat irányítatlan éleinek megduplázásával alkotott irányított gráf olyan színezését keresik, melyben minden Sablon:Mvar irányított él színe eltér mind a Sablon:Mvar-ből, mind a Sablon:Mvar szomszédaiból kiinduló élek színeitől. Erre olyan heurisztikát javasolnak, ami egy Sablon:Math-élszínezési elosztott algoritmuson alapul kiegészítve egy utófeldolgozási fázissal, ami újraütemezi az éleket, amik interferálnának egymással.

Az optikai szál-alapú kommunikáció útszínezési problémájában színeket (fényfrekvenciákat) rendelnek az egymással kommunikálni kívánó csomópontpárokhoz, valamint minden párhoz egy-egy útvonalat az optikai szálon keresztül, azzal a megszorítással, hogy az ugyanazt az útvonalat használó két páros nem használhatja ugyanazt a frekvenciát. Az olyan útvonalak, amik ugyanazok a hálózati kapcsolón mennek át, de más optikai szál-szegmensen, lehetnek azonos színűek. Ha a kommunikációs hálózat csillag topológiájú, ahol egy központi switch köti össze önálló szálakkal az egyes hálózati csomópontokat, az útszínezési probléma pontosan megfeleltethető egy gráf vagy multigráf élszínezésének, melyben a kommunikáló csomópontok a gráf csúcsai, az egymással kommunikálni akaró csúcsokat élek köti össze és a felhasználható frekvenciák az élszínezési probléma színeit adják. Általánosabb, fa topológiájú kommunikációs hálózatok esetén az egyes switchek csillaghálózatainak lokális útszínezési megoldásait összefoltozva kapható meg a globális megoldás.[28]

Egyéb problémák

Sablon:Harvtxt 23 élszínezéssel kapcsolatos eldöntetlen problémát sorol fel. Közülük néhány:

  • Sablon:Harvtxt sejtése szerint az élkromatikus szám és a frakcionális élkromatikus szám legfeljebb eggyel térnek el egymástól, ami lehetővé tenné az élkromatikus szám polinom időben való approximációját.
  • Jakobsen és mások több sejtése az élszínezés szempontjából kritikus gráfok szerkezetéről szól, olyan 2. osztályba tartozó gráfokról, melyek bármely részgráfjának vagy alacsonyabb a maximális fokszáma, vagy az 1. osztályba tartozik. Jakobsen eredeti sejtése szerint az összes kritikus gráf páratlan számú csúccsal rendelkezik, de ezt megcáfolták. A témában további nyitott sejtések az eredeti gyengébb változatai, illetve a kritikus gráfok és multigráfok csúcsainak számára állítanak fel korlátokat.
  • Vizing problémája, avagy a 2. osztályba tartozó síkbarajzolható gráfok lehetséges maximális fokszámainak klasszifikációja.
  • A. J. W. Hilton overfull részgráf sejtése, aminek állítása szerint a legalább Sablon:Math fokszámmal rendelkező gráfok vagy az 1. osztályba tartoznak, vagy van olyan részgráfjuk, ami az eredetivel megegyező Sablon:Math fokszámú és páratlan Sablon:Mvar csúcsa van, éleinek száma pedig nagyobb mint Sablon:Math; Herbert Grötzsch és Paul Seymour hasonló sejtése pedig magas fokszámú gráfok helyett síkbarajzolható gráfokkal foglalkozik.
  • Chetwynd és Hilton egy (esetleg Gabriel Andrew Dirac korábbi munkáira visszavezethető) sejtése szerint a páros Sablon:Mvar csúccsal és legalább Sablon:Math fokszámmal rendelkező reguláris gráfok az 1. osztályba tartoznak.
  • Claude Berge és D. R. Fulkerson sejtése szerint a hídmentes 3-reguláris egyszerű gráfok éleinek duplázásával kapott 6-reguláris multigráfok 6-élszínezhetők.
  • Fiorini és Wilson sejtése szerint a K1,3 mancson kívül egyetlen háromszögmentes síkbarajzolható gráf sem egyedileg 3-élszínezhető.
  • Egy 2012-es sejtés szerint ha Sablon:Math Sablon:Math-reguláris síkbarajzolható multigráf, akkor Sablon:Math pontosan akkor Sablon:Math-élszínezhető, ha Sablon:Math páratlanul Sablon:Math-élösszefüggő (ami azt jelenti, hogy bármely páratlan méretű csúcshalmazából kimenő élek számossága nem kisebb Sablon:Math-nél). A Sablon:Math=3 eset egybeesik a négyszínsejtéssel, aminek a sejtés az általánosítása. Maria Chudnovsky, Katherine Edwards és Paul Seymour bizonyították, hogy egy 8-reguláris síkbarajzolható multigráf élkromatikus száma 8.Sablon:Sfnp

Fordítás

Jegyzetek

Sablon:Reflist

Sablon:Refbegin

Sablon:Refend

  1. ↑ Sablon:Harvtxt, problem 16.4, p. 133.
  2. ↑ Sablon:Harvtxt, problem 16.5, p. 133. Az, hogy vagy Sablon:Mvar, vagy Sablon:Math színre van szükség, a Vizing-tétel következménye.
  3. ↑ Sablon:Harvtxt; Sablon:Harvtxt; Sablon:Harvtxt.
  4. ↑ 4,0 4,1 Sablon:Harvtxt, p. 134.
  5. ↑ Sablon:Harvtxt
  6. ↑ Sablon:Harvtxt.
  7. ↑ Sablon:Harvtxt.
  8. ↑ Sablon:Harvtxt.
  9. ↑ Sablon:Harvtxt; Sablon:Harvtxt.
  10. ↑ Sablon:Harvtxt, p. 136.
  11. ↑ Sablon:Harvtxt.
  12. ↑ Sablon:Harvtxt.
  13. ↑ Sablon:Harvtxt; Sablon:Harvtxt; Sablon:Harvtxt.
  14. ↑ Sablon:Harvtxt.
  15. ↑ Sablon:Harvtxt.
  16. ↑ Sablon:Harvtxt.
  17. ↑ Sablon:Harvtxt.
  18. ↑ Sablon:Harvtxt; Sablon:Harvtxt; Sablon:Harvtxt.
  19. ↑ Sablon:Harvtxt.
  20. ↑ Sablon:Harvtxt.
  21. ↑ Sablon:Harvtxt; Sablon:Harvtxt; Sablon:Harvtxt; Sablon:Harvtxt.
  22. ↑ Sablon:Harvtxt; Sablon:Harvtxt.
  23. ↑ Sablon:Harvtxt; Sablon:Harvtxt
  24. ↑ Sablon:Harvtxt.
  25. ↑ Sablon:Harvtxt.
  26. ↑ Sablon:Harvtxt.
  27. ↑ Sablon:Harvtxt.
  28. ↑ Sablon:Harvtxt.
A lap eredeti címe: „https://hu.wiki.beta.math.wmflabs.org/w/index.php?title=Élszínezés&oldid=3809”