„Gráf” változatai közötti eltérés

=== [[SzinezésSzínezés (gráfelmélet)|SzinezésSzínezés]]ek ===

[[Kép:3-coloringEx.svg|thumb|3 színnel szinezettszínezett egyszerű gráf]]

:''Legkevesebb hány szín kell a csúcsok kiszinezéséshezkiszínezéséshez, ha a szomszédosak nem lehetnek egyszínűek?''

<small>Ezzel a feladattal szembesülünk például egy politikai térkép színezésénél. A csúcsok az országok, az élek a közös határral rendelkező országok között futnak. A természetes térképekből ilyen módon kapott gráfoknak megvan az a szép tulajdonságuk, hogy lerajzolhatóak élkeresztezések nélkül a [[sík]]ba. (lásd: ''→[[síkgráf]]'') Egy diák figyelt fel rá, hogy akármilyen bonyolult térképet is választ, négy szín mindig elegendő volt a megfelelő szinezéshezszínezéshez. Nagyon sokáig nyitott probléma volt, hogy ez mindig lehetséges-e, de végül megszületett a [[négyszín-tétel]]. A csúcsok minél kevesebb színnel szinezéseszínezése általános gráfokban továbbra is nehéz feladat.</small>