Kör (gráfelmélet)

Lásd még: körgráf.

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

A körben szereplő élek száma a kör hossza. Az n hosszú kört C_n-nel jelöljük. Speciálisan C₁ neve hurokél, C₂ kétszög, C₃ 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 girthparamé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

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

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ű) halmaza, 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ások

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