Wikiszótár

gráfok színezése

Magyar

Kiejtés

  • IPA: [ ˈɡraːfoksiːnɛzeːʃɛ]

Főnév

gráfok színezése

  1. (matematika) A gráfszínezés problémája azt vizsgálja, hogy adott egy gráf csúcsait hogyan lehet kis számú színnel színezni úgy, hogy semmilyen szomszédos csúcs ne kapjon azonos színt.

Típusok

  1. Csúcsszínezés (Vertex Coloring):
    • A gráf csúcsainak színezése minimális számú színnel.
  2. Élszínezés (Edge Coloring):
    • A gráf éleinek színezése úgy, hogy semmilyen szomszédos él ne legyen azonos színű.
  3. Síkgráf színezése:
    • Síkgráf csúcsainak színezése legfeljebb négy színnel (négy szín tétele).

Alapvető Cél

  • A legkisebb számú szín (kromatikus szám, ((G))) megtalálása a gráf színezéséhez.


Gráfszínezés Alkalmazások

  1. Ütemezési problémák:
    • Például órarendek készítése, ahol két szomszédos csúcs összeférhetetlenséget jelent.
  2. Frekvencia-hozzárendelés:
    • Mobilhálózatok frekvenciáinak optimalizálása.
  3. Térképszínezés:
    • Területek színezése térképen.


Python Megoldás

A gráfszínezés problémáját Pythonban a “Greedy Algorithm” segítségével egyszerűen megoldhatjuk. Ez egy heurisztikus algoritmus, amely csúcsokat egyenként színez, és mindig a legkisebb elérhető színt választja.

Python Implementáció:

def greedy_coloring(graph):
    """
    Gráfszínezés greedy algoritmussal.
    
    Args:
        graph: Szomszédsági lista, ahol graph[i] a i csúcs szomszédos csúcsainak listája.
    
    Returns:
        colors: Lista, ahol colors[i] az i csúcs színe.
    """
    n = len(graph)  # Csúcsok száma
    colors = [-1] * n  # Kezdetben minden csúcs színezés nélkül
    available_colors = [True] * n  # Elérhető színek jelölése

    # Minden csúcs színezése
    for node in range(n):
        # Szomszédos csúcsok színei
        for neighbor in graph[node]:
            if colors[neighbor] != -1:
                available_colors[colors[neighbor]] = False

        # Legkisebb elérhető szín kiválasztása
        for color in range(n):
            if available_colors[color]:
                colors[node] = color
                break

        # Színek visszaállítása a következő iterációra
        available_colors = [True] * n

    return colors

# Példa gráf (szomszédsági lista)
graph = [
    [1, 2, 3],  # 0. csúcs szomszédai
    [0, 2],     # 1. csúcs szomszédai
    [0, 1, 3],  # 2. csúcs szomszédai
    [0, 2]      # 3. csúcs szomszédai
]

# Gráfszínezés futtatása
colors = greedy_coloring(graph)

print("Csúcsok színei:", colors)

Példa Kimenet

Adott gráf: - 0. csúcs szomszédai: 1, 2, 3 - 1. csúcs szomszédai: 0, 2 - 2. csúcs szomszédai: 0, 1, 3 - 3. csúcs szomszédai: 0, 2

Kimenet: 

Csúcsok színei: [0, 1, 2, 1]

Magyarázat

  1. Input:
    • Egy gráf szomszédsági listája.
  2. Algoritmus:
    • Minden csúcsot egyenként színezünk.
    • A szomszédos csúcsok színeit vizsgálva kiválasztjuk a legkisebb elérhető színt.
  3. Output:
    • Minden csúcs színét tartalmazó lista, ahol a színek számok ((0, 1, 2, )).


Optimalitás és Hatékonyság

Greedy Algoritmus:

  • Nem garantálja a minimális kromatikus számot (((G))), de gyors és egyszerű.
  • Időbonyolultság: (O(V^2)), ahol (V) a csúcsok száma.

Fejlettebb Megoldások:

  1. Backtracking Algoritmus:
    • Garantáltan megtalálja a minimális színezést, de időigényes ((O(k^V))).
  2. Heurisztikus Algoritmusok:
    • Például Welsh-Powell algoritmus.


Összegzés

A gráfszínezés problémája számos gyakorlati alkalmazással rendelkezik. A fenti Python implementáció hatékony módja egy egyszerű gráfszínezési probléma megoldásának. Nagyobb és bonyolultabb gráfok esetén érdemes fejlettebb algoritmusokat vagy könyvtárakat használni (pl. NetworkX).

Fordítások

Tartalom

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=gráfok_színezése&oldid=3479792”