Dubbel täckning av en tvådelad graf

Den tvådelade dubbla täckningen av en oriktad graf G är den tvådelade täckande grafen för G med dubbelt så många hörn som G . Omslaget kan konstrueras som en tensorprodukt av grafer , G × K 2 . Detta omslag kallas även Kronecker-dubbeltäcket eller det kanoniska dubbeltäcket på grafen G.

Denna täckning bör inte förväxlas med den dubbla cykeltäckningen av en graf, en familj av cykler som inkluderar varje kant två gånger.

Byggnad

Ett tvådelat dubbelhölje av G har två hörn u i och w i för varje vertex vi i G . Två hörn u i och w j är förbundna med en kant i det dubbla locket om och endast om v i och v j är förbundna med en kant i G . Till exempel, nedan är en ritning av ett tvådelat dubbelt omslag av en icke-tvådelad graf H . I illustrationen visas varje vertex i tensorprodukten i färg från den första faktorn ( H ) och formen på vertexen är hämtad från den andra faktorn ( K 2 ). Således visas topparna u i i det dubbla omslaget som cirklar, och hörnen w i visas som kvadrater.

Ett tvådelat dubbelhölje kan också konstrueras med hjälp av närliggande matriser (som beskrivs nedan) eller som en härledd spänningsgraf där varje kant av G är märkt med element som inte är noll i tvåelementsgruppen .

Exempel

Den tvådelade dubbla täckningen av Petersen -grafen är Desargues-grafen — K 2 × G (5,2)= G (10,3).

Den tvådelade dubbla omslaget till den fullständiga grafen K n är kronan ( den fullständiga tvådelade grafen K n , n minus den perfekta matchningen ). I synnerhet är det tvådelade dubbla höljet av tetraedergrafen , K 4 , kubgrafen .

Det tvådelade dubbla omslaget för en cykel med udda längd är en cykel som är dubbelt så lång, medan den tvådelade dubbla omslaget för en tvådelad graf (i synnerhet den jämna cykeln som visas i figuren) bildas av två kopior av den ursprungliga grafen .

Matristolkning

Om en oriktad graf G har matris A som sin närliggande matris , så är närliggande matris för det tvådelade dubbelhöljet av graf G

och biadjacency-matrisen av det dubbla höljet G är själva matrisen A . Det vill säga att omvandla en graf till dess dubbla täckning kan göras helt enkelt genom att tolka A som en bis-adjacency-matris snarare än en adjacency-matris. Mer generellt ger tolkningen av närliggande matriser för riktade grafer som bisadjacent matriser en kombinatorisk ekvivalens mellan riktade grafer och balanserade tvådelade grafer [1] [2] .

Egenskaper

Den tvådelade dubbla täckningen av en graf G är en tvådelad graf . Båda delarna av en tvådelad graf har en vertex för varje vertex av G . En tvådelad dubbelkåpa ansluts om och endast om G är ansluten och inte tvådelad [3] .

Tvådelat dubbeltäcke är ett specialfall av tvådelat täcke (2-faldig täckande graf . Dubbeltäckning i grafteori kan betraktas som ett specialfall av topologisk dubbeltäckning .

Om graf G inte är en tvådelad symmetrisk graf , är den tvådelade omslaget till G också en symmetrisk graf. Några välkända kubiska symmetriska grafer kan erhållas på detta sätt. Till exempel är det tvådelade omslaget till K 4 en kubgraf. Det dubbla höljet på Petersen-grafen är Desargues-grafen, och det dubbla höljet av dodekaedern är den symmetriska kubiska grafen med 40 vertex [4] .

Två olika grafer kan ha isomorfa tvådelade dubbla omslag. Till exempel är Desargues-grafen inte bara ett tvådelat dubbelt omslag av Petersen-grafen, utan också ett tvådelat dubbelt omslag av en annan graf som inte är isomorft med Petersen-grafen [5] . Inte varje tvådelad graf är en tvådelad dubbel täckning av en annan graf. För att en tvådelad graf G ska vara en tvådelad täckning av en annan graf, är det nödvändigt och tillräckligt att automorfismerna i grafen G inkluderar en involution som mappar varje vertex till en annan icke-angränsande vertex [5] . Till exempel är en graf med två hörn och en kant tvådelad, men inte en tvådelad dubbeltäckning, eftersom den inte innehåller icke-intilliggande hörnpar som kan mappas till varandra genom en sådan involution. Å andra sidan är kubgrafen ett tvådelat dubbelt omslag och har en involution som mappar varje vertex till en diametralt motsatt vertex. En alternativ beskrivning av tvådelade grafer som kan bildas genom att konstruera ett tvådelat dubbelt omslag erhölls av Sampatkumar [6] .

Andra dubbla omslag

I allmänhet kan en graf ha flera andra dubbla omslag än ett dubbelt dubbelt omslag [7] . I figuren är graf C en dubbel täckning av graf H :

  1. Grafen C är en täckande graf över grafen H — det finns en surjektiv lokal isomorfism f från C till H , visad i färger i figuren. Till exempel mappar f båda blå hörn från C till den blå hörn i H . Dessutom, låt X vara grannskapet till den blå vertexen i C och låt Y vara grannskapet till den blå vertexen i H . Då är begränsningen av f till X en bijektion från X till Y . I synnerhet är graderna för var och en av de blå hörnen lika. Detsamma gäller vilken färg som helst.
  2. Graf C är ett dubbelt omslag (eller ett dubbelt omslag ) av H - den omvända bilden av varje vertex i H har storlek 2. Till exempel finns det exakt 2 hörn i C som mappar till den blå hörn i H .

C är dock inte en tvådelad dubbel täckning av H eller någon annan graf. Grafen är inte en tvådelad graf.

Om vi ​​ersätter en triangel med en kvadrat i H , har den resulterande grafen fyra olika dubbla omslag. Två av dem är tvådelade, men bara en av dem är ett Kronecker-överdrag.

Som ett annat exempel är icosahedron -grafen en dubbel täckning av hela grafen K 6 . För att erhålla en täckande mappning från icosahedron-grafen till K 6 , mappa varje par av motsatta icosahedron-toppar till en vertex av K 6 . Emellertid är icosahedron inte tvådelad, så grafen för icosaedern är inte en tvådelad dubbel täckning av grafen K 6 . Istället kan ett tvådelat dubbelhölje erhållas som ett orienterbart dubbelt hölje av inbäddningen av grafen K 6 i det projektiva planet .

Anteckningar

  1. ↑ Dulmage, Mendelsohn, 1958 .
  2. ↑ Brualdi, Harary, Miller, 1980 .
  3. ↑ Brualdi, Harary, Miller, 1980 , sid. Sats 3.4.
  4. ↑ Feng, Kutnar, Malnič, Marušic, 2008 .
  5. ↑ 12 Imrich , Pisanski, 2008 .
  6. ↑ Sampathkumar, 1975 .
  7. ↑ Waller, 1976 .

Litteratur

Länkar