SURÁNYI LÁSZLÓ: GRÁFELMÉLET
III. fejezet
Gráf körei és útjai, Hamilton-kör
Ez az oldal még készül.
Addig is mellékeljük belole azokat a definíciókat és tételeket, amelyekre az elozo fejezetkben szükség van:
DEFINÍCIÓ:
Az olyan kört, amely a gráf minden pontját tartalmazza, Hamilton-körnek nevezzük.
Dirac tétele:
Ha egy n pontú gráfban minden pont foka legalább n/2, akkor a gráfnak van Hamilton-köre.
TÉTEL:
Euler tétele csak páros fokú pontot tartalamzó gráfban: egy ilyen gráfban van olyan séta, amely minden élen pontosan egyszer halad át.