Vino-symmetrinen kaavio

Vinosymmetrinen graafi on suunnattu graafi , joka on isomorfinen oman transponoidun graafinsa kanssa . Tämä kuvaaja on muodostettu kääntämällä kaikki kaaret isomorfismin kanssa ja se on involuutio ilman kiinteitä pisteitä . Vinosymmetriset graafit ovat identtisiä kaksisuuntaisten graafien kaksoispeitteiden kanssa .

Vinosymmetriset graafit esiteltiin ensin nimellä antisymmetriset digraafit Tutt [1] , myöhemmin polaaristen graafien kaksoispeittograafien nimellä niitä käytti Zelinka [2] ja myöhemmin nimellä kaksisuuntaisten graafien kaksoispeittokuvaajat. Zaslavskyn käyttämä [3] . Niitä esiintyy esimerkiksi mallinnettaessa vuorottelevien polkujen ja syklien etsintää, algoritmeissa, joilla etsitään yhteensopivuutta testausta varten, ongelmassa, joka koskee konfiguraation hajottamista Game of Lifessa pienemmiksi komponenteiksi, graafin visualisointiongelmassa ja Tuloskaavioiden muodostamisen ongelma [ . käytetään ratkaisemaan tehokkaasti 2-täytettävyysongelma .

Määritelmä

Kuten esimerkiksi Goldberg ja Karzanov [4] määrittelivät, vinosymmetrinen graafi on suunnattu graafi yhdessä funktion kanssa , joka kartoittaa graafin kärjet sen muihin pisteisiin ja täyttää ominaisuudet: $G$ $\sigma$ $G$

Kaikille yläosille $v,\sigma (v)\neq v$
Kaikille yläosille $v,\sigma (\sigma (v))=v$
Jokaiselle kaarelle on myös oltava kaari. ${\näyttötyyli (u,v),(\sigma (v),\sigma (u))}$

Voit käyttää kolmatta ominaisuutta laajentaaksesi kaavion kaaren suunnan käänteistoimintoon . $\sigma$ $G$

Graafin transponoitu graafi on graafi , joka on muodostettu kääntämällä graafin jokainen reuna ja se määrittelee isomorfismin kohteesta transponoituun graafiin. Vinosymmetriselle graafille on kuitenkin lisävaatimus, että isomorfismi vie jokaisen kärjen toiseen kärkeen antamatta kärjen kartoittua itseensä tai ryhmitellä useampaa kuin kahta kärkeä isomorfismisyklissä. $G$ $G$ $\sigma$ $G$

Vinosymmetrisen graafin polun tai syklin sanotaan olevan säännöllinen , jos polun tai syklin jokaisessa kärjessä vastaava kärki ei ole osa polkua tai sykliä. $v$ $\sigma (v)$

Esimerkkejä

Mikä tahansa suunnattu polku , jossa on parillinen määrä pisteitä, on vinossa-symmetrinen polun kaksi päätä vaihtavan symmetrian mukaan. Polut, joissa on pariton määrä pisteitä, eivät kuitenkaan ole vinosymmetrisiä, koska tämän graafin käänteinen orientaatiosymmetria kartoittaa tämän graafin keskipisteen itseensä, mikä ei ole sallittua vinosymmetrisille kaavioille.

Vastaavasti orientoitu sykli on vinosymmetrinen silloin ja vain, jos sillä on parillinen määrä pisteitä. Tässä tapauksessa graafin vinosymmetrian toteuttavien eri kuvausten määrä on yhtä suuri kuin puolet syklin pituudesta . $\sigma$

Napakuvaajat ja polkunuolet, kaksoiskansikuvaajat ja kaksisuuntaiset kaaviot

Vinosymmetrinen graafi voidaan määritellä vastaavasti napagraafin kaksoispeitteen kuvaajaksi (jotka esitteli Zelinka [5] [6] , ja Cook kutsuivat polunuoligraafit [7] [8] ), jotka ovat suuntaamattomia graafia ja jossa kunkin kärjen vieressä olevat reunat jaetaan kahdeksi osajoukoksi. Polaarisen graafin kukin kärki vastaa vinosymmetrisen graafin kahta kärkeä, ja napagraafin jokainen reuna vastaa vinosymmetrisen graafin kahta reunaa. Tätä ekvivalenssia käyttivät Goldberg ja Karzanov [4] mallintaakseen yhteensopivuusongelmia vinosymmetristen graafien suhteen. Tällaisessa sovelluksessa reunojen kaksi osajoukkoa kussakin kärjessä ovat yhteensopivia ja yhteensopimattomia reunoja. Zelinka (F. Zaitekin mukaan) ja Cook visualisoivat napagraafin kärjet pisteinä, joissa useat raideraiteet yhtyvät jos juna tulee yhdestä suunnasta tulevan radan vaihteeseen, sen on poistuttava radan kautta. toiseen suuntaan. Ei-itseleikkautuvien sileiden käyrien löytämisen ongelma radan tiettyjen pisteiden välillä syntyy, kun tarkistetaan, onko jonkinlainen graafivisualisointi sallittu [9] , ja se voidaan mallintaa säännöllisen polun löytämiseksi vinosymmetrisessä kaaviossa.

Läheisesti liittyvä käsite on Edmondsin ja Johnsonin [10] kaksisuuntainen graafi ("polarisoitu graafi" Zelinkan [5] [6] terminologiassa ), graafi, jossa minkä tahansa reunan kahdesta kärjestä voi olla joko alku tai loppu, riippumatta toisesta huipusta. Kaksisuuntainen graafi voidaan tulkita polaariseksi graafiksi, jos kunkin kärjen reunat on jaettu reunan suunnan mukaan kyseisessä kärjessä - alussa tai lopussa. Alkujen ja loppujen roolien vaihto erillisessä kärjessä (pisteen "vaihtaminen" Zaslavskyn terminologiassa [3] ) antaa kuitenkin toisen kaksisuuntaisen graafin, mutta saman polaarisen graafin.

Kaksisuuntaisten graafien ja vinosymmetristen graafien vastaavuudesta, katso Zaslavsky [11] tai Babenko [12] .

Muodostaaksemme kaksoispeittograafin (eli vastaavan vinosymmetrisen graafin) napagraafista luomme kaksi kärkeä graafin kustakin kärjestä ja , ja annamme . Luo kullekin graafin reunalle kaksi suunnattua reunaa peittävässä graafissa, yksi kohteesta - ja toinen kohteesta - . Jos se on reunojen ensimmäisessä osajoukossa , nämä kaksi kaarta menevät osoitteesta ja alkaen , mutta jos se kuuluu toiseen osajoukkoon, kaaret ovat alkaen ja alkaen . Päinvastoin, vinosymmetrinen graafi voidaan muodostaa polaarinen graafi, jossa on yksi piste jokaiselle vastaavalle graafin pisteparille ja yksi suuntaamaton reuna kullekin vastaavalle reunaparille . Suuntamattomat reunat napagraafin kussakin kärjessä voidaan jakaa kahteen osajoukkoon sen mukaan, kummasta alkuperäisen graafin kärjestä kaari lähtee ja tulee. $G$ $v$ $G$ $v_{0}$ $v_{1}$ $\sigma (v_{i})=v_{1-i}$ $e=(u,v)$ $G$ $u$ $v$ $v$ $u$ $e$ $v$ $u_{0}$ $v_{0}$ $v_{1}$ $u_{1}$ $e$ $u_{0}$ $v_{1}$ $v_{0}$ $u_{1}$ $G$ $G$ $G$

Säännöllinen polku tai sykli vinosymmetrisessä graafissa vastaa polkua tai sykliä polaarisessa graafissa, joka käyttää korkeintaan yhtä reunaa kustakin särmien osajoukosta kussakin sen kärjessä.

Vastaava

Suuntaamattomaan graafiin sovitusta rakennettaessa on tärkeää löytää vuorotteleva polku , polku pisteiden läpi, joka alkaa ja päättyy pisteisiin, jotka eivät kuulu sovitukseen ja joiden reunat polun parittomissa paikoissa eivät kuulu tähän. osittainen sovitus, ja jonka reunat polun parillisissa kohdissa ovat sovituksen reunoja. Poistamalla sovituksesta kyseiseltä polulta sovitukseen kuuluvat reunat ja lisäämällä siihen loput polun reunat, voidaan sovituksen kokoa suurentaa. Samoin syklit, jotka vuorottelevat yhteensopivien ja ei-sopivien reunojen välillä, ovat tärkeitä painotetuissa sovitusongelmissa. Kuten Goldberg ja Karzanov [4] ovat osoittaneet , suuntaamattoman graafin vuorotteleva polku tai sykli voidaan mallintaa säännölliseksi poluksi tai sykliksi vinosymmetrisesti suunnatussa graafissa. Luodaksesi vinosymmetrisen graafin suuntaamattomasta graafista tietyllä sovituksella , katso graafia nuoligraafina, jossa kunkin kärjen reunat on jaettu yhdistelmään kuuluviin ja ei kuuluviin. Vaihteleva polku kaaviossa on tällöin säännöllinen polku nuolikaaviossa, ja kaavion vuorotteleva sykli on säännöllinen sykli nuolikaaviossa. $G$ $M$ $G$ $G$ $G$

Goldberg ja Karzanov [4] yleistivat vuorottelevia polkualgoritmeja osoittaakseen, että säännöllisen polun olemassaolo vinosymmetrisen graafin minkä tahansa kahden kärjen välillä voidaan varmistaa lineaarisessa ajassa. Jos lisäksi annetaan ei-negatiivinen pituusfunktio graafin reunoilla, joka määrittää yhtä pituudet reunalle ja reunalle , lyhin säännöllinen polku, joka yhdistää tietyn solmuparin vinosymmetrisessä graafissa, jossa on reunat ja kärjet löytyy ajoissa . Jos pituusfunktio voi saada negatiivisia arvoja, negatiivisen säännöllisen syklin olemassaolo voidaan varmistaa polynomiajassa . $e$ $\sigma (e)$ $m$ $n$ $O(m\log n)$

Sovituksen kanssa työskennellessä syntyvien polkuongelmien lisäksi tutkittiin myös maksimivirtauksen ja minimileikkauslauseen vinosymmetrisiä yleistyksiä [1] [13] .

Theory of the Game of Life

Cook [8] osoitti, että Game of Lifen konfiguraatio voidaan jakaa kahdeksi pienemmäksi konfiguraatioksi, jos ja vain, jos siihen liittyvän matkanuolikaavion kaavio sisältää säännöllisen syklin. Nuoligraafissa, joka sisältää korkeintaan kolme reunaa kärkeä kohti, tämä voidaan tarkistaa polynomiajassa poistamalla yksitellen sillat (reunat, joiden poistaminen tekee graafista irti) ja kärjet, joissa kaikki reunat kuuluvat samaan osion osaan. tällaisia yksinkertaistuksia on mahdollista toteuttaa. Jos tulos on tyhjä graafi, kaaviossa ei ole säännöllistä sykliä. Muutoin säännöllinen sykli löytyy mistä tahansa ei-silloitetusta komponentista. Tämän algoritmin siltojen haku voidaan tehdä tehokkaasti käyttämällä dynaamista Sorup-algoritmia [14] . Gabov, Kaplan ja Tarjan harkitsivat aiemmin samanlaista tekniikkaa siltojen poistamiseksi sovitusten yhteydessä [15] .

Toteutettavuus

2 -täytettävyysongelma , eli lauseke konjunktiivisessa normaalimuodossa , jossa on kaksi muuttujaa tai niiden negaatio, voidaan muuntaa lähtögraafiksi korvaamalla jokainen lauseke kahdella implikaatiolla ja . Tässä kaaviossa jokainen kärki edustaa muuttujaa tai sen negaatiota ja jokainen suunnattu reuna edustaa implikaatiota. Kaavio on rakenteeltaan vinosymmetrinen funktiolla , joka kartoittaa jokaisen muuttujan negaatioonsa. Kuten Asvall, Plass ja Tarjan [16] ovat osoittaneet , tyydyttävän arvojoukon löytäminen 2-tyydytettävyysongelman esiintymälle vastaa tämän tulosgraafin jakamista kahdeksi kärkien osajoukoksi ja siten, että kaari ei ala. klo ja päättyy klo . Jos tällainen jako on olemassa, tyydyttävä arvojoukko voidaan saada antamalla jokaiselle muuttujalle arvo True ja jokaiselle muuttujalle arvo False . Tämä voidaan tehdä silloin ja vain, jos mikään graafin vahvasti kytketty komponentti ei sisällä sekä kärkeä että sen komplementtipistettä . Jos kaksi kärkeä kuuluu samaan vahvasti toisiinsa liittyvään komponenttiin, vastaavat muuttujat tai niiden negaatiot ovat välttämättä yhtä suuria toistensa kanssa missä tahansa tyydyttävässä 2-täytettävyysongelman esiintymän tyydyttävässä arvojoukossa. Vahvan yhteyden tarkistamisen ja tulosgraafin osion löytämisen kokonaisaika on lineaarinen tietyn 2-CNF-lausekkeen koossa. ${\näyttötyyli u\tai v}$ $(\lnot u)\Rightarrow v$ $(\lnot v)\Rightarrow u$ $\sigma$ $S$ $\sigma (S)$ $S$ $\sigma (S)$ $S$ $\sigma (S)$ $v$ $\sigma (v)$

Tunnustus

Ongelma sen tunnistamisessa, onko tietty suunnattu graafi vinosymmetrinen, on NP-täydellinen . Tämä seuraa Lalonden tuloksesta [17] , että ongelma värin käänteisen involuution löytämisessä kaksiosaisessa graafissa on NP-täydellinen, jos ja vain, jos kunkin reunan orientaation yhdestä väriluokasta toiseen antama suunnattu graafi on vinosymmetrinen. . Tämä monimutkaisuus ei vaikuta vinosymmetristen graafien polunetsintäalgoritmeihin, koska nämä algoritmit olettavat, että vinosymmetrinen rakenne annetaan osana algoritmin syötettä sen sijaan, että se olisi johdettu graafista.

Muistiinpanot

↑ 1 2 Tutte, 1967 .
↑ Zelinka, 1976b .
↑ 12 Zaslavsky , 1991 .
↑ 1 2 3 4 Goldberg, Karzanov, 1996 .
↑ 1 2 Zelinka, 1974 .
↑ 12 Zelinka , 1976a .
↑ Vaihteistokäyrä tulee kaavion esityksestä rautatiekiskoja vastaavana, yksittäisten haarojen risteyksissä vaihtonuolina.
↑ 12 Cook , 2003 .
↑ Hui, Schaefer, Štefankovič, 2004 .
↑ Edmonds, Johnson, 1970 .
↑ Zaslavsky, 1991 , s. Osa 5.
↑ Babenko, 2006 .
↑ Goldberg, Karzanov, 2004 .
↑ Thorup, 2000 .
↑ Gabow, Kaplan, Tarjan, 1999 .
↑ Aspvall, Plass, Tarjan, 1979 .
↑ Lalonde, 1981 .

Kirjallisuus

Bengt Aspvall, Michael F. Plass, Robert E. Tarjan. Lineaariaikainen algoritmi tiettyjen kvantifioitujen Boolen kaavojen totuuden testaamiseen // Tietojenkäsittelykirjaimet. - 1979. - T. 8 , no. 3 . — S. 121–123 . - doi : 10.1016/0020-0190(79)90002-4 .
Maxim A. Babenko. Asykliset kaksisuuntaiset ja vinosymmetriset graafit: algoritmit ja rakenne // Tietojenkäsittelytiede - Teoria ja sovellukset. - Springer-Verlag, 2006. - T. 3967. - S. 23-34. — (Luentomuistiinpanot tietojenkäsittelytieteestä). - ISBN 978-3-540-34166-6 . - doi : 10.1007/11753728_6 .
Norman L. Biggs. Algebrallinen graafiteoria. – Lontoo: Cambridge University Press, 1974.
Matthew Cook. Asetelmateoria // Uudet rakenteet soluautomaatissa. - Santa Fe Institute Studies in the Sciences of Complexity, Oxford University Press, 2003. - s. 93–118. .
Jack Edmonds, Ellis L. Johnson. Vastaavuus: hyvin ratkaistu lineaaristen ohjelmien luokka // Kombinatoriset rakenteet ja niiden sovellukset: Calgary Symposiumin julkaisu, kesäkuu 1969. - Gordon ja Breach, 1970. Uusintapainos julkaisussa "Combinatorial Optimization - Eureka, You Shrink!", Springer-Verlag , Lecture Notes in Computer Science 2570, 2003, s. 27-30, doi : 10.1007/3-540-36478-1_3 .
Harold N. Gabow, Haim Kaplan, Robert E. Tarjan . Ainutlaatuiset enimmäissovitusalgoritmit // Proc. 31. ACM Symp. Tietojenkäsittelyteoria (STOC). - 1999. - S. 70-78. — ISBN 1-58113-067-8 . - doi : 10.1145/301250.301273 .
Andrew V. Goldberg, Alexander V. Karzanov. Polkuongelmat vinosymmetrisissä kaavioissa // Combinatorica. - 1996. - T. 16 , no. 3 . — S. 353–382 . - doi : 10.1007/BF01261321 .
Andrew V. Goldberg, Alexander V. Karzanov. Maksimi vinosymmetriset vuot ja sovitukset // Matemaattinen ohjelmointi. - 2004. - T. 100 , no. 3 . — S. 537–568 . - doi : 10.1007/s10107-004-0505-z . — arXiv : math/0304290 .
Peter Hui, Marcus Schaefer, Daniel Štefankovič. Junaradat ja yhtymäpiirrokset // Proc. 12th Int. Symp. Graafinen piirustus . - Springer-Verlag, 2004. - T. 3383. - S. 318-328. — (Luentomuistiinpanot tietojenkäsittelytieteestä).
Francois Lalonde. Le problème d'étoiles pour graphes est NP-complet // Discrete Mathematics. - 1981. - T. 33 , no. 3 . — S. 271–280 . - doi : 10.1016/0012-365X(81)90271-5 .
Mikkel Thorup. Lähes optimaalinen täysin dynaaminen [ sic ] graafiyhteys // Proc. 32. ACM Symposium on Theory of Computing . - 2000. - S. 343-350 . — ISBN 1-58113-184-4 . - doi : 10.1145/335305.335345 .
Tutte WT Antisymmetriset digrafit // Canadian Journal of Mathematics. - 1967. - T. 19 . — S. 1101–1117 . - doi : 10.4153/CJM-1967-101-8 .
Thomas Zaslavsky. Signed graphs // Discrete Applied Mathematics. - 1982. - T. 4 . — s. 47–74 . - doi : 10.1016/0166-218X(82)90033-6 .
Thomas Zaslavsky. Merkittyjen graafien suuntaus // European Journal of Combinatorics. - 1991. - T. 12 . - S. 361-375 . - doi : 10.1016/s0195-6698(13)80118-7 .
Bohdan Zelinka. Napakuvaajat ja rautatieliikenne // Aplikace Matematicy. - 1974. - T. 19 . - S. 169-176 .
Bohdan Zelinka. Polaaristen ja polarisoitujen graafien isomorfismit // Czechoslovak Mathematical Journal. – 1976a. - T. 26 . — S. 339–351 .
Bohdan Zelinka. Mengerin lauseen analogia polaarisille ja polarisoiduille kaavioille // Czechoslovak Mathematical Journal. – 1976b. - T. 26 . — S. 352–360 .