Színező grafikon - e
Színező grafikon
A grafikon és a csúcsok mindkét szélét színezheti. Először megérintjük a csúcspontok színezésének problémáját. feltételezzük, hogy a grafikon nem orientált, és nem multigraph.
A feladat. Színezze a gráf csúcspontjait úgy, hogy a két szomszédos csúcs különböző színekben legyen festve, és a felhasznált színek száma legyen a legkisebb. Ezt a számot a grafikon kromatikus (szín) számának nevezzük, amit a = a (G) jelöléssel jelölünk (ha G egy adott grafikon). Ha a szám k i a. akkor a grafikon k-színezhető.
A Grundy függvény függvény egy olyan gráf csúcsán, amely a csúcsokat egy készletre helyezi, és ha az xi csúcs a k számmal van színezve. akkor a Grandi függvény h (xi) = k.
Nyilvánvaló, hogy egy adott gráf esetében a kromatikus szám egyedi, de sok Grandi funkció létezik. Természetesen a Grandi legalább egy funkciójának megtalálása azt jelenti, hogy megtaláljuk az egyik lehetséges "legjobb" színezéket (sok ilyen színezőanyag létezik).
Megjegyezzük, hogy ha az adott gráf teljes, vagyis bármelyik két csúcs szomszédos, akkor egy ilyen gráf kromatikus száma n-val egyenlő, ahol n az csúcsok száma.
A jövőben a következő definícióra van szükségünk.
A csúcsok halmaza nevezzük maximális független halmaz (MNS), ha bármely két pont ez a készlet nem összefüggőek, és nem lehet a készletben egy másik csúcs ezt a feltételt is megmarad. Megjegyezzük, hogy a MNF jelenléte a gráf elég egyszerű: egy tetszőleges vertex, akkor találunk top, nem szomszédos, és akkor találja meg a legjobb, nem szomszédos a kiválasztott csomópontok, stb Természetesen az MHC ebben az oszlopban lehet sok, és ezek .. különböző számú csúcsot tartalmazhat.
Most az algoritmus leírására térünk vissza, hogy megtaláljuk a grafikon csúcsai legjobb színezését. Tegyük fel, hogy van egy G. gráf. Itt találunk néhány MHC-t, amit S1-vel jelöltünk. és az összes csomópont, amelyek az MHC, festett színes № 1. Továbbá, eltávolítjuk a grafikonon az összes csomópont, amelyek az MHC (az uszonyok), és újra megtalálni az új grafikon MHC jelölt S2. Ezek az új csúcsok kiemelve szín № 2, majd távolítsa el a csúcsot a grafikonon, valamint megfelelő bordák és újra megtalálni az MHC, amely kiemelt szín № 3, és így tovább. E. is bizonyítható, hogy a lehető legjobban meg színezés bármilyen eljárás ennek az eljárásnak, és megtalálja a Grundy függvényt és az adott grafikon kromatikus számát.
Egy példa. A grafikon (9. ábra) 3 maximálisan független vertikumrendszert tartalmaz :, és. Nyilvánvaló, hogy a grafikon kromatikus számának megtalálásához szükséges bármely eljáráshoz kapjuk a 3. számot.
Tétel: Ha a gráf csúcsainak maximális mértéke r. akkor a gráf kromatikus száma nem haladja meg az r + 1 értéket. Ebben az esetben a gráf kromatikus száma csak két esetben egyenlő r + 1 értékkel: először, ha a grafikon teljes, másodszor, ha r = 2, és a gráf tartalmaz egy kontúrot páratlan hosszúságú (ilyen grafikon látható a 10. ábrán, a csúcsok maximális mértéke 2, a kromatikus szám pedig 3). Minden más esetben a grafikon kromatikus száma nem haladja meg a csúcsok maximális fokát.
Megjegyzés. Az e tétel által megadott kromatikus szám becslése meglehetősen durva. Ez különösen a fa példáján (14. fejezet) látható, amelynél a csúcsok tetszőlegesen nagyok lehetnek, és a kromatikus szám 2.
A vizsgált kérdések a négy szín ismert problémájához kapcsolódnak. Ennek megfogalmazásához még több definícióra van szükségünk.
A grafikon síknak mondható, ha egy síkra húzódik, és bármelyik két széle csak a csúcson metszhet.
A grafikonok izomorfak. ha ilyen gráfok ilyen csúcsai vannak, hogy ugyanaz a szomszédsági mátrixuk van (valójában az izomorf grafikonok ugyanazok a grafikonok, amelyek csak egy másik képen különböznek).
A gráfot síknak nevezik. ha izomorf a síkbeli gráfra. Így a sík grafikon síkban ábrázolható a síkban. Az 1. ábrán. A 11. ábra két izomorf (azonos) grafikonot mutat be, amelyek közül az első sík, a második sík.
Megjegyezzük a négy színes probléma legismertebb értelmezését. Legyen földrajzi térkép. Lehetséges-e, hogy csak 4 színt használva ábrázolják ezt a térképet, hogy a szomszédos országok (közös határral) különböző színekben legyenek festve? Nyilvánvaló, hogy a megfelelő gráfban a felsőek az országok, és a szomszédos országok szomszédos csúcsok. Nyilvánvaló, hogy a kapott grafikon sík, és 1976 után a kérdésre adott válasz pozitív.
Megjegyezzük, hogy a grafikonok elméletében a grafikonok éleinek színezése gyakran felmerül. Mi az a minimális számú színben (ez a szám néha nevezik élkromatikus) meg kell festeni a széleit a gráf úgy, hogy bármely két szomszédos élei (azaz. E. 2. élek egy közös vertex) lenne festve más színnel? Mert élkromatikus számú grafikon tart sokkal pontosabb értékelését, mint egyszerűen a kromatikus szám, azaz a következő igaz, hogy bizonyos mértékig meglepő, tétel.
Vizing tétele. Ha a gráfban a csúcsok maximális foka r. akkor az élkromatikus szám megegyezik vagy r-val. vagy r + 1.
Ne feledje, hogy még mindig nincsenek "jó" kritériumok a grafikonokhoz, amikor pontosan az élkromatikus szám egyenlő r-vel. és amikor r + 1.
Nyilvánvaló, hogy a legegyszerűbb algoritmus megtalálása élkromatikus számát (és a megfelelő élek a színezés) a következő: a grafikonon épület egy úgynevezett kettős grafikon: élek a gráf felel meg csúcsai egy új (kettős) a grafikon, és ha a két borda közös vertex, akkor Ezek szomszédosak, és a kettős gráfban egy perem csatlakozik. Miután ez a szín a legjobb tetején a kettős gráf, és megy a „régi”, gróf jutunk (egy lehetséges) a legjobb borda színezékeket grafikonok.
Összefoglalásként megjegyezzük, hogy az élszínezéseket gyakran használják különböző eszközök kialakításában, ahol az egyik csúcshoz csatlakozó vezetékeknek (a kényelem érdekében) különböző színekkel kell rendelkezniük.