Fül bomlás

A gráfelméletben egy irányítatlan G gráf füle egy P út , amelynek két végpontja egybeeshet, de egyébként nem megengedett a csúcsok vagy élek ismétlése, így P bármely belső pontjának kettős fokozata van az úton. Egy irányítatlan G gráf füldekompozíciója az élének felosztása egy fülsorozatba úgy, hogy az egyes fülek végpontjai a sorozatban korábban kiválasztott fülekhez tartoznak, míg az egyes fülek belső csúcsai nem tartoznak az előzőhöz. fülek. Ezenkívül a legtöbb esetben a sorozat első fülének huroknak kell lennie. A nyitott vagy megfelelő füllebontás olyan füldekompozíció, amelyben az elsőtől eltérő mindkét fül két végpontja eltérő.

A füldekompozíció felhasználható a gráfok néhány fontos osztályának leírására, valamint hatékony gráfalgoritmusok részeként . A füldekompozíció matroidokra általánosítható .

A gráfosztályok leírása

A gráfok néhány fontos osztálya bizonyos típusú füldekompozíciókkal írható le.

Grafikon csatlakoztathatóság

Egy gráf csúcs-k-összefüggő , ha csak ( k − 1) csúcsok eltávolításával az algráf összekapcsolt marad, és k-él-összefüggésben van , ha bármely ( k − 1) él eltávolításával az algráf összekapcsolt marad.

A következő eredmény Hasler Whitneynek köszönhető [1] :

Egy csúcsú gráf akkor és csak akkor 2-kapcsolt, ha nyitott fülű dekompozíciója van.

G=(V,E)

|E|\geq 2

A következő eredmény Herbert Robinsonnak köszönhető [2] :

Egy gráf akkor és csak akkor 2 élű, ha van füldekompozíciója.

Mindkét esetben a fülek számának meg kell egyeznie a grafikon kontúrrangjával . Robbins a 2 élhez kapcsolódó gráfok füldekompozícióját használta annak bizonyítására , hogy Robbins tétele , hogy ezek pontosan olyan gráfok, amelyeknek erősen összefüggő orientációt lehet adni. Mivel Whitney és Robinson volt az első, aki feltárta a fül bomlását, ezt néha Whitney–Robinson szintézisnek is nevezik [3] .

A nem elválasztó fül-felbontás egy nyitott fül-felbontás, amelyben v minden csúcsához egy kivételével van egy szomszédos csúcs, amely később jelenik meg, mint v a dekompozícióban . Ez a fajta dekompozíció használható Whitney eredményének általánosítására:

Egy c gráf akkor és csak akkor kapcsolódik 3 csúcshoz, ha G nem szeparáló fülfelbontással rendelkezik.

G=(V,E)

|V|\geq 2

Ha létezik ilyen dekompozíció , akkor G egy uv élére úgy választhatjuk meg , hogy u az első fülhöz tartozik, v egy új csúcs az utolsó fülben több éllel, és uv egy fül, amely egy élből áll. él. Ezt az eredményt először Cheryan és Maheshwari mondta ki kifejezetten [4] , de ahogy Schmidt írja [5] , ez egyenértékű a Ph.D. eredményével. Lee Mondshein 1971-es értekezése. A maximális síkbeli gráfok nem elválasztó füldekompozícióihoz szorosan kapcsolódó struktúrák, amelyeket kanonikus rendezéseknek neveznek, szintén szabványos gráfvizualizálók .

Az irányított gráfok erős összekapcsolhatósága

A fent megadott definíciók kiterjeszthetők irányított gráfokra is . A fül ekkor egy olyan irányított út, amelyben minden belső csúcs indegre és külső foka egyenlő 1-gyel. Egy irányított gráf erősen összefügg , ha bármely csúcsból bármely másik csúcsba irányított utat tartalmaz. Ekkor teljesül a következő tétel:

Egy irányított gráf akkor és csak akkor erősen összefüggő, ha füldekompozíciója van.

Hasonlóképpen, egy irányított gráf kétszeresen kapcsolódik , ha bármely két csúcsra létezik egy egyszerű ciklus, amely mindkét csúcsot tartalmazza. Akkor

Egy irányított gráf akkor és csak akkor kapcsolódik kétszeresen, ha nyitott fülű dekompozíciója van.

Tényezőkritikus grafikonok

A füllebontás páratlan , ha minden fülnek páratlan számú éle van. A faktorkritikus gráf páratlan számú csúcsú gráf, így ha bármelyik v csúcsot eltávolítjuk a gráfból, a fennmaradó csúcsok tökéletesen illeszkednek . Lovas László [6] megállapította, hogy:

A G gráf akkor és csak akkor faktorkritikus gráf, ha G -nek páratlan füldekompozíciója van.

Általánosságban elmondható, hogy Frank eredménye [7] lehetővé teszi, hogy bármely G gráfra olyan füldekompozíciót találjunk, amelyben a legkevesebb páros fül.

Párhuzamos-szekvenciális gráfok

A fafül dekompozíció olyan megfelelő fülbontás, amelyben az első fül egyetlen él, és minden következő fülhez tartozik egy egyedi fül , , amelyben mindkét végpont a [8] -on fekszik . A beágyazott fülfelbontás olyan fafül-felbontás, amely minden fülön belül a -n belüli más fülek végpontpárjainak halmaza beágyazott intervallumok halmazát alkotja. A párhuzamos-soros gráf két különálló s és t végű gráf , amely rekurzív módon alakítható ki kisebb párhuzamos soros gráfok kétféle módon történő kombinálásával - soros kapcsolat (az egyik gráf egyik végét azonosítjuk a a másik gráf, a másik pedig mindkét gráf két vége lesz az unió vége) és párhuzamos kapcsolat (mindkét kisebb gráf mindkét kapocspárját azonosítjuk). ${\displaystyle P_{i))$ ${\displaystyle P_{j))$ $i>j$ ${\displaystyle P_{i))$ ${\displaystyle P_{j))$ ${\displaystyle P_{j))$ ${\displaystyle P_{i))$ ${\displaystyle P_{j))$

A következő eredmény David Epsteinnek köszönhető [9] :

A 2-es csúcshoz kapcsolódó gráf akkor és csak akkor párhuzamos soros gráf, ha van beágyazott fül-dekompozíciója.

Ezen túlmenően egy 2-csúccsal összekapcsolt párhuzamos soros gráf bármely nyitott fülű dekompozícióját be kell ágyazni. Az eredmény általánosítható párhuzamos-szekvenciális gráfokra, amelyek nem 2-csúcsként kapcsolódnak egymáshoz egy nyitott fül dekompozíció segítségével, amely a két vége közötti útvonalból indul ki.

Matroidok

A füldekompozíció fogalma a grafikonoktól a matroidokig általánosítható . A matroid fül dekompozícióját a matroid ciklusok sorozataként határozzuk meg, amelynek két tulajdonsága van:

a szekvencia minden ciklusának van egy nem üres metszéspontja az előző hurokkal.
a sorozat minden ciklusa ciklus marad, még akkor is, ha a szekvencia összes előző ciklusát összehúzzuk.

Ha egy G gráf gráfmatroidjára alkalmazzuk, a füldekompozíciónak ez a definíciója megegyezik G megfelelő dekompozíciójának definíciójával – a helytelen dekompozíciókat kizárja az a követelmény, hogy minden ciklus tartalmazzon legalább egy élt. az előző ciklusokhoz. Ezzel a definícióval egy matroidot akkor határozhatunk meg hányados-kritikusnak, ha van egy füldekompozíciója, amelyben a sorozat minden ciklusában páratlan számú új elem van [10] .

Algoritmusok

A 2 élhez kapcsolódó gráfok füldekompozíciója és a 2 csúcshoz kapcsolódó gráfok nyílt dekompozíciója megtalálható olyan mohó algoritmusok segítségével , amelyek egyenként találják meg az egyes füleket. Schmidt javasolta egy egyszerű mohó algoritmust, amely a fültágulást, a nyitott fültágulást, az st-számozást és az st-orientációt lineáris időben (ha létezik) ugyanabban az időben számítja ki [11] . A megközelítés egy speciális füllebontás, a láncbontás egyútvonal-generálási szabállyal történő kiszámításán alapul . Schmidt megmutatta [5] , hogy lineáris időben fel lehet építeni egy nem szeparáló füldekompozíciót.

Lovas [12] , Maon, Shiber és Vyshkin [13] , valamint Miller és Ramachandran [14] hatékony párhuzamos algoritmusokat nyújtottak különböző típusú füldekompozíciók megalkotásához. Például egy 2 élhez kapcsolódó gráf füldekompozíciójának megtalálásához Maon, Schieber és Wyshkin [13] algoritmusa a következő lépéseken megy keresztül:

Megkeresi az adott gráf feszítőfáját és kiválasztja a fa gyökerét.
Minden olyan uv élre , amely nem része a fának, határozza meg a távolságot u és v gyöke és legkisebb közös őse között .
Minden uv élhez , amely a fa részét képezi, keresse meg a megfelelő "főélt", egy wx élt, amely nem a fától származik, úgy, hogy a wx fához való hozzáadásával létrehozott ciklus átmenjen az uv -n, és úgy, hogy az összes w és x él között a legalacsonyabb őse van a lehető legközelebb a gyökérhez.
Minden nem fa élhez egy fület képezünk, amely ebből az élből és a fa éleiből áll, amelyeknél ez az él a fő. A füleket a főélnek a gyökértől való távolsága szerint rendezzük el.

Ez az algoritmus más problémák megoldására is használható, beleértve a kapcsolódás ellenőrzését, a soros párhuzamos gráfok felismerését és a gráfok st -számozásának létrehozását (a síkság ellenőrzésének fontos eljárása ).

Egy matroid füldekompozíciója azzal a további megszorítással, hogy bármely fül ugyanannyi fix számú matroid elemet tartalmazzon, megtalálható polinomiális időben , ha van függetlenségi orákulum a matroidhoz [15] .

Irodalom

J. Cheriyan, S. N. Maheshwari. Nem szétválasztó indukált ciklusok és független feszítőfák keresése 3 összekapcsolt gráfokban // Journal of Algorithms. - 1988. - T. 9 , sz. 4 . – S. 507–537 . - doi : 10.1016/0196-6774(88)90015-6 .
Collette R. Collard, Lisa Hellerstein. Függetlenség és port orákulumok matroidokhoz, alkalmazással a számítási tanuláselmélethez // Combinatorica . - 1996. - T. 16 , sz. 2 . – S. 189–208 . - doi : 10.1007/BF01844845 .
D. Eppstein. Sorozatpárhuzamos gráfok párhuzamos felismerése // Information & Computation. - 1992. - T. 98 , sz. 1 . – S. 41–55 . - doi : 10.1016/0890-5401(92)90041-D .
Frank András. Grafikonok konzervatív súlyozásai és fül-dekompozíciói // Combinatorica . - 1993. - T. 13 , sz. 1 . – 65–81 . - doi : 10.1007/BF01202790 .
Jonathan L. Gross, Jay Yellen. Gráfelmélet és alkalmazásai. — 2. – Chapman & Hall/CRC, Boca Raton, FL, 2006. – 498–499. - (Diszkrét matematika és alkalmazásai (Boca Raton)). - ISBN 978-1-58488-505-4 .
Samir Huller. Füldekompozíciók // SIGACT News . - 1989. - T. 20 , sz. 1 . - S. 128 .
Lovasz László . Megjegyzés a faktorkritikus grafikonokhoz // Studia Sci. Math. Hung .. - 1972. - T. 7 . – S. 279–280 .
Lovasz László. 26. éves szimpózium a számítástechnika alapjairól . - 1985. - S. 464-467. - doi : 10.1109/SFCS.1985.16 .
Y. Maon, B. Schieber, U. Vishkin. Párhuzamos füldekompozíciós keresés (EDS) és ST-számozás gráfokban // Elméleti számítástechnika . - 1986. - T. 47 , sz. 3 . - doi : 10.1016/0304-3975(86)90153-2 .
G. Miller , V. Ramachandran. Hatékony párhuzamos füllebontás alkalmazásokkal. - Kiadatlan kézirat, 1986.
H.E. Robbins . Tétel a grafikonokról, alkalmazással egy forgalomirányítási problémára // American Mathematical Monthly . - 1939. - T. 46 . – S. 281–283 . - doi : 10.2307/2303897 . .
Jens M. Schmidt. Egy egyszerű teszt a 2-csúcs- és 2-él-kapcsolaton // Információfeldolgozási levelek. — 2013a. - T. 113 , sz. 7 . – S. 241–244 . - doi : 10.1016/j.ipl.2013.01.016 .
Jens M. Schmidt. Mondshein sorozat. — 2013b.
Alexander Schrijver . kombinatorikus optimalizálás. Poliéder és hatékonyság. A. kötet – Springer-Verlag, 2003. – ISBN 978-3-540-44389-6 .
Szegedy Balázs, Szegedy Christian. A matroidok szimplektikus terei és fül-dekompozíciója // Combinatorica . - 2006. - T. 26 , sz. 3 . – S. 353–377 . - doi : 10.1007/s00493-006-0020-3 .
H. Whitney . Nem szétválasztható és síkbeli gráfok // Transactions of the American Mathematical Society . - 1932. - T. 34 . – S. 339–362 . - doi : 10.1090/S0002-9947-1932-1501641-2 . — .