„Négyszín-tétel” változatai közötti eltérés
| [ellenőrzött változat] | [ellenőrzött változat] |
Tartalom törölve Tartalom hozzáadva
a →Lásd még: fejezetcím mód. + 3 link korr. |
a hiv. korr, + egyéb apróság AWB |
||
1. sor:
[[Kép:Four Colour Map Example.svg|jobbra|bélyegkép|Példa egy négy színnel színezett térképre]]
A [[matematika|matematikában]] a '''négyszín-tétel''' azt állítja, hogy egy tetszőleges régiókra osztott [[sík (geometria)|sík]]ot, akár egy politikai [[térkép]]et 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édos''nak, 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]].
Az egészen nyilvánvaló, hogy három szín kevésnek bizonyulhat. Ez már egy olyan térképnél is megmutatkozik, ahol egy régiót három másik régió vesz körül (ámbár ha páros számú régió veszi körül, három szín is elég). Nem túl nehéz megmutatni, hogy [[ötszín-tétel|öt szín elégséges]] egy térkép kiszínezéséhez.
A négyszín-sejtés volt az első nevezetes matematikai [[sejtés]], amit [[számítógép]] használatával sikerült bebizonyítani. Ez sok vitát váltott ki, hiszen lehetséges, hogy a programban, a számítógép [[hardver]]ében, a fordítóprogramban stb. szisztematikus hiba van, amiről nem tudunk. Az is igaz azonban, hogy egy matematikus bizonyításába is csúszhat hiba, főleg, ha ilyen sok esetet kell megvizsgálni, mint ami a sejtés esetén is szükséges.
Egy másik tényező a matematikai elegancia hiánya volt. Ahogy akkoriban mondták: „egy jó matematikai bizonyítás olyan, mint egy költemény; ez inkább olyan, mint a telefonkönyv!”
37. sor:
* egy ''csökkenthető elrendezés'' a régiók olyan konfigurációja, amiket egy minimális ellenpélda nem tartalmazhat. Ha egy térkép tartalmaz egy csökkenthető elrendezést, és a térkép többi része négy színnel kiszínezhető, akkor az egész térkép színezhető négy színnel, és a térkép nem minimális.
A csökkenthető elrendezések tulajdonságain alapuló matematikai szabályok és eljárások segítségével (gyűrűk, Kempe-láncok, method of discharging stb.) Appelnek és Hakennek sikerült találnia a csökkenthető elrendezéseknek egy elkerülhetetlen halmazát, így bebizonyítva, hogy a négyszín-sejtés ellenpéldája nem létezhet. Bizonyításuk redukálta a végtelen számú lehetséges térképet összesen 1936 elrendezésre (később ezt sikerült 1476-ra leszorítani), amit aztán egyenként számítógéppel ellenőrizni lehetett. Mindazonáltal, a bizonyítás elkerülhetetlenséggel foglalkozó része több mint 500 oldalnyi, kézzel írott ellen-ellenpéldát tartalmazott, aminek nagy részét Haken tinédzser fia, Lippold ellenőrzött. A bizonyítás így 50 szöveget és diagramokat tartalmazó, 85 további 2500 diagramot tartalmazó oldalból, és 400 mikrokártyából állt, ami a bizonyítás főszövegében levő 24 lemma ezernyi eseteinek egyedi igazolását tartalmazta. A bizonyítás része még egy számítógépes program, ami ezerkétszáz órán keresztül futott.
Az Appel-Haken-féle bizonyításban publikálásuk óta olyan nagy mennyiségű hibát találtak (Appel és Haken szisztematikus javításukban ezeket aprólékosan kategorizálták is), hogy számos vezető kutató már nem Appelt és Hakent tekinti a négyszíntétel első bizonyítójának.
60. sor:
A tételt legegyszerűbben a [[gráfelmélet]] keretein belül lehet megfogalmazni. Ilyenformán azt állítjuk, hogy minden [[síkba rajzolható gráf]] [[csúcspont]]jai [[gráfok színezése|kiszínezhetők]] legfeljebb négy színnel úgy, hogy semelyik két szomszédos csúcspont ne legyen azonos színű. Vagy rövidebben: „minden síkba rajzolható gráf négy színnel színezhető”. Ebben a megfogalmazásban a térkép minden régiója a gráf egy csúcspontjának felel meg, és két csúcspont [[akkor és csak akkor]] van [[él (gráfelmélet)|éllel]] összekötve, ha a térkép két régiójának közös határrésze van (nem csak egy pontban).
[[Kép:Four Colour Planar Graph.svg|középre
== Ekvivalens állítások==
89. sor:
[[Kép:Torus-with-seven-colours.png|bélyegkép|jobbra|300px|A sima és a dupla nyilakat csatlakoztatva olyan [[tórusz]]t kapunk, ami hét egymást kölcsönösen érintő régióból áll; ezért hét szín szükséges]]
A színezési probléma a [[sík (geometria)|sík]]on kívül más felületeken is felvethető. A [[gömb]] felszínén a probléma ekvivalens a síkbéli esettel.
Zárt (irányított vagy nem irányított) pozitív nemszámú (genusú) felületeken a maximálisan szükséges színek ''p'' száma a felület [[Euler-karakterisztika|Euler-karakterisztikájától]] függ, a következő képlet szerint:
104. sor:
A valóságban nem minden ország összefüggő, előfordulnak [[exklávé]]k, mint például [[Alaszka]] az [[Amerikai Egyesült Államok|USA]] részeként, [[Nahicseván]]<!--magyar neve?--> [[Azerbajdzsán]] részeként, és [[Kalinyingrád]] [[Oroszország]] részeként. Ha a választott színezés megkívánja, hogy az ország külterületét ugyanolyan színnel kell rajzolni, mint az országot, négynél több színre lehet szükség. Koncepcionálisan egy ilyen megszorítás azt jelenti, hogy a térkép már nem síkbeli, és így a négyszín-tétel már nem vonatkozik rá. Vegyük például a következő egyszerűsített térképet:
[[Kép:Four color inadequacy example.png|none
Ezen a térképen a két „A”-val jelölt régió ugyanahhoz az országhoz tartozik, ezért ugyanolyan színnel kell megrajzolni. Így a térkép öt színt igényel, mert a két „A”-régió négy másik régióval érintkezik, amelyek mind egymással is érintkeznek. Ha „A” három részből állna, hat vagy még több színre lenne szükség; könnyen konstruálható térkép, ami tetszőlegesen magas számú színt kíván meg.
127. sor:
{{Portál|Matematika}}
{{DEFAULTSORT:Negyszintetel}}
[[Kategória:Kombinatorikus geometria]]
| |||