graph coloring problem

Angol

Főnév

graph coloring problem (tsz. graph coloring problems)

1. (informatika) gráfszínezési probléma

---

A graph coloring (gráfszínezés) egy klasszikus probléma a gráfelméletben és a kombinatorikában, amely során a gráf csúcsaihoz (vagy éleihez) színeket rendelünk úgy, hogy bizonyos feltételek teljesüljenek. Ez a probléma nemcsak elméleti jelentőségű, hanem számos gyakorlati alkalmazása is van, például ütemezés, térképszínezés, regiszter-allokáció, frekvenciakiosztás, stb.

---

🧠 1. Mi az a graph coloring?

Gráfszínezés alatt általában a csúcspontok színezését értjük, úgy hogy szomszédos csúcsok nem kaphatják ugyanazt a színt.

Formálisan:

Egy irányítatlan gráf ${\textstyle G=(V,E)}$ egy k-színezése olyan hozzárendelés ${\textstyle f:V\rightarrow \{1,2,...,k\}}$, hogy:

$$\forall (u,v)\in E:f(u)\neq f(v)$$

---

🎯 2. Cél

• Olyan színezést találni, ahol:
  • minimális számú színt használunk (→ kromatikus szám)
  • vagy: a gráfot k színnel színezni egyáltalán lehetséges

---

🧮 3. Példa

Gráf:

A — B — C
 \     /
   D

Lehetséges színezés:

• A → piros
• B → zöld
• C → piros
• D → kék

---

📉 4. Kromatikus szám (χ(G))

A kromatikus szám ${\textstyle \chi (G)}$ a legkisebb szám, amellyel a gráf színezhető.

Példák:

• Üres gráf (nincs él): χ = 1
• Teljes gráf ${\textstyle K_{n}}$: χ = n
• Ciklus gráf:
  • páros ciklus: χ = 2
  • páratlan ciklus: χ = 3
• Fa (nem triviális): χ = 2

---

🔁 5. Algoritmusok gráfszínezésre

5.1 Greedy algoritmus

Egyszerű, nem optimális, de gyors:

def greedy_coloring(graph):
    color = {}
    for node in graph:
        neighbor_colors = {color[n] for n in graph[node] if n in color}
        for c in range(len(graph)):
            if c not in neighbor_colors:
                color[node] = c
                break
    return color

• Komplexitás: ${\textstyle O(V+E)}$
• Nem garantálja a minimumot, de mindig érvényes színezést ad

---

5.2 Backtracking

• Kipróbál minden lehetőséget
• Garantáltan megtalálja a minimumot
• Nagyon lassú nagy gráfokra (NP-teljes probléma)

5.3 DSATUR (Degree of Saturation)

• Heurisztika: mindig azt a csúcsot színezzük, amelyiknek a legnagyobb a szomszédjai között a színezési diverzitás

---

⚠️ 6. Nehézségi szint

A gráf minimális színezésének megtalálása NP-teljes probléma. Ez azt jelenti, hogy:

• nincs ismert polinomiális algoritmus
• kis gráfoknál kipróbálhatjuk
• nagy gráfoknál heurisztikákat vagy approximációt alkalmazunk

---

🧩 7. Alkalmazások

Alkalmazás	Leírás
Kurzusütemezés	Két kurzus nem lehet egy időben, ha ugyanaz a hallgató felvette
Regiszter-allokáció	Programváltozók színezése regiszterekhez
Frekvenciakiosztás	Két közeli állomás nem sugározhat ugyanazzal a frekvenciával
Térképszínezés	Szomszédos országok más színt kapnak
Konfliktusmentes beosztás	Tevékenységek hozzárendelése időhöz vagy erőforráshoz

---

🎨 8. Színezés típusai

Típus	Feltétel
Csúcsszínezés	Szomszédos csúcsok nem lehetnek azonos színűek
Élszínezés	Szomszédos élek nem lehetnek azonos színűek
Területszínezés	Régiók színezése, pl. térképen
Listaszínezés	Minden csúcsnak saját színlistája van
Kétszínezés	Lehetséges-e 2 színnel? ↔ Gráf bipartit?

---

🧾 9. Összefoglalás

Fogalom	Leírás
Gráfszínezés	Színek hozzárendelése csúcsokhoz úgy, hogy szomszédosak ne egyezzenek
Kromatikus szám	Minimum szükséges színek száma
Probléma típusa	NP-teljes
Megoldási módok	Greedy, backtracking, DSATUR, approximáció
Alkalmazásai	Ütemezés, erőforrás-kezelés, térképszínezés, nyelvfordítók

További információk

• graph coloring problem - Szótár.net (en-hu)
• graph coloring problem - Sztaki (en-hu)
• graph coloring problem - Merriam–Webster
• graph coloring problem - Cambridge
• graph coloring problem - WordNet
• graph coloring problem - Яндекс (en-ru)
• graph coloring problem - Google (en-hu)
• graph coloring problem - Wikidata
• graph coloring problem - Wikipédia (angol)