Kör (gráfelmélet)

A Wikipédiából, a szabad enciklopédiából

A gráfelméletben a kör élek olyan egymáshoz csatlakozó sorozata, amelyben az élek és pontok egynél többször nem szerepelhetnek, és a kiindulási pont megegyezik a végponttal.

Jelölések, fogalmak[szerkesztés | forrásszöveg szerkesztése]

A körben szereplő élek száma a kör hossza. Az n hosszú kört Cn-nel jelöljük. Speciálisan C1 neve hurokél, C2 kétszög, C3 pedig háromszög.

Egy kört páros körnek hívunk, ha a hossza páros, különben páratlan kör. Egy gráf akkor és csak akkor páros gráf, ha nem tartalmaz páratlan kört.

Egy gráf girth paraméterét kör segítségével definiáljuk: a gráfban található legrövidebb kör hossza.

Hamilton-kör, Euler-kör[szerkesztés | forrásszöveg szerkesztése]

Egy kör Hamilton-kör, ha minden csúcsot pontosan egyszer érint. Hamilton-kör létezésére vannak elégséges feltételek (Dirac-feltétel, Pósa-feltétel, Ore-feltétel, Chvátal-feltétel), de, mivel a „Van-e adott gráfban Hamilton-kör?” feladat NP-teljes, pontos feltétel megtalálása nem remélhető.

A Hamilton-körrel duális fogalom az Euler-kör (avagy Euler-vonal); ami olyan zárt élsorozat, mely minden élet pontosan egyszer tartalmaz. Egy összefüggő gráfban akkor és csak akkor létezik Euler-kör, ha minden csúcsának fokszáma páros. Euler-kör létezésével kapcsolatos a königsbergi hidak problémája.

Körmentes gráf[szerkesztés | forrásszöveg szerkesztése]

Körmentesnek (vagy aciklikusnak) nevezzük az olyan gráfot, amely nem tartalmaz kört. Ha egy körmentes gráf összefüggő, akkor fa. Mivel minden körmentes gráf fák (esetleg egyelemű) halamza, a körmentes gráfokat erdőnek is nevezzük. Az irányított körmentes gráfok jelentős szerepet játszanak a számítástudományban.

Forrás[szerkesztés | forrásszöveg szerkesztése]

  • Hajnal Péter: Gráfelmélet, Polygon, Szeged, 2003.