Cirkeldiagram

I grafteorin är en cirkelgraf en graf över skärningspunkterna för uppsättningen av ackord i en cirkel . Det vill säga, det är en oriktad graf vars hörn kan identifieras med cirkelns ackord, och dessa hörn ligger intill om och endast om motsvarande ackord skär varandra.

Algoritmisk komplexitet

Spinrad [1] presenterade en algoritm som körs i O( n 2 ) tid som testar om en given n -vertex oriktad graf är cirkulär, och om den är cirkulär, konstruerar en uppsättning ackord som ger en cirkulär graf.

Många andra problem som är NP-kompletta på allmänna grafer har polynomtidsalgoritmer, om de är begränsade till cirkelgrafer. Till exempel visade Klox [2] att trädbredden för en cirkulär graf kan bestämmas och det optimala nedbrytningsträdet konstrueras i O( n 3 ) tid. Dessutom kan den minsta ersättningen (det vill säga en kordalgraf med så få kanter som möjligt innehållande den givna cirkelgrafen som subgraf) hittas i O( n 3 ) tid [3] . Tiskin [4] visade att den största klicken av en cirkelgraf kan hittas i O( n log 2 n ) tid, och Nash och Gregg [5] visade att den största oberoende uppsättningen av en oviktad cirkelgraf kan hittas i O( n min{ d , α }), där d är en grafparameter känd som densiteten , och α är den cirkulära grafens oberoendenummer .

Ändå finns det problem som förblir NP-kompletta , även när de är begränsade till cirkeldiagram. Dessa uppgifter inkluderar att söka efter den dominerande uppsättningen , den minsta anslutna dominanta uppsättningen och den minsta totala dominanta uppsättningen [6] .

Kromatiskt nummer

Det kromatiska numret för en cirkelgraf är det minsta antalet färger som kan användas för att färga ackorden så att inga två korsande ackord har samma färg. Eftersom det är möjligt att bilda en cirkelgraf där ett godtyckligt stort antal ackord skär varandra, kan det kromatiska talet för en cirkelgraf vara godtyckligt stort, och att bestämma det kromatiska numret för en cirkelgraf är ett NP-komplett problem [8 ] . Ett NP-komplett problem är också att kontrollera om det är möjligt att färglägga en cirkulär graf med fyra färger [9] . Unger [10] hävdade att sökandet efter en färg med tre färger kan göras i polynomtid , men många detaljer saknas i beskrivningen av hans resultat [10] .

Vissa författare har studerat problem med att färga begränsade underklasser av cirkulära grafer med ett litet antal färger. I synnerhet cirkelgrafer, där det inte finns några uppsättningar av k eller fler ackord, där alla ackord skär varandra, kan färgas utan att överskrida färger [11] . Speciellt för k  = 3 (det vill säga för triangelfria cirkelgrafer ) överstiger inte det kromatiska talet fem, och denna gräns är skarp - alla triangelfria cirkelgrafer kan färgas med fem färger, och det finns triangel -fria cirkeldiagram som kräver fem färger för att färga [12] . Om en cirkelgraf har minst fem omkretsar (det vill säga att den inte innehåller trianglar och cykler med fyra hörn), kan den färgas med tre färger [ 13] . Problemet med att färglägga boxgrafer utan trianglar motsvarar problemet med att representera boxgrafer som en graf som är isometrisk för en direkt produkt av träd . I denna överensstämmelse av problem motsvarar antalet färger i färgningen antalet träd i produkten [14] .

Applikationer

Cirkeldiagram visas i VLSI- design som en abstraktion av ett specialfall av PCB-routing känt som "bipolär kanalövergångsrouting". I det här fallet är spårområdet en rektangel, alla nätverk är bipolära och ledningarna är placerade längs rektangelns omkrets. Det är lätt att se att skärningsgrafen för detta nätverk är en cirkelgraf [15] . Ett av målen med routing är att säkerställa att det inte finns någon elektrisk kontakt mellan olika nätverk och att eventuella överlappande delar ska ligga på olika lager. Cirkeldiagram fångar alltså en del av spårningsuppgifterna.

Färgningen av cirkelgrafer kan också användas för att hitta en bokinbäddning av godtyckliga grafer - om hörnen på en given graf G är placerade på en cirkel, och kanterna på grafen G bildar cirkelns ackord, då är grafen för skärningspunkterna mellan dessa ackord är en cirkelgraf, och färgläggning av denna cirkelgraf motsvarar en bokinbäddning som bevarar cirkelarrangemanget . I denna ekvivalens motsvarar antalet färger antalet sidor i en bokinlaga [16] .

Relaterade grafklasser

Skärningsgrafen för en uppsättning intervall på en linje kallas en intervallgraf .

En graf är cirkulär om och endast om det är en graf med reguljära intervall . Detta är grafer vars hörn motsvarar (öppna) linjesegment och två hörn är sammankopplade med en kant om två intervall har en icke-tom skärningspunkt. Inget intervall är dock helt inneslutet i ett annat intervall.

Stränggrafer , skärningsdiagram för kurvor i planet, inkluderar cirkeldiagram som ett specialfall.

Varje avståndsärvd graf är en cirkelgraf, liksom alla permutations- eller likgiltiga grafer . Varje ytterplanär graf är också cirkulär [17] [16] .

Anteckningar

  1. ↑ Spinrad, 1994 .
  2. ↑ Kloks, 1996 .
  3. ↑ Kloks, Kratsch, Wong, 1998 .
  4. ↑ Tiskin, 2010 .
  5. ↑ Nash, Gregg, 2010 .
  6. ↑ Keil, 1993 .
  7. ↑ Ageev, 1996 .
  8. ↑ Garey, Johnson, Miller, Papadimitriou, 1980 .
  9. ↑ Unger (1988) .
  10. ↑ 12 Unger , 1992 .
  11. ↑ Černý, 2007 . För tidigare gränser, se Gyárfás, 1985 , Kostochka, 1988 och Kostochka, Kratochvíl, 1997 .
  12. ↑ Se Kostochka, 1988 för den övre gränsen och Ageev, 1996 för grafer som når den nedre gränsen. Karapetyan ( Karapetyan 1984 ) och ( Gyárfás, Lehel 1985 ) har tidigare angett svagare gränser för samma problem.
  13. ↑ Ageev, 1999 .
  14. ↑ Bandelt, Chepoi, Eppstein, 2010 .
  15. ↑ Sherwani, 2000 .
  16. ↑ 12 Unger , 1988 .
  17. ↑ Wessel, Poschel, 1985 .

Litteratur

Länkar