ötszín-tétel

• IPA:

ötszín-tétel (matematika, gráfelmélet) 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.

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

- 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ő.

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.

- Az Euler-tétel szerint egy síkbarajzolható gráfban: ${\displaystyle v-e+f=2,}$ ahol ${\displaystyle v}$ a csúcsok, ${\displaystyle e}$ az élek, és ${\displaystyle 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: ${\displaystyle {\text{átlagos fokszám}}={\frac {2e}{v}}\leq 6.}$ - Így mindig van legalább egy csúcs, amelynek fokszáma legfeljebb 5.

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

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

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

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

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

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

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

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

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

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 = 
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= for node in G.nodes()])
plt.show()

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

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.

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.

• ötszín-tétel - Értelmező szótár (MEK)
• ötszín-tétel - Etimológiai szótár (UMIL)
• ötszín-tétel - Szótár.net (hu-hu)
• ötszín-tétel - DeepL (hu-de)
• ötszín-tétel - Яндекс (hu-ru)
• ötszín-tétel - Google (hu-en)
• ötszín-tétel - Helyesírási szótár (MTA)
• ötszín-tétel - Wikidata
• ötszín-tétel - Wikipédia (magyar)