Periferikus kör

Ebben a gráfban az 1, 2 és 5 csúcsok háromszöge egy periferikus kört alkot, a megmaradó négy él pedig egyetlen hidat. Az 1–2–3–4–5 ötszög azonban nem periferikus, hiszen a megmaradó két él két külön hidat alkot.

A matematika, azon belül a gráfelmélet területén egy irányítatlan gráf periferikus köre vagy periferiális köre (peripheral circuit) olyan kör, ami nem választja el egymástól a gráf különböző részeit. A periferikus köröket (vagy Tutte sajátos nevezéktana szerint, periferikus sokszögeket) elsőként (Tutte 1963) vizsgálta. Fontos szerepet játszanak a síkbarajzolható gráfok jellemzésében és a nem-síkgráfok körtereinek előállításában.

Definíciók

Egy $G$ gráf $C$ periferikus köre több, egymással ekvivalens módon definiálható:

• $C$ periferikus, ha összefüggő gráf egyszerű köre, mely azzal a tulajdonsággal rendelkezik, hogy $G\setminus C$ bármely két $e_{1}$ és $e_{2}$ éléhez tartozik olyan $G$-beli út, ami $e_{1}$-gyel kezdődik, $e_{2}$-ben végződik és egyetlen belső csúcsa sem tartozik $C$-hez.
• $C$ periferikus, ha olyan feszített kör, melyre igaz, hogy a $C$ csúcsainak és éleinek törlésével kapott $G\setminus C$ részgráf összefüggő.
• Ha $C$ a $G$-nek tetszőleges részgráfja, $C$ egy hídja (bridge) alatt $G$ azon minimális $B$ részgráfját értjük, ami $C$-vel éldiszjunkt és minden csatolódási pontja (A $B$ és $G\setminus B$ élein is rajta lévő csúcsa) $C$-hez tartozik. Egy $C$ egyszerű kör akkor periferikus, ha pontosan egy hídja van.

A fenti definíciók egyenértékűségét nem nehéz belátni: akár a $G\setminus C$ egy összefüggő részgráfjának (az őt $C$-vel összekötő élekkel együtt), akár egy kör annak feszített körségét megakadályozó húrjának hídnak kell lenniük, továbbá az éleken értelmezett bináris reláció ekvivalenciaosztályának, melyben két él akkor van egymással relációban, ha egy olyan út két végén találhatók, melynek nincsenek belső csúcsai $C$-ben.

Tulajdonságok

A periferikus körök megjelennek a poliédergráfok, azaz a 3-szorosan csúcsösszefüggő síkbarajzolható gráfok elméletében. Minden $G$ síkbarajzolható gráf, minden síkba rajzolásának azon tartományainak, melyek feszített körök, periferikus köröknek kell lenniük. Egy poliédergráfban minden tartomány periferikus kör, és minden periferikus kör tartomány. Ebből a tényből következik, hogy (a kombinatorikus ekvivalencia, a külső tartomány választása és a sík orientációja erejéig) minden poliédergráf egyedi síkba ágyazással rendelkezik. A síkbarajzolható gráfok körterét a síkba rajzolás tartományai generálják, míg síkba nem rajzolható gráfok esetében a periferikus körök játszanak hasonló szerepet: bármely 3-szorosan csúcsösszefüggő véges gráf körterét a periferikus körök generálják. Az eredmény kiterjeszthető olyan végtelen gráfokra is, melyek lokálisan végesek. Az előzőekből az is következik, hogy minden 3-szorosan csúcsösszefüggő gráf garantáltan tartalmaz periferikus köröket. Léteznek olyan 2-összefüggő gráfok, amik nem tartalmaznak periferikus köröket (ilyen például a $K_{2,4}$ teljes páros gráf, melynek minden köréhez két híd tartozik), de ha egy 2-összefüggő gráf minimális fokszáma 3, akkor legalább egy periferikus kört tartalmaznia kell. A 3-összefüggő gráfok periferikus körei lineáris időben megkereshetők, ezért síkbarajzolhatósági tesztekben is felhasználják őket. Kiterjesztették őket a nem szeparáló fülfelbontások általánosabb fogalmára is. Egyes síkbarajzolhatóságot tesztelő algoritmusokban hasznos lehet nem periferikus kört keresni a probléma kisebb alproblémákra osztásához. Egy háromnál kisebb ciklikus rangú 2-összefüggő gráf (amilyen egy körgráf vagy egy thétagráf) minden kör periferikus, de a legalább három ciklikus rangú 2-összefüggő gráfokban már lennie kell nem periferikus körnek is, ami lineáris időben megkereshető. (Seymour & Weaver 1984) a merev körű gráfok általánosításaiként úgy definiálja a lekötött gráfokat, hogy a gráfok, melyek minden periferikus köre háromszög. Karakterizációjuk alapján ezek a gráfok, melyek előállnak merev körű gráfok és maximális síkgráfok klikkösszegeiként.

Kapcsolódó fogalmak

A periferikus köröket nevezik nem elválasztó köröknek vagy nem szeparáló köröknek is, de ez a kifejezés kétértelmű, mivel két hasonló, de eltérő fogalomra is használják: egyszerű körök, melyek eltávolítása után nem esik szét a megmaradó gráf, avagy topologikusan beágyazott gráfnál olyan kör, mely mentén végigvágva az adott felületet, melybe a gráf be van ágyazva, a felület nem esik szét. Matroidok esetében egy nem szeparáló kör a matroid olyan köre (tehát egy minimális függő halmaza), melyet kitörölve egy kisebb, összefüggő (kisebb matroidok direkt összegeként fel nem írható) matroid marad. Ezek a periferikus körökkel analóg, de nem teljesen megegyező fogalmak, még a grafikus matroidok (matroidok, melyek körei a gráf egyszerű köreinek felelnek meg) esetében sem. Például a $K_{2,3}$ teljes páros gráf minden köre periferikus (egyetlen hídja van, egy két élből álló út), de a híd által alkotott grafikus matroid nem összefüggő, így a $K_{2,3}$ grafikus matroid egyetlen körére sem igaz, hogy nem szeparáló.

Fordítás

• Ez a szócikk részben vagy egészben a Peripheral cycle című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.