Prismakuvaaja

Graafiteoriassa prismagraafi on graafi , jonka yksi prismoista on luuranko.

Esimerkkejä

Yksittäiset kaaviot voidaan nimetä niihin liittyvien kappaleiden mukaan:


Y 3 = GP(3,1)
Y 4 \ u003d Q 3 \u003d GP (4,1)
Y 5 = GP(5,1)
Y 6 = GP(6,1)
Y 7 = GP(7,1)
Y8 = GP (8,1)

Vaikka geometrisesti stelloidut monikulmiot toimivat myös toisen (itseleikkaavan ja ei-kuperan) prismaattisten polytooppien sekvenssin pinnoina, näiden tähtitettyjen prismojen graafit ovat isomorfisia prismagraafien kanssa eivätkä muodosta erillistä kuvasarjaa.

Rakentaminen

Prismagraafit ovat esimerkkejä yleistetyistä Petersen-graafista parametreilla GP( n ,1). Graafit voidaan muodostaa myös syklin ja yksikköreunan suorana tulona [1] .

Kuten monet vertex-transitiiviset graafit, prismaattiset graafit voidaan rakentaa Cayley-graafina . N: n kertaluvun dihedraaliryhmä on säännöllisen n -gonin symmetriaryhmä tasossa. Se vaikuttaa n - kulmaan kiertojen ja heijastusten avulla. Ryhmä voidaan muodostaa kahdella elementillä, kulman kierrolla ja yhdellä heijastuksella, ja tämän ryhmän Cayley-graafi tällä generointijoukolla on prismagraafi. Tiivistetysti ryhmällä on tehtävä (missä r on rotaatio ja f on heijastus) ja Cayley-graafin generaattoreina on r ja f (tai r , r −1 ja f ) [1]

Parittoman n : n n - kulmaisen prisman kuvaaja voidaan muodostaa kiertokaaviona , mutta tämä konstruktio ei toimi parillisilla n: n arvoilla [1] .

Ominaisuudet

N - kulmaisen prisman graafissa on 2n kärkeä ja 3n reunaa. Kaaviot ovat säännöllisiä kuutiokaavioita . Koska prismoissa on symmetrioita, jotka vievät minkä tahansa kärjen mihin tahansa toiseen, prismagraafit ovat kärkitransitiivisia grafiikoita . Koska nämä graafit ovat monitahoisia , ne ovat myös vertex-3-liitettyjä tasokaavioita . Jokaisella prismagraafilla on Hamiltonin sykli [2] .

Kaikista kaksinkertaisesti kytketyistä kuutiograafista prismagraafit sisältävät vakiokertoimeen asti suurimman mahdollisen määrän graafin 1-hajoja . 1-hajotelma on graafin reunan osio, joka on asetettu kolmeen täydelliseen yhteensovitukseen, tai vastaavasti graafin kolmivärinen reunavärjäys . Jokaisella kaksikytketyllä kuutiograafilla, jossa on n kärkeä, on O (2 n /2 ) 1-hajoja, ja prismagraafissa on Ω (2 n /2 ) 1-hajoja [3] .

N -kulmaisen prisman kuvaajan virittävien puiden lukumäärä saadaan kaavasta [4] .

Jos n = 3, 4, 5, ... nämä luvut ovat yhtä suuret

78, 388, 1810, 8106, 35294, ...

Parillisen n : n n -kulmaisen prisman kuvaajat ovat osittaisia ​​kuutioita . Ne muodostavat yhden harvoista tunnetuista äärettömistä kuutioisten osittaiskuutiograafien perheistä, ja ne ovat (neljää poikkeusta lukuun ottamatta) ainoat huipputransitiiviset kuutioosittaiskuutiot [5] .

Viisikulmainen prismagraafi on yksi kielletyistä alaväreistä graafille , jonka puunleveys on kolme [6] . Kolmioprisma- ja kuutiograafien puun leveys on tasan kolme, mutta kaikissa suuremmissa prismoissa puun leveys on neljä.

Aiheeseen liittyvät kaaviot

Muita säännöllisiin kantapolyhedriin perustuvia loputtomia monitahograafisia perheitä ovat antiprismakuvaajat ja -pyörät pyramidigraafit ). Muita vertex-transitiivisia monitahoisia kuvaajia ovat Archimedean graafit .

Jos prismaattisen graafin kaksi sykliä murretaan poistamalla yksi reuna molemmissa jaksoissa samasta paikasta, saadaan tikkaat . Jos kaksi poistettua reunaa korvataan kahdella risteävällä reunalla, saadaan ei-tasograafi " Möbius-ladder " [7] .

Muistiinpanot

  1. ↑ 1 2 3 Weisstein, Eric W. Prismakaavio  (englanniksi) Wolfram MathWorld -verkkosivustolla .
  2. ↑ Lue, Wilson, 2004 , s. 261, 270.
  3. ↑ Eppstein, 2013 . Eppstein uskoo havainnon, että prismagraafit sisältävät lähes maksimimäärän 1-hajoja, Greg Kuperbergin ansioksi , joka teki tämän havainnon yksityisesti.
  4. ↑ Jagers, 1988 , s. 151-154.
  5. ↑ Mark, 2015 .
  6. ↑ Arnborg, Proskurowski, Corneil, 1990 , s. 1–19.
  7. ↑ Guy, Harary, 1967 , s. 493–496.

Kirjallisuus