Viivadiagrammi

Graafiteoriassa suuntaamattoman graafin G viivagraafi L ( G ) on graafi L ( G ), joka edustaa graafin G reunojen lähialuetta .

Tietyn graafin viivakaavion käsite on niin luonnollinen, että monet kirjoittajat ovat ottaneet sen käyttöön itsenäisesti. Tietenkin jokainen heistä antoi oman nimensä: Ore [1] kutsui tätä graafia "naapurigraafiksi" , Sabidussi [2] - "johdannaiskaavio" , Beinecke [3] - "johdannaiskaavio" , Sechu ja Read [4] - "edge -vertex-dual" , Castelein [5] - "covering graph" , Menon [6] - "adjoint" ("adjoint") [7] [8] [9] .

Yksi varhaisimmista ja tärkeimmistä viivagraafiteoreemoista johtuu Whitneystä, joka osoitti, että yhtä poikkeusta lukuun ottamatta graafin G rakenne on täysin viivagraafin määrittelemä. Toisin sanoen, yhtä poikkeusta lukuun ottamatta, koko graafi voidaan rekonstruoida viivakaaviosta.

Muodollinen määritelmä

Olkoon graafi G annettu , jolloin sen viivagraafi L ( G ) on sellainen graafi, että

Esimerkkejä

Rakenneesimerkki

Seuraavassa kuvassa on graafi (vasemmalla, sinisillä pisteillä) ja sen viivakaavio (oikealla, vihreillä pisteillä). Viivagraafin jokainen kärki on merkitty alkuperäisen graafin vastaavan reunan kärkinumeroiden parilla. Esimerkiksi oikealla oleva vihreä piste, joka on merkitty numerolla 1,3, vastaa vasemmalla olevaa sinisten pisteiden 1 ja 3 välistä reunaa. Vihreä kärki 1,3 on kolmen muun vihreän kärjen vieressä: 1,4, 1,2 ( vastaavat reunoja, joilla on yhteinen kärki 1 sinisessä graafissa) ja 4,3 (vastaa reunoja, joilla on yhteinen kärki 3 sinisessä graafissa).

Sointukaaviot

Täydellisen graafin K n viivakaavio tunnetaan sointugraafina (tai kolmiomittaisena graafina ). Tärkeä lause sointukuvaajista on lause, jonka mukaan sointukuvaajalle on tunnusomaista spektri , paitsi n = 8, kun on kolme muuta kuvaajaa, joilla on sama spektri kuin L ( K 8 ). Poikkeukset on selitetty kohdassa Kuvaajan vaihto .

Kuperan polyhedran viivakaaviot

Viivakaavioiden esimerkkien lähde löytyy kohdasta geometria - yksinkertaisten polytooppien kuvaajille . Jos rakennamme viivakaavion tetraedrigraafille , saamme oktaedrigraafin . Kuution kuvaajasta saadaan kuutioktaedrin kuvaaja . Dodekaedrin kuvaajasta saadaan ikosidodekaedrin kuvaaja jne . Geometrisesti operaatiossa leikataan kaikki monitahoisen kärjet pois tasolla, joka leikkaa kaikki niiden keskellä olevaan kärkeen konjugoidut reunat.

Jos monitahoinen ei ole yksinkertainen (eli sillä on enemmän kuin kolme pintaa kärkeä kohti), viivakaavio ei ole tasomainen.

Mediaanikaavio

Mediaanikuvaaja on muunnelma tasograafin viivakaaviosta. Keskimmäisessä graafissa kaksi kärkeä ovat vierekkäin silloin ja vain, jos alkuperäisen graafin vastaavat reunat ovat tasograafin jonkin alueen kaksi peräkkäistä reunaa. Yksinkertaisten polygonien mediaanikuvaaja ja viivakaavio ovat samat, mutta monimutkaisissa polygoneissa mediaanikuvaaja pysyy tasaisena. Siten kuution ja oktaedrin keskimmäiset graafit ovat isomorfisia kuutioktaedrin graafin kanssa ja dodekaedrin ja ikosaedrin keskimmäiset graafit ovat isomorfisia ikosidodekaedrin graafin kanssa.

Ominaisuudet

Graafin G ominaisuudet, jotka riippuvat vain reunojen viereisyydestä, voidaan kääntää graafin L ( G ) vastaaviksi ominaisuuksiksi, jotka riippuvat vain kärkien viereisyydestä. Esimerkiksi yhteensopivuus G :ssä  on joukko kaaria, joista mikään ei ole vierekkäinen, ja vastaava joukko L: ssä ( G ) olevia pisteitä, joista mikään ei ole toisen vieressä, eli riippumaton joukko kärjet .

Niin,

Koska maksimiyhteensopivuus löytyy polynomiajasta, viivagraafin suurin riippumaton joukko löytyy myös polynomiajassa, vaikka sellaisen joukon löytäminen yleisemmille graafiperheille on vaikeaa.

Ominaisuudet ja tunnustus

Graafi G on jonkin toisen graafin viivakaavio silloin ja vain, jos G :stä on mahdollista löytää joukko klikkejä , jotka jakavat G:n kaaret siten , että kukin G :n kärki kuuluu täsmälleen kahdelle klikkille. Saattaa käydä niin, että tämän saavuttamiseksi on tarpeen valita yksittäisiä huippuja klikeissä. Whitneyn lauseen [ 10] [11] mukaan, jos G ei ole kolmio, tällaista osiota voi olla vain yksi. Jos osio on olemassa, voimme rakentaa graafin, jolle G on viivagraafi, luomalla kullekin klikkille kärkipiste ja yhdistämällä tuloksena olevat pisteet reunaan, jos kärki kuuluu molemmille klikkeille. Siten, lukuun ottamatta ja , jos kaksi viivakaaviota kytketty graafit ovat isomorfisia , niin kaaviot ovat myös isomorfisia. Roussopoulos [12] käytti tätä havaintoa perustana aikalineaariselle algoritmille viivakaavioiden tunnistamiseksi ja niiden alkuperäisten graafien rekonstruoimiseksi.  

Tällaista ominaisuutta voidaan käyttää esimerkiksi osoittamaan, että seuraava kaavio ei ole viivakaavio:

Tässä esimerkissä 4. asteen keskipisteestä ylöspäin, vasemmalle ja oikealle menevät reunat eivät sisällä yhteisiä klikkejä. Joten minkä tahansa graafin reunojen osion klikeiksi tulee sisältää vähintään yksi klikki jokaista näistä kolmesta reunasta, ja kaikki kolme klikkaa leikkaavat keskipisteessä, mikä rikkoo ehtoa, että kukin kärki kuuluu täsmälleen kahdelle klikkille. Näin ollen esitetty kaavio ei voi olla viivakaavio.

Toisen graafin ominaisuuden osoitti Beinecke [13] (ja mainitsi aiemmin ilman todistetta [3] ). Hän osoitti, että on yhdeksän minimaalista epäsuoraa kuvaajaa siten, että mikä tahansa ei-viivainen kaavio sisältää yhden näistä yhdeksästä kaaviosta generoituna aligraafina . Siten graafi on viivagraafi, jos ja vain jos mikään kärkien osajoukko ei luo yhtä näistä yhdeksästä. Yllä olevassa esimerkissä neljä ylintä kärkeä luovat kynnen ( eli täydellisen kaksiosaisen graafin K 1,3 ), joka näkyy kielletyn aligraafin kuvan vasemmassa yläkulmassa. Siten Beinecken ominaisuuden mukaan tämä graafi ei voi olla viivakaavio. Graafeille, joiden kärkiaste on vähintään 5, kuvaajan avulla voidaan generoida vain kuusi aligraafia kuvan vasemmassa ja oikeassa sarakkeessa [14] . Tämä tulos on samanlainen kuin hypergraafiviivakaavioiden tulos [15] .

Viivakaavion muodostamisoperaation toisto

Ruij ja Wilf [16] tarkastelivat graafien sekvenssiä

He osoittivat, että yhdistetyn graafin G äärelliselle graafille vain neljä tämän sekvenssin käyttäytymistä on mahdollista:

Jos G on irrotettu, tämä luokitus koskee jokaista G :n kytkettyä komponenttia .

Suhde muihin kaavioperheisiin

Mikään viivakaavio ei sisällä kynsiä .

Kaksiosaisen graafin viivakaavio on täydellinen ( katso Königin lause ). Kaksiosaisten graafien viivakaaviot muodostavat yhden tärkeimmistä rakennuspalikoista, joita käytetään täydellisen graafisen lauseen todistamiseen. Erikoistapauksia ovat tornikuvaajat , täydellisten kaksiosaisten graafien viivakaaviot .

Yleistykset

Multigraphs

Graafin G viivagraafin käsite voidaan luonnollisesti laajentaa tapaukseen, jossa G on multigrafi, vaikka tässä tapauksessa Whitneyn ainutlaatuisuuslause ei kelpaa. Esimerkiksi täydellisellä kaksiosaisella graafilla K 1, n on sama viivagraafi kuin dipoligraafilla ja Shannon-multigrafilla , jossa on sama määrä reunoja.

Reunan digrafit

Viivakaaviot voidaan myös yleistää suunnatuiksi graafisiksi [17] . Jos G  on suunnattu graafi, niin sen suunnatulla viivakuvaajalla tai viivadigraafilla on yksi kärki kullekin G :n kaarelle . Kaksi kärkeä, jotka vastaavat kaaria u :sta v :ään ja w :stä x :ään graafista G on yhdistetty kaarella uv :sta wx :ään viivadigraafissa, kun v = w . Siten jokainen kaari viivadigrafissa vastaa polkua, jonka pituus on 2 alkuperäisessä kaaviossa. De Bruijn -graafit voidaan saada rakentamalla toistuvasti suunnattuja viivakaavioita, alkaen täydellisestä digraafista [18] .

Painotetut viivakaaviot

Jokainen k - asteen kärki alkuperäisessä graafissa G luo k(k-1)/2 reunaa viivagraafiin L ( G ). Monenlaisessa analyysissä tämä tarkoittaa, että G :n korkean asteen kärjet ovat vahvemmin edustettuina viivakaaviossa L ( G ). Kuvittele esimerkiksi satunnainen kävely alkuperäisen graafin G kärkien yli . Kuljemme pitkin reunaa e jollain todennäköisyydellä f . Toisaalta reuna e vastaa yhtä kärkeä, vaikkapa v viivagraafissa L ( G ). Jos nyt suoritetaan samanlainen satunnainen kävely viivakaavion kärkien yli, käyntitaajuus v voi osoittautua aivan erilaiseksi kuin f . Jos G :n reunamme e olisi yhdistetty O(k) asteen pisteisiin , se kulkisi O(k 2 ) useammin viivagraafissa L ( G ). Siten vaikka Whitneyn lause [10] takaa, että viivakaavio sisältää lähes aina G :n koodatun topologian , se ei takaa, että kahdella graafilla on yksinkertaiset dynaamiset yhteydet. Yksi ratkaisu tähän ongelmaan on luoda painotettu viivagraafi, eli viivagraafi, jonka reunat on painotettu. On olemassa useita luonnollisia tapoja tehdä tämä [19] . Jos esimerkiksi graafin G reunat d ja e ovat konjugoituja k -asteen kärjessä v , niin viivagraafissa L ( G ) kahta kärkeä d ja e yhdistävälle reunalle voidaan antaa painoarvo 1/(k- 1) . Samalla tavalla minkä tahansa G :n reunan (ellei se ole kytketty asteen 1 kärkeen ) paino 2 viivagraafissa L ( G ), joka vastaa G:n reunan kahta päätä .

Hypergraafien viivakaaviot

Hypergrafin reunat voivat muodostaa minkä tahansa joukkoperheen, joten hypergraafin viivakaavio  on sama kuin perheen joukkojen leikkauskuvaaja .

Muistiinpanot

  1. ↑ O. Malmi. Hamiltonin kytketyt graafit // J. Math. Pures Appl. - 1963. - T. 42 . - S. 21-27 .
  2. ↑ G. Sabidussi. Graafit tietyllä ryhmällä ja annetuilla praph-teoreettisilla ominaisuuksilla  // Canad. J Math. - 1957. - T. 9 . - S. 515-525 .
  3. ↑ 1 2 L. W. Beineke. Beitrage zur Graphentheorie. - Leipzig: Teubner, 1968.
  4. ↑ Seshu S., Reed M. Lineaariset graafit ja sähköpiirit. - M . : Higher School, 1971. - T. 42. - S. 21-27.
  5. ↑ Kasteleyn P. W. Liukeneva itsestään välttävä kävelyongelma // Physica. - 1968. - T. 23 . - S. 85-89 .
  6. ↑ Menon V. Toistuvista vaihtokaavioista // Amer Math Monthly. - 1966. - T. 13 . - S. 986-989 .
  7. ↑ F. Harari . Graph Theory = Graph Theory / Käännös englannista ja esipuhe V.P. Kozyrev. - 2. - M. : Pääkirjoitus URSS, 2003. - 296 s.
  8. ↑ Balakrishnan VK Schaumin graafisen teorian pääpiirteet. – 1. - McGraw-Hill, 1997. - ISBN 0-07-005489-4 .
  9. ↑ R.L. Hemminger, L.W. Beineke. Valitut aiheet graafiteoriassa. - Academic Press Inc., 1978. - S. 271-305 .
  10. ↑ 1 2 H. Whitney. Yhdenmukaiset graafit ja graafien liitettävyys  // American Journal of Mathematics. - 1932. - T. 54 , no. 1 . - S. 150-168 . - doi : 10.2307/2371086 . — .
  11. ↑ J. Krausz. Demonstration nouvelle d'un théorème de Whitney sur les réseaux // Mat. Fiz. Lapok. - 1943. - T. 50 . - S. 75-85 .
  12. ↑ N.D. Roussopoulos. Max { m , n } -algoritmi graafin H määrittämiseksi sen viivakaaviosta G  // Tietojenkäsittelykirjaimet. - 1973. - Osa 2 , numero. 4 . - S. 108-112 . - doi : 10.1016/0020-0190(73)90029-X .
  13. ↑ LW Beineke. Johdettujen graafien karakterisoinnit // Journal of Combinatorial Theory. - 1970. - Voi. 9. - S. 129-135 . - doi : 10.1016/S0021-9800(70)80019-9 .
  14. ↑ Juri Metelsky, Regina Tyshkevich. Lineaaristen 3-uniformisten hypergraafien viivakaaviot // Journal of Graph Theory. - 1997. - T. 25 , no. 4 . - S. 243-251 . - doi : 10.1002/(SICI)1097-0118(199708)25:4<243::AID-JGT1>3.0.CO;2-K .
  15. ↑ Weisstein, Eric W. Line Graph  Wolfram MathWorld -verkkosivustolla .
  16. ↑ ACM van Rooij, H. S. Wilf. Äärillisen graafin vaihtograafi // Acta Mathematica Hungarica. - 1965. - T. 16 , no. 3-4 . - S. 263-269 . - doi : 10.1007/BF01904834 .
  17. ↑ Frank Harary, RZ Norman. Joitakin viivadigrafien ominaisuuksia // Rendiconti del Circolo Matematico di Palermo . - 1960. - T. 9 , no. 2 . - S. 161-169 . - doi : 10.1007/BF02854581 .
  18. ↑ Fu Ji Zhang, Guo Ning Lin. De Bruijn – Hyviä kaavioita // Acta Math. Sinica. - 1987. - T. 30 , no. 2 . - S. 195-205 .
  19. ↑ T. S. Evans, R. Lambiotte. Viivakaaviot, linkkien osiot ja päällekkäiset yhteisöt // Phys.Rev.E. - 2009. - T. 80 . - doi : 10.1103/PhysRevE.80.016105 .

Linkit