Cirkel graf

I grafteori, en cirkel graf er skæringspunktet graf af et sæt af akkorder i en cirkel. Det vil sige, det er en ikke-orienteret graf, hvis hjørner kan være forbundet med akkorder i en cirkel, således at to knudepunkter støder op hvis og kun hvis de tilsvarende akkorder krydser hinanden.

Kompleksiteten af ​​algoritmen,

Spinrad giver en O-tid algoritme, der tester, om en given n-vertex-orienteret graf er en cirkel graf og, hvis det er, konstruerer et sæt af akkorder, der repræsenterer det.

En række andre problemer, der er NP-komplet på generelle grafer har polynomiel tid algoritmer, når begrænset til cirkel grafer. For eksempel viste Kloks at treewidth af en cirkel graf kan bestemmes, og en optimal træ nedbrydning konstrueret, i O tid. Derudover kan et minimum fill-in findes i O tid. Tiskin har vist, at en maksimal klike af en cirkel kurve kan findes i O tiden, mens Nash & amp; Gregg har vist, at der kan findes en maksimal uafhængigt sæt et uvægtet cirkel grafen i O tid, hvor d er en parameter af grafen kendt som dens tæthed, og α er antallet af cirklen grafen uafhængighed.

Men der er også problemer, der fortsat er NP-komplet, når begrænset til cirkel grafer. Disse omfatter den mindste dominerende sæt, minimum forbundet dominerende sæt, og minimum samlede dominerende sæt problemer.

Kromatisk nummer

Den kromatiske antal af en cirkel graf er det mindste antal af farver, der kan bruges til at farve sine akkorder, så ikke to krydsende akkorder har samme farve. Da det er muligt at danne cirkel grafer, hvor vilkårligt store sæt af akkorder alle krydser hinanden, kan den kromatiske antal af en cirkel graf vilkårligt store og fastlæggelse af kromatiske antal af en cirkel grafen NP-komplet. Det er fortsat NP-komplet at teste, om en cirkel graf kan farves med fire farver. Unger hævdede, at finde en farve med tre farver kan gøres i polynomiel tid, men hans writeup af dette resultat udelader mange detaljer.

Flere forfattere har undersøgt problemerne med farve begrænsede underklasser af cirkel grafer med få farver. Især for cirkel grafer, hvor der ikke sæt K eller flere akkorder alle krydser hinanden, er det muligt at farve grafen med så få som farver. I det særlige tilfælde, hvor K = 3 den kromatiske nummer er højst fem, og det er stramt: alle trekant-fri cirkel grafer kan være farvet med fem farver, og der eksisterer trekant-fri cirkel grafer, der kræver fem farver. Hvis en cirkel grafen har omkreds mindst fem kan være farvet med højst tre farver. Problemet med farvning trekant-fri squaregraphs svarer til problemet med at repræsentere squaregraphs som isometrisk subgraphs af Cartesiske produkter af træer; i denne korrespondance, antallet af farver i farve svarer til antallet af træer i produktet repræsentation.

Applikationer

Circle grafer opstå i VLSI fysiske design som en abstrakt repræsentation for en særlig sag for wire routing, kendt som "to-terminal switchbox routing". I dette tilfælde rutningsområde er et rektangel, alle redskaber er to-terminal, og terminalerne er anbragt på omkredsen af ​​rektanglet. Det ses let, at skæringspunktet graf over disse net er en cirkel graf. Blandt målene for wire routing skridt er at sikre, at forskellige redskaber ophold elektrisk frakoblet, og deres potentielle skærende dele skal lægges ud i forskellige ledende lag. Derfor cirkel grafer fange forskellige aspekter af denne routing problem.

Farvestoffer cirkel grafer kan også bruges til at finde bogen indlejringerne af vilkårlige grafer: hvis knudepunkter af en given graf G er anbragt på en cirkel, med kanterne af G danner akkorder cirklen, derefter krydset graf over disse akkorder er en cirkel graf og farvestoffer i denne cirkel graf svarer til bog indlejringerne, der respekterer den givne cirkulære layout. I denne ækvivalens, antallet af farver i farve svarer til antallet af sider i bogen indlejring.

Relaterede graf klasser

En graf er en cirkel graf hvis og kun hvis det er overlappet graf af et sæt intervaller på en linje. Dette er en graf, hvor de knudepunkter svarer til intervallerne, og to knudepunkter er forbundet med en kant, hvis de to intervaller overlapper hinanden, med hverken indeholder den anden.

Skæringspunktet graf af et sæt intervaller på en linje kaldes intervallet grafen.

String grafer, skæringspunktet grafer af kurver i flyet, omfatter cirkel grafer som et særligt tilfælde.

Hver distance-arvelige graf er en cirkel graf, som er hver permutation graf og hvert ligegyldighed graf. Hver outerplanar graf er også en cirkel graf.

  0   0
Forrige artikel David H. Shepard
Næste artikel Emerson Moisés Costa

Kommentarer - 0

Ingen kommentar

Tilføj en kommentar

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Tegn tilbage: 3000
captcha