négyszín-tétel

Magyar

Kiejtés

• IPA: [ ˈneːcsiːnteːtɛl]

Főnév

négyszín-tétel

1. (matematika, gráfelmélet)

   

   Példa egy négy színnel színezett térképre

A Kétfarkú Kutya Párt négyszín-tételt illusztráló dekorációja az Örs vezér terén

A matematikában a négyszín-tétel azt állítja, hogy egy tetszőleges régiókra osztott síkot, akár egy politikai térképet egy ország megyéiről, ki lehet úgy színezni legfeljebb négy szín felhasználásával, hogy ne legyen két azonos színű szomszédos régió. Két régiót akkor nevezünk szomszédosnak, ha nem csak izolált pontokban, hanem egy görbe mentén érintkeznek. A régióknak összefüggőeknek kell lenniük: tehát nem állhatnak különálló részekből, mint nem kevés ország, például Angola, Azerbajdzsán vagy az Amerikai Egyesült Államok.

---

Négyszín-tétel

Definíció

A **négyszín-tétel** a gráfelmélet egy híres eredménye, amely a síkbarajzolható gráfok csúcsszínezésére vonatkozik. A tétel kimondja:

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

Ez a tétel ekvivalens azzal, hogy minden síkban adott térképen legfeljebb négy szín elegendő ahhoz, hogy bármely két szomszédos ország különböző színt kapjon.

Fogalmak

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

Síkbarajzolható gráf

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

Gráfelméleti megfogalmazás

- A négyszín-tétel állítása szerint minden síkbarajzolható gráf kromatikus száma legfeljebb 4, azaz a gráf minden csúcsa kiszínezhető legfeljebb négy színnel.

Történeti háttér

1. Első sejtés (1852): Francis Guthrie vetette fel először a tételt térképszínezési problémaként.
2. Első "bizonyítás" (1879): Alfred Kempe bizonyítást publikált, de később (1890-ben) Percy Heawood bebizonyította, hogy ez a bizonyítás hibás.
3. Számítógépes bizonyítás (1976): Kenneth Appel és Wolfgang Haken voltak az elsők, akik számítógépes segítséggel teljes bizonyítást adtak a tételre. Ez az első számítógéppel igazolt matematikai tétel.

Bizonyítás vázlata

A tétel bizonyítása három kulcsfontosságú lépésből áll:

1. Síkbarajzolható gráfok redukálása

- Az összes síkbarajzolható gráf redukálható egy "minimális redukált gráfokra", amelyeken a tétel ellenőrizhető. - A redukált gráf definíció szerint 4-színezhető, ha minden megfelelő részgráfja is 4-színezhető.

2. Diszjunktív konfigurációk keresése

- Az összes lehetséges minimális konfigurációt (gráfrészleteket) azonosítani kell, amelyek nem 4-színezhetők. - A síkbarajzolható gráfok rendelkeznek bizonyos topológiai tulajdonságokkal, amelyek lehetővé teszik az ilyen konfigurációk véges listára szűkítését.

3. Számítógépes ellenőrzés

- Appel és Haken számítógépes programot használtak a véges konfigurációk listájának ellenőrzésére. - Bebizonyították, hogy minden lehetséges minimális konfiguráció 4 színnel színezhető.

Bizonyítás alapelvei

Gráfelméleti tulajdonságok

1. Euler-tétel alkalmazása:

  Egy síkbarajzolható gráfra:
  $v-e+f=2,$
  ahol $v$: csúcsok száma, $e$: élek száma, $f$: régiók száma.
  Ez segít meghatározni, hogy a gráf csúcsainak és éleinek száma hogyan korlátozza a konfigurációkat.

1. Kritikus gráfok keresése: Egy gráf akkor 4-színezhető, ha minden részgráfja 4-színezhető.

Redukció

- Egy csúcs fokszáma (azaz hány él csatlakozik hozzá) legfeljebb 6 lehet. - Egy csúcs eltávolításával és a maradék gráf 4-színezhetőségének ellenőrzésével bizonyítható a tétel.

Számítógépes ellenőrzés

- Appel és Haken 1476 konfigurációt azonosítottak, és ezek mindegyikét ellenőrizték számítógéppel.

Kritika és elfogadás

- A számítógépes bizonyítás miatt a tétel eleinte vitákat váltott ki, mert nem lehetett közvetlenül ellenőrizni a számításokat. - Azóta több optimalizált számítógépes bizonyítást is adtak, megerősítve a tételt.

Példa: Egy egyszerű gráf színezése

Gráf

\[ V = \{A, B, C, D\}, \quad E = \{(A, B), (B, C), (C, D), (D, A), (A, C)\}. \]

Színezés

1. Adjunk színt $A$-nak: ${\text{Szín}}_{1}$.
2. Adjunk $B$-nek ${\text{Szín}}_{2}$-t (szomszédos $A$-val).
3. Adjunk $C$-nek ${\text{Szín}}_{1}$-t (szomszédos $B$-vel).
4. Adjunk $D$-nek ${\text{Szín}}_{2}$-t (szomszédos $C$-vel).

Ez a gráf 2 színnel színezhető, mert páros gráf.

Python Implementáció

import networkx as nx
import matplotlib.pyplot as plt

def color_graph(graph):
    """
    Színezési algoritmus a síkbarajzolható gráfhoz.
    """
    coloring = nx.coloring.greedy_color(graph, strategy="largest_first")
    return coloring

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

# Színezés
coloring = color_graph(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': 0, 'D': 1}

Alkalmazások

1. Térképszínezés: Országok színezése térképen, hogy szomszédos országok különböző színt kapjanak.
2. Hálózattervezés: Csúcskonfliktusok elkerülése (pl. frekvenciák kiosztása mobilhálózatokban).
3. Ütemezés: Feladatok ütemezése erőforrások (pl. tantermek) szerint.

Összegzés

A **négyszín-tétel** a gráfelmélet egyik legismertebb tétele, amely először mutatta meg, hogy a számítógépes bizonyítások használata megváltoztathatja a matematikai bizonyítások módszertanát. A tétel gyakorlati alkalmazásai számos területen jelentősek, beleértve a térképszínezést, a hálózatok optimalizálását és az ütemezési problémákat. Az Appel-Haken-féle bizonyítás óta a tétel széles körben elfogadott és megerősített eredmény.

• angol: four color theorem (en)
• német: Vierfarbensatz (de)

További információk

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