Ötszín-tétel

Sablon:Hunfn Sablon:Label Az ötszín-tétel a síkbarajzolható gráfok csúcsszínezésére vonatkozó állítás, amely a négyszín-tétel gyengébb változata. A tétel kimondja:

 Bármely síkbarajzolható gráf csúcsai kiszínezhetők legfeljebb öt színnel úgy, hogy bármely két szomszédos csúcs különböző színt kapjon.

Ez azt jelenti, hogy minden síkban rajzolt térkép színezésére elegendő öt szín.

Fogalmak

Síkbarajzolható gráf

- Egy gráf síkbarajzolható, ha síkban rajzolható úgy, hogy élei nem metszik egymást.

Csúcsszínezés

- Egy gráf csúcsszínezése olyan hozzárendelés, amelyben minden csúcs kap egy színt úgy, hogy két szomszédos csúcs színe különböző.

Tétel Bizonyítása

Az ötszín-tétel bizonyítása egyszerűbb, mint a négyszín-tételé, és nem igényel számítógépes segítséget. A bizonyítás a síkbarajzolható gráfok strukturális tulajdonságaira épül.

1. Síkbarajzolható gráfok tulajdonságai

- Az Euler-tétel szerint egy síkbarajzolható gráfban: $v-e+f=2,$ ahol $v$ a csúcsok, $e$ az élek, és $f$ a régiók száma. - Ebből következik, hogy a síkbarajzolható gráfokban a csúcsok átlagos fokszáma legfeljebb 6: $\text{átlagos fokszám}=\frac{2e}{v}\le 6.$ - Így mindig van legalább egy csúcs, amelynek fokszáma legfeljebb 5.

2. Induktív bizonyítás

A bizonyítást indukcióval végezzük a gráf csúcsainak számára ($v$).

Báziseset:

- Ha $v\le 5$, akkor a gráf legfeljebb 5 csúcsot tartalmaz, és nyilvánvalóan kiszínezhető 5 színnel.

Indukciós lépés:

- Tegyük fel, hogy minden $n$-nél kevesebb csúcsú síkbarajzolható gráf kiszínezhető legfeljebb 5 színnel. - Tekintsünk egy $G$ gráfot $n$ csúccsal. - Válasszunk ki egy $v$ csúcsot, amelynek fokszáma legfeljebb 5 (létezik ilyen csúcs a síkbarajzolhatóság miatt). - Távolítsuk el $v$-t a gráfból, és jelöljük a maradék gráfot $G^{\prime }$-vel.

 - $G^{\prime }$ kiszínezhető legfeljebb 5 színnel az indukciós feltétel alapján.

Színezés visszaállítása:

- Adjunk $v$-nek egy olyan színt, amely eltér a szomszédos csúcsok színétől.

 - Mivel $v$-nek legfeljebb 5 szomszédja van, mindig marad egy elérhető szín a színezéshez.

Ezzel a gráf $G$ is kiszínezhető legfeljebb 5 színnel.

Példa

Gráf

$V=\{A,B,C,D,E\},E=\{(A,B),(A,C),(A,D),(A,E),(B,C),(C,D),(D,E)\}.$

Színezés

1. Adjunk $A$-nak ${\text{Szín}}_1$-et.
2. Adjunk $B$-nek ${\text{Szín}}_2$-t (szomszédos $A$-val).
3. Adjunk $C$-nek ${\text{Szín}}_3$-at (szomszédos $A$ és $B$-vel).
4. Adjunk $D$-nek ${\text{Szín}}_4$-et (szomszédos $A$ és $C$-vel).
5. Adjunk $E$-nek ${\text{Szín}}_5$-öt (szomszédos $A$ és $D$-vel).

Python Implementáció

import networkx as nx
import matplotlib.pyplot as plt

def five_color_theorem(graph):
    """
    Az ötszín-tétel megvalósítása: kiszínezi a síkbarajzolható gráfot legfeljebb 5 színnel.
    """
    coloring = nx.coloring.greedy_color(graph, strategy="largest_first")
    return coloring

# Példa gráf
G = nx.Graph()
edges = [("A", "B"), ("A", "C"), ("A", "D"), ("A", "E"), ("B", "C"), ("C", "D"), ("D", "E")]
G.add_edges_from(edges)

# Színezés
coloring = five_color_theorem(G)
print("Csúcsszínezés:", coloring)

# Gráf ábrázolása
pos = nx.planar_layout(G)
nx.draw(G, pos, with_labels=True, node_color=[coloring[node] for node in G.nodes()])
plt.show()

Kimenet

Csúcsszínezés: {'A': 0, 'B': 1, 'C': 2, 'D': 3, 'E': 4}

Alkalmazások

1. Térképszínezés: Térképek színezése 5 színnel, amikor nem szükséges a minimális színszám.
2. Hálózattervezés: Konfliktusmentes frekvenciahasználat tervezése.
3. Ütemezési problémák: Feladatok vagy események ütemezése, hogy ne legyenek átfedések.

Összegzés

Az **ötszín-tétel** a síkbarajzolható gráfok színezésére vonatkozó fontos eredmény, amely egyszerű bizonyítással és széles körű alkalmazási lehetőségekkel bír. Bár a négyszín-tétel erősebb állítás, az ötszín-tétel bizonyítása kevésbé összetett, és nem igényel számítógépes segítséget. Az ötszín-tétel gyakorlati jelentőséggel bír a gráfelmélet és a különféle optimalizálási problémák területén.

• Sablon:En: Sablon:T
• Sablon:De: Sablon:T