Perifer slinga
Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från
versionen som granskades den 31 januari 2022; kontroller kräver
4 redigeringar .
En perifer cykel i en oriktad graf är en cykel som inte separerar någon del av grafen från någon annan. Perifera cykler (eller, som de först kallades, perifera polygoner , som Tutt kallade cykler " polygoner "), studerades först av Tutt, William Thomas [1] . Perifera cykler spelar en viktig roll i beskrivningen av plana grafer och i bildandet av cykliska utrymmen för icke- plana grafer [2] .
Definitioner
En perifer cykel i en graf kan formellt definieras på något av följande sätt:
![C](https://wikimedia.org/api/rest_v1/media/math/render/svg/4fc55753007cd3c18576f7933f6f089196732029)
![G](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5f3c8921a3b352de45446a6789b104458c9f90b)
är en perifer cykel om det är en enkel cykel i en sammankopplad graf med egenskapen att för två kanter och i , det finns en väg i som börjar vid , slutar på , och har inga interna punkter som tillhör [3] .![e_{1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6e81caf3d4bcb929315801cbabc83543829484ee)
![e_{2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4045b5c7cee9bd0681153bbb077489b13269355e)
![{\displaystyle G\setminus C}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4c67777264fb18a4d7b572a9b75ecc105d92cdae)
![G](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5f3c8921a3b352de45446a6789b104458c9f90b)
![e_{1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6e81caf3d4bcb929315801cbabc83543829484ee)
![e_{2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4045b5c7cee9bd0681153bbb077489b13269355e)
![C](https://wikimedia.org/api/rest_v1/media/math/render/svg/4fc55753007cd3c18576f7933f6f089196732029)
är en perifer cykel om det är en genererad cykel med egenskapen att subgrafen som bildas genom att ta bort kanter och hörn på cykeln är ansluten. [fyra]![{\displaystyle G\setminus C}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4c67777264fb18a4d7b572a9b75ecc105d92cdae)
![C](https://wikimedia.org/api/rest_v1/media/math/render/svg/4fc55753007cd3c18576f7933f6f089196732029)
- Om är någon subgraf av grafen , är bryggan [5] av grafen den minimala subgrafen av grafen som inte har gemensamma kanter med och har egenskapen att alla dess fästpunkter (hörn intill kanter som hör till och samtidigt) tillhör [6] . En enkel slinga är perifer om den har exakt en brygga [7]
![C](https://wikimedia.org/api/rest_v1/media/math/render/svg/4fc55753007cd3c18576f7933f6f089196732029)
![G](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5f3c8921a3b352de45446a6789b104458c9f90b)
![C](https://wikimedia.org/api/rest_v1/media/math/render/svg/4fc55753007cd3c18576f7933f6f089196732029)
![B](https://wikimedia.org/api/rest_v1/media/math/render/svg/47136aad860d145f75f3eed3022df827cee94d7a)
![G](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5f3c8921a3b352de45446a6789b104458c9f90b)
![C](https://wikimedia.org/api/rest_v1/media/math/render/svg/4fc55753007cd3c18576f7933f6f089196732029)
![B](https://wikimedia.org/api/rest_v1/media/math/render/svg/47136aad860d145f75f3eed3022df827cee94d7a)
![{\displaystyle G\setminus B}](https://wikimedia.org/api/rest_v1/media/math/render/svg/79e0bc09007036aa11d05c6606c022072724dab3)
![C](https://wikimedia.org/api/rest_v1/media/math/render/svg/4fc55753007cd3c18576f7933f6f089196732029)
![C](https://wikimedia.org/api/rest_v1/media/math/render/svg/4fc55753007cd3c18576f7933f6f089196732029)
Ekvivalensen av dessa definitioner är lätt att se: en sammankopplad subgraf av en graf (tillsammans med kanter som förbinder den med ) eller ett cykelackord som bryter mot cykelgenerering måste i alla fall vara en bro, och det måste också finnas en ekvivalensklass för en binär relation på kanter där två kanter är sammankopplade , om de är ändar på en bana utan inre hörn i [8]![{\displaystyle G\setminus C}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4c67777264fb18a4d7b572a9b75ecc105d92cdae)
Egenskaper
Perifera cykler förekommer i teorin om polyedriska grafer , dvs vertex-3-anslutna plana grafer . För alla plana grafer och alla plana inbäddningar måste ytorna på inbäddningen som genereras av cykler vara perifera cykler. I en polyedrisk graf är alla ytor perifera cykler, och alla perifera cykler är ett ansikte [9] . Detta innebär att (före kombinatorisk ekvivalens, val av yttre yta och orientering av planet) varje polyedrisk graf har en unik plan inbäddning [10] .
![G](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5f3c8921a3b352de45446a6789b104458c9f90b)
![G](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5f3c8921a3b352de45446a6789b104458c9f90b)
I plana grafer bildas det cykliska utrymmet av kanterna, men i icke-planära grafer spelar perifera cykler en liknande roll - för alla vertex-3-kopplade finita grafer bildas det cykliska rummet av perifera cykler [11] . Resultatet kan utökas till lokalt ändliga oändliga grafer [12] . I synnerhet innebär detta att 3-kopplade grafer garanterat innehåller perifera cykler. Det finns 2-kopplade grafer som inte innehåller perifera cykler (ett exempel är en komplett tvådelad graf , där varje cykel har två bryggor), men om en 2-kopplad graf har en minsta grad av tre, så innehåller den minst en perifer cykel [13] .
![{\displaystyle K_{2,4}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a95e1fb5e38742f5ba8731229a76a25e52d4f227)
Perifera cykler i 3-kopplade grafer kan beräknas i linjär tid och har använts för att utveckla tester för planaritet [14] . De har också utvidgats till det mer allmänna begreppet icke-separerande öronexpansion . I vissa algoritmer för att kontrollera planariteten hos grafer är det användbart att hitta en cykel som inte är perifer för att dela upp problemet i mindre delproblem. I en tvåkopplad graf med konturrang mindre än tre (som en cykel eller en tetagraf ) är vilken cykel som helst en periferi, men varje tvåkopplad graf med konturrang tre eller mer har en icke-perifer cykel som kan hittas i linjär tid [15] .
Generaliserande ackordsgrafer definierade Seymour och Weaver [16] en sammandragen graf som en graf där varje perifer cykel är en triangel. De beskrev dessa grafer som klicksummor av ackordsgrafer och maximala plana grafer [17] .
Relaterade begrepp
Perifera cykler kallades också icke-separerande cykler [3] , men denna term är tvetydig, eftersom den används för två andra begrepp - för enkla cykler, vars borttagning gör att den återstående grafen kopplas bort [18] , och för cykler av topologiska cykler. inbäddning av grafen , så att skärning längs cykeln inte gör att ytan som grafen är inbäddad i [19] kopplas bort .
I matroider är en icke-separerande cykel en matroidcykel (d.v.s. minimalt beroende uppsättning) där borttagning av -cykeln lämnar en mindre matroid som är ansluten (dvs. som inte kan delas upp i en direkt summa av matroider) [20] . De liknar perifera cykler, men är inte identiska ens i grafmatroider (matroider där cykler är enkla cykler av en graf). Till exempel, i en komplett tvådelad graf är vilken cykel som helst perifer (den har bara en bro, en bana med två kanter), men grafmatroiden som bildas av denna bro är inte ansluten, så ingen grafgrafmatroidcykel är icke -separerande.
![{\displaystyle K_{2,3}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/12fbb4f29ce32d31e5aeebe69cd58980a32e7c30)
![{\displaystyle K_{2,3}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/12fbb4f29ce32d31e5aeebe69cd58980a32e7c30)
Anteckningar
- ↑ Tutte, 1963 .
- ↑ Tutte, 1963 , sid. 743–767.
- ↑ 1 2 Di Battista, Eades, Tamassia, Tollis, 1998 , sid. 74–75.
- ↑ Detta är den definition som används av Bruhn ( 2004 ). Brun särskiljde dock fallet som har isolerat hörn från frånkopplingen orsakad av cykelborttagning .
![G](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5f3c8921a3b352de45446a6789b104458c9f90b)
- ↑ Inte att förväxla med bridge , ett annat begrepp med samma namn.
- ↑ Tutte, 1960 , sid. 304–320.
- ↑ Denna definition av perifera cykler användes ursprungligen av Tutte ( Tutte 1963 ). Seymour och Weaver ( 1984 ) använde samma definition av en perifer loop, men med en annan bryggdefinition som mer liknar child loop-definitionen för perifera loopar.
- ↑ Se till exempel sats 2.4 i Tutte ( Tutte 1960 ) som visar att en uppsättning brohörn är sammankopplade med banor, se Seymour och Weaver ( 1984 ) för att definiera broar med hjälp av ackord och sammankopplade komponenter, och se även Di Battista, Eades, Tamassia, Tollis 1998 för att definiera broar med användning av ekvivalensklasser för en binär relation på kanter.
- ↑ Tutte, 1963 , sid. Satserna 2.7 och 2.8.
- ↑ Se anmärkningarna efter sats 2.8 i Tuttes artikel ( Tutte 1963 ). Som Tutt noterar var detta redan känt för Whitney ( Whitney 1932 )
- ↑ Tutte, 1963 , sid. Sats 2.5.
- ↑ Bruhn, 2004 , sid. 235–256.
- ↑ Thomassen, Toft, 1981 , sid. 199–224.
- ↑ Schmidt, 2014 , sid. 967-978.
- ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , sid. 75–76 Lemma 3.4.
- ↑ Seymour, Weaver, 1984 .
- ↑ Seymour, Weaver, 1984 , sid. 241–251.
- ↑ Se till exempel ( Borse, Waphare 2008 )
- ↑ Se till exempel ( Cabello, Mohar 2007 )
- ↑ Maia, Lemos, Melo, 2007 , sid. 162–171.
Litteratur
- Tutte WT Hur man ritar en graf // Proceedings of the London Mathematical Society. - 1963. - T. 13 . — S. 743–767 . - doi : 10.1112/plms/s3-13.1.743 .
- Giuseppe Di Battista, Peter Eades, Roberto Tamassia, Ioannis G. Tollis. Grafritning: Algoritmer för visualisering av grafer. - Prentice Hall , 1998. - S. 74-75. — ISBN 978-0-13-301615-4 .
- Tutte WT Konvexa representationer av grafer // Proceedings of the London Mathematical Society. - 1960. - T. 10 . — S. 304–320 . - doi : 10.1112/plms/s3-10.1.304 .
- Hassler Whitney . Icke-separerbara och plana grafer // Transactions of the American Mathematical Society. - 1932. - T. 34 , nr. 2 . — S. 339–362 . - doi : 10.2307/1989545 .
- Henning Bruhn. Cykelutrymmet för en 3-kopplad lokalt finit graf genereras av dess ändliga och oändliga perifera kretsar // Journal of Combinatorial Theory. - 2004. - T. 92 , nr. 2 . — S. 235–256 . - doi : 10.1016/j.jctb.2004.03.005 .
- Carsten Thomassen, Bjarne Toft. Icke-separerande inducerade cykler i grafer // Journal of Combinatorial Theory. - 1981. - T. 31 , nr. 2 . — S. 199–224 . - doi : 10.1016/S0095-8956(81)80025-1 .
- Jens M. Schmidt. The Mondshein Sequence // Proceedings of the 41st International Colloquium on Automata, Languages and Programming (ICALP'14). - 2014. - S. 967-978. - doi : 10.1007/978-3-662-43948-7_80 .
- Seymour PD, Weaver RW En generalisering av ackordsgrafer // Journal of Graph Theory. - 1984. - T. 8 , nr. 2 . — S. 241–251 . - doi : 10.1002/jgt.3190080206 .
- Borse YM, Waphare BN Vertex disjunkt icke-separerande cykler i grafer // The Journal of the Indian Mathematical Society. - 2008. - T. 75 , nr. 1-4 . — S. 75–92 (2009) .
- Sergio Cabello, Bojan Mohar. Hitta kortaste icke-separerande och icke-sammandragbara cykler för topologiskt inbäddade grafer // Diskret och beräkningsgeometri . - 2007. - T. 37 , nr. 2 . — S. 213–235 . - doi : 10.1007/s00454-006-1292-5 .
- Braulio Maia Junior, Manoel Lemos, Tereza RB Melo. Icke-separerande kretsar och samkretsar i matroider // Kombinatorik, komplexitet och slump. — Oxford: Oxford Univ. Press, 2007. - T. 34. - S. 162-171. — (Oxford Lecture Ser. Math. Appl.). - doi : 10.1093/acprof:oso/9780198571278.003.0010 .