Soros párhuzamos gráfok

Soros párhuzamos gráfok elsõ definíciója: Egy két pontú, két párhuzamos élt tartalmazó gráfból kiindulva két operáció ismételt alkalmazásával megkapható gráfok lesznek a soros párhuzamos gráfok. A két operáció: egy él mellé egy párhuzamos él behúzása, egy él egy új ponttal történõ felosztása.

Soros párhuzamos gráfok második definíciója: Ebben az esetben a gráfok egy éle ki lesz tüntetve és irányítással el lesz látva. Ezt az élt alapélnek nevezzük (az alapél kezdõpontja a forrás, a végpontja nyelõ). Kiindulásként adott ``sok'' két pontú, két párhuzamos éllel rendelkezõ gráf. Ezekbõl párhuzamos és soros összeolvasztásokkal nyert gráfokat nevezzük soros-párhuzamos gráfoknak. A párhuzamos összeragasztás a két alapél (irányítást is figyelembe vevõ azonosítása. A soros összekapcsolásban az elsõ gráf nyelõjét azonosítjuk a második gráf forrásával és a két alapél helyett az új alapél az elsõ gráf nyelõjébõl halad a második gráf forrásába.

A fenti két definíció ekvivalens: A második definíció szerint soros-párhuzamos gráf, elfelejtve az alapélét az elsõ defíníció szerint is soros-párhuzamos gráf. Az elsõ definíció szerint soros-párhuzamos gráf tetszõleges éle kijelölésével és ennek tetszõleges irányításával soros-párhuzamos gráf lesz. Ennek igazolása egyszerû, de formális leírása hosszadalmas. Egy példa vizsgálatával azonban mindenki meggyõzõdhet i gazságáról.

Megjegyzés: A fenti két definíció nem állíthat elõ akármilyen gráfokat. A kapott gráfok rendelkeznek azzal a tulajdonsággal, hogy nincs izolált csúcsuk, legalább két élük van és bármely két élük egy körön van. Az ilyen gráfokat Whitney szerint kétszeresen összefüggõnek nevezzük. (Ez a kétszeres összefüggõség eltér a szokásostól: a megfelelõ gráfban nem lehet hurokél, elképzelhetõ viszont hogy csak két csúcsa van, amely koz;öt legalább két párhuzamos él fut.)

A soros-párhuzamos gráfok kiterjesztett definíciója: Egy gráf (általános) soros-párhuzamos gráf, ha blokkjai (az éleken azon ekvivalencireláció osztályai által feszi;tett gráfok, amely szerint két él akkor és csak akkor vamn relációban, ha egybeesnek, vagy egy körön vannak) egy elemûek vagy az elõzõ értelemben véve soros-párhuzamos gráfok.

Megjegyzés: A fenti kiterjesztett definíció elmondható az elsõ definíció módosításával. Egy gráf (általános) soros párhuzamos gráf az egy pontú nulla élû gráfból kiindulva öt operáció ismételt alkalmazásával megkapható gráfok. Az öt operáció: (i) egy él mellé egy párhuzamos él behúzása, (ii) egy él egy új ponttal történõ felosztása, (iii) egy új izolált pont felvétele, (iv) tetszõleges pontnál hurokél hozzáadása, (v) tetszõleges pontban egy ág hajtása, azaz egy új pont felvételé és egyetlen új él segítségével ennek ``bekötése '' a kiinduló csúcshoz. Ezen definíció ekvivalenciája az elõzõvel újból egy nem nehéz, de formálisan nehezen leírható bizonyítás. Mindeki gyõzze meg magát igaz voltáról.