Tælle grad

Graden k (skrevet G k ) af en urettet graf G er en anden graf, der har det samme sæt af toppunkter , og to toppunkter på denne graf er tilstødende, hvis afstanden mellem disse toppunkter i den oprindelige graf G ikke overstiger k . For at angive graden af ​​en graf bruges terminologi svarende til talpotenser - G 2 kaldes kvadratet af grafen G , G 3 kaldes terningen [1] .

Graden af ​​en graf skal ikke forveksles med multiplikationen af ​​en graf af sig selv, som (i modsætning til graden af ​​en graf) generelt har mange flere hjørner end den oprindelige graf.

Egenskaber

Hvis diameteren af ​​en graf er d , så er dens d -te grad en komplet graf [2] . Hvis en familie af grafer har en afgrænset klikbredde , så gælder det samme for de d -te potenser af graferne for familien for enhver fast d [3] .

Farvelægningsside

Graffirkantfarvning kan bruges til at tildele frekvenser til medlemmer af det trådløse netværk på en sådan måde, at ikke to medlemmer forstyrrer hinanden og andre fælles naboer [4] , samt til at finde en grafisk repræsentation af grafer med høj vinkelopløsning [5 ] .

Både det kromatiske tal og degenerationen af ​​den kth grad af en plan graf med maksimal toppunktsgrad Δ er lig med , hvor degenerationsbundet viser, at man kan bruge den grådige farvealgoritme til at farve grafen med det antal farver [4] . I tilfælde af en kvadratisk plan graf formodede Wegner i 1977, at det kromatiske tal for en sådan graf ikke overstiger , og det er i øjeblikket kendt, at det kromatiske tal ikke overstiger [6] [7] . Mere generelt, for enhver graf med degeneration d og maksimal grad Δ, er kvadratdegenerationen af ​​grafen O ( d Δ), således at mange slags sparsomme grafer , bortset fra plane grafer, også har et kvadratisk kromatisk tal proportionalt med Δ.

Selvom det kromatiske tal for en kvadrat af en ikke-plan graf med maksimal grad Δ kan være proportional med Δ 2 i værste fald , er det mindre for grafer med stor omkreds og er begrænset til O(Δ 2 /log Δ) [8] i denne sag .

Problemet med at bestemme minimumsantallet af farver til farvning af en kvadratisk graf er NP-svært selv for det plane tilfælde [9]

Hamiltonian

Terningen af ​​enhver forbundet graf indeholder nødvendigvis en Hamilton-cyklus [10] . Kvadratet af en forbundet graf vil ikke nødvendigvis indeholde en Hamilton-cyklus, og problemet med at bestemme, at en sådan cyklus er indeholdt i et kvadrat, er NP-komplet [11] . Men ifølge Fleischners sætning er kvadratet af en toppunkt-2-forbundet graf altid Hamiltonsk [12] .

Beregningsmæssig kompleksitet

Graden k af en graf med n toppunkter og m kanter kan fås i O( mn ) tid ved at anvende bredde-først søgning , som udføres på hvert hjørne af grafen for at finde afstandene til alle andre toppunkter. Alternativt, hvis A er tilstødende matrix af grafen modificeret på en sådan måde, at der ikke er nogen nul-elementer på hoveddiagonalen, så giver de ikke-nul-elementer af matricen A k tilstødende matrix af den k - te grad af graf [13] , hvilket indebærer, at konstruktionen af ​​grafens k -te grad kan udføres i en tid svarende, op til en logaritmisk faktor, til tidspunktet for matrixmultiplikation .

Givet en graf er det et NP-komplet problem at bestemme, om det er en kvadrat af en anden graf [14] . Desuden er det et NP-komplet problem at afgøre, om en graf er den k'te potens af en anden graf for et givet tal k  ≥ 2, og også om det er den k'te potens af en todelt graf for k  > 2 [15] .

Genererede undergrafer

En semi-square af en todelt graf G er en undergraf af grafen G 2 genereret af en del af grafen G . Kortgrafer er halvkvadrater af plane grafer [16] , halverede terninggrafer er halvkvadrater af hyperkubegrafer [17] .

Grader af blade er undergrafer over grader af træer genereret af blade af træer [18] .

Noter

  1. ↑ Bondy, Murty, 2008 , s. 82.
  2. ↑ Weisstein, Eric W. Graph Power  på Wolfram MathWorld -webstedet .
  3. ↑ Todinca, 2003 , s. 370-382.
  4. ↑ 1 2 Agnarsson, Halldorsson, 2000 , s. 654-662.
  5. ↑ Formann, Hagerup, Haralambides et al., 1993 , s. 1035-1052.
  6. ↑ F. & H. Kramer, 2008 , s. 422-426.
  7. ↑ Molloy, Salavatipour, 2005 , s. 189-213.
  8. ↑ Alon, Mohar, 2002 , s. 1-10.
  9. ↑ Agnarsson og Halldórsson ( Agnarsson, Halldórsson 2000 ) lister i deres publikation papirbeviser for NP-hårdhed i tilfælde af generelle grafer (artikler af McCormick (1983) og artikler af Lin og Skiena (Lin, Skiena, 1995)), og for plane grafer (artikler af Ramanathan og Lloyd (Ramanathan, Lloyd, 1992-1993)).
  10. ↑ Bondy, Murty, 2008 , s. 105.
  11. ↑ Underground, 1978 , s. 323.
  12. ↑ Diestel, 2012 .
  13. ↑ Hammack, Imrich, Klavžar, 2011 .
  14. ↑ Motwani, Sudan, 1994 , s. 81-88.
  15. ↑ Le, Nguyen, 2010 , s. 238-249.
  16. ↑ Chen, Grigni, Papadimitriou, 2002 , s. 127-138.
  17. ↑ Shpektorov, 1993 .
  18. ↑ Nishimura, Ragde, Thilikos, 2002 , s. 69-108.

Litteratur