Faktorgraf
En kvotientgraf Q af en graf G er en graf, hvis toppunkter er partitionsblokke af toppunkterne på grafen G , og en blok B støder op til en blok C , hvis et eller andet toppunkt i B støder op til et toppunkt i C [1] . Med andre ord, hvis G har et kantsæt E og et sæt toppunkter V og R er en ækvivalensrelation genereret af en partition, så har kvotientgrafen et sæt toppunkter V / R og et kantsæt .
![{\displaystyle \{([u]_{R},[v]_{R})\midt (u,v)\i E(G)\))](https://wikimedia.org/api/rest_v1/media/math/render/svg/186432536c2647b3543b553b1043167267e285a5)
Mere formelt er en kvotientgraf et kvotientobjekt i kategorien grafer . Kategorien af grafer er øjeblikkelig — kortlægningen af en graf til dens toppunktsæt gør den til en konkret kategori , så dens objekter kan opfattes som "sæt med yderligere struktur", og kvotientgrafen svarer til grafen genereret på kvotienten sæt V / R ved sit toppunkt sæt V . Så er der en grafhomomorfi ( kvotientmapping ) fra en graf til en kvotientgraf, der afbilder hver toppunkt eller kant til den ækvivalensklasse, den tilhører . Intuitivt svarer dette til at "lime" (formelt "identificere") grafens spidser og kanter.
Eksempler
En graf er trivielt en faktorgraf for sig selv (hver partitionsblok er et separat toppunkt), og en graf bestående af et enkelt punkt er en faktorgraf for enhver ikke-tom graf (partitionen består af en blok, der indeholder alle toppunkter). Den enkleste ikke-trivielle kvotientgraf fås ved at lime to spidser (vertex identification ), men hvis to spidser støder op til hinanden, kaldes dette kantkontraktion .
Særlige typer faktorgrafer
Kondensationen af en rettet graf er en kvotientgraf, når de stærkt forbundne komponenter danner partitionsblokke. Denne konstruktion kan bruges til at opnå en rettet acyklisk graf fra enhver rettet graf [2] .
Resultatet af en eller flere kantkontraktioner i en ikke-rettet graf G er en kvotientgraf af G , hvor blokkene er de forbundne komponenter af subgrafen af G dannet af kantkontraktionen. Partitionsblokkene, der fører til en kvotientgraf, danner dog ikke nødvendigvis forbundne undergrafer.
Hvis G er en dækkende graf for en anden graf H , så er H en kvotientgraf for G. Blokkene i den tilsvarende partition er de omvendte billeder af hjørnerne af H under den dækkende kortlægning. Dækkende kortlægninger har dog yderligere krav, som generelt ikke er opfyldt for kvotientgrafer, nemlig at kortlægningen er en lokal isomorfi [3] .
Ofte, især når man arbejder med periodiske grafer , betragter man faktorgrafer, hvis toppunkter svarer til kredsløbene for toppunkterne på den oprindelige graf under påvirkning af grafautomorfigruppen (eller nogle af dens undergrupper).
Beregningsmæssig kompleksitet
Givet en n -vertex kubisk graf G og en parameter k , er det et NP-komplet problem at bestemme om graf G kan opnås som en kvotientgraf af en plan graf med n + k toppunkter [4] .
Noter
- ↑ Sanders, Schulz, 2013 , s. 1-17.
- ↑ Bloem, Gabow, Somenzi, 2006 , s. 37-56.
- ↑ Gardiner, 1974 , s. 255-273.
- ↑ Faria, de Figueiredo, Mendonça, 2001 , s. 65-83.
Litteratur
- Peter Sanders, Christian Schulz. Grafopdeling af høj kvalitet // Grafopdeling og grafklynger. — Amer. Matematik. Soc., Providence, RI, 2013, bind 588, s. 1-17. - (Kontempl. Matematik.). - doi : 10.1090/conm/588/11700 .
- Roderick Bloem, Harold N. Gabow, Fabio Somenzi. En algoritme til stærkt forbundet komponentanalyse i n log n symbolske trin // Formelle metoder i systemdesign. - 2006. - Januar ( bind 28 , hæfte 1 ). — s. 37–56 . - doi : 10.1007/s10703-006-4341-z .
- Gardiner A. Antipodale dækkende grafer // Journal of Combinatorial Theory. - 1974. - T. 16 . — S. 255–273 . - doi : 10.1016/0095-8956(74)90072-0 .
- Faria L., de Figueiredo CMH, Mendonça CFX Opdelingsnummer er NP-komplet // Diskret anvendt matematik . - 2001. - T. 108 , no. 1-2 . — s. 65–83 . - doi : 10.1016/S0166-218X(00)00220-1 .