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.