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

6 bájt hozzáadva ,  15 évvel ezelőtt
a
→‎Szinezések: typo: szinezés -> színezés mindenütt
[nem ellenőrzött változat][nem ellenőrzött változat]
a (→‎Alapfogalmak: séta def bővítés)
a (→‎Szinezések: typo: szinezés -> színezés mindenütt)
<!-- <math>(\mbox{beton kész})</math> <math>(\mbox{beton kész})\longrightarrow^{8}(\mbox{falazást kezd})</math> -->
 
=== [[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]]
Egyszerű gráfban:
:''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>
 
=== További problémák ===
321

szerkesztés