Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoalap|SzamElmTetelA12}} SzamelmSzig > DaniVeloxKidolgozas > *Hamilton-körök és -utak. Szükséges feltétel Hamilton-kör/út lét…”

2012-10-21T20:15:01Z

Új oldal, tartalma: „{{GlobalTemplate|Infoalap|SzamElmTetelA12}} SzamelmSzig > DaniVeloxKidolgozas > *Hamilton-körök és -utak. Szükséges feltétel Hamilton-kör/út lét…”

Új lap

{{GlobalTemplate|Infoalap|SzamElmTetelA12}}

[[SzamelmSzig]] > [[DaniVeloxKidolgozas]] >
*Hamilton-körök és -utak. Szükséges feltétel Hamilton-kör/út létezésére. Elégséges feltételek: Ore * és Dirac tétele. Hamilton-kör keresés bonyolultsága '''. Euler-körök és -utak, ezek létezésének szükséges és elégséges feltétele.'''

_Hamilton-kör_: G-ben egy kör, amely a G gráf minden pontját pontosan egyszer tartalmazza.

_Hamilton-út_: G-ben egy út, amely G minden pontját pontosan egyszer tartalmazza.

*Tétel*: (_szükséges tétel a Hamilton-kör létezésére_): Ha G-ben van Hamilton-kör, akkor tetszőleges k pont elhagyásával legfeljebb k részre esik szét a gráf (nem elégséges, pl.: Petersen gráf).
Bizonyítás: Indirekt tegyük fel, hogy van a gráfban Hamilton-kör, legyen ez (v1,v2,…,vn) és legyen vi1,vi2,…,vik az a k pont, melyet elhagyva a gráf több, mint k komponensre esik. Az elhagyott pontok közötti „ívek” összefüggő komponenseket alkotnak. Pl. a (vi1+1,vi1+2,…,vi2-1) ív is összefüggő, hiszen két szomszédos pontja között az eredeti Hamilton-kör egy éle fut. Mivel éppen k ilyen ív van, nem lehet több komponens k-nál. (Kevesebb lehet, hiszen különböző ívek között futhatnak élek.)

*Tétel*: (_szükséges tétel a Hamilton-út létezésére_): Ha G-ben van Hamilton-út, akkor tetszőleges k pont elhagyásával legfeljebb k+1 részre esik szét a gráf.
Bizonyítás: Hasonlóan, mint Hamilton-körre.

*Tétel*: (_elégséges tétel Hamilton-kör létezésére_):
_Ore_: ha minden a, b pont párra, amelyek nincsenek összekötve, d(a)+d(b)≥n, akkor van Hamilton-kör.
_Dirac_: ha minden pont foka legalább n/2, akkor van Hamilton-kör.
Bizonyítás: Ore tételből következik: d(a)≥n/2, d(b)≥n/2 => d(a)+d(b)≥n (d(a) az a pont fokszáma)

''Hamilton-kör keresés bonyolultsága:''
Legyen H a Hamilton-kört tartalmazó gráfokból álló nyelv. 
*Állítás*: H eleme NP (teljes)

_Euler-kör_: G gráfban egy olyan zárt élsorozat, amely minden élen pontosan egyszer megy át (nem kör, mert metszheti sajátmagát).

_Euler-út_: élsorozat, mely nem feltétlenül zárt, amely minden élen pontosan egyszer megy át (nem út, mert visszatérhetünk egy pontba többször is).

*Tétel*: _Euler-tétel_: G-ben akkor és csak akkor van Euler-kör, ha G összefüggő, és minden pont foka páros.
Bizonyítás:
=> van Euler-kör: biztosan összefüggő, és egy csúcsba annyiszor lépünk be az Euler-kör során, ahányszor ki, minden élet be kell járni és csak egyszer, tehát a fokszámok párosak.
<= G összefüggő (n pontja van), párosak a fokszámok: Tegyük fel, hogy minden k<n-re van a gráfban Euler-kör. Be akarjuk látni, hogy akkor az n pontúban is van. Induljunk el egy pontból, és sétáljunk az éleken úgy, hogy egy élen csak egyszer megyünk át. Ez a séta csak a kiinduló pontban akadhat el, mivel minden pont foka páros. Ekkor hagyjuk el azokat az éleket, amelyeken sétáltunk. Az így kapott, nem feltétlenül összefüggő gráf minden komponensében van Euler-kör.(legfeljebb n-1pont maradhat, mivel a kiinduló pontban már nincs bejáratlan él, és mivel az volt az indukciós feltevés, hogy az n-nél kevesebb élű gráfokban van Euler-kör, ezért minden komponensen van). Így viszont a séta hossza növelhető úgy, hogy vesszük a sétánkat és egy komponens Euler-körét. Ezeket össze lehet építeni úgy, hogy a közös pontból előbb bejárjuk az egyiket, majd a másikat. Majd vesszük a következő komponenst, annak az Euler-körét is hozzáfűzzük az új sétánkhoz. Ha már nincs több komponens, akkor már bejártuk az összes élet, vagyis megvan a G gráf Euler-köre.

*Tétel*: G-ben akkor és csak akkor van Euler-út, ha G összefüggő és pontosan 2 (vagy 0) páratlan fokú pont van.
Bizonyítás: A két páratlan fokút összekötjük egy új éllel. Vissza van vezetve az előző tételre.

-- [[SzaMa|SzaMa]] - 2005.09.17.

[[Category:Infoalap]]

A12. tétel - Laptörténet

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoalap|SzamElmTetelA12}} SzamelmSzig > DaniVeloxKidolgozas > *Hamilton-körök és -utak. Szükséges feltétel Hamilton-kör/út lét…”