A12. tétel

Ez az oldal a korábbi SCH wikiről lett áthozva.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor, kérlek, javíts rajta egy rövid szerkesztéssel!

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót.

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 (v₁,v₂,…,v_n) és legyen v_i1,v_i2,…,v_ik 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 (v_i1+1,v_i1+2,…,v_i2-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 - 2005.09.17.