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[szerkesztés]
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 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[szerkesztés]
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]
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[szerkesztés]
- Hajnal Péter: Gráfelmélet, Polygon, Szeged, 2003.