Blokgraf - Block graph
I grafteori , en gren af kombinatoriske matematik, en blok graf eller klike træ er en type af ikke-orienterede graf hvor hver biconnected komponent (blok) er en klike .
Bloker grafer er undertiden fejlagtigt kaldes Husimi træer (efter Kodi Husimi ), men det navn refererer mere korrekt at kaktus grafer , grafer, hvor hver nontrivial biconnected komponent er en cyklus.
Blokgrafer kan karakteriseres som skæringsgraferne for blokkene af vilkårligt uorienterede grafer.
Karakterisering
Blokgrafer er nøjagtigt de grafer, som for hver fire hjørner u , v , x og y de to største af de tre afstande d ( u , v ) + d ( x , y ), d ( u , x ) + d ( v , y ) og d ( u , y ) + d ( v , x ) er altid ens.
De har også en forbudt grafkarakterisering som de grafer, der ikke har diamantgrafen eller en cyklus med fire eller flere hjørner som en induceret undergraf ; det vil sige, at de er de diamantfrie akkordgrafer. De er også de Ptolemaiske grafer ( akkordafstandsarvelige grafer ), hvor hver to knudepunkter på afstand to fra hinanden er forbundet med en unik kortest vej , og akkordgraferne, hvor hver to maksimale klik har højst et toppunkt til fælles.
En graf G er en blokgraf, hvis og kun hvis skæringspunktet for hver to tilsluttede undersæt af hjørner af G er tomt eller forbundet. Derfor danner de tilsluttede undersæt af hjørner i en tilsluttet blokgraf en konveks geometri , en egenskab, der ikke er sand for alle grafer, der ikke er blokgrafer. På grund af denne egenskab har hvert sæt hjørner i en tilsluttet blokgraf et unikt minimalt tilsluttet supersæt, dets lukning i den konvekse geometri. De tilsluttede blokgrafer er nøjagtigt de grafer, hvor der er en unik induceret sti, der forbinder hvert par hjørner.
Relaterede grafklasser
Blokgrafer er akkordale , afstandsarvelige og geodetiske . De afstandsarvede grafer er graferne, hvor hver to inducerede stier mellem de samme to hjørner har samme længde, en svækkelse af karakteriseringen af blokgrafer som højst en induceret vej mellem hver to hjørner. Fordi både akkordgraferne og de afstandsarvelige grafer er underklasser af de perfekte grafer , er blokgrafer perfekte.
Hvert træ , klyngediagram eller vindmøllediagram er en blokgraf.
Hver blokgraf har højst to bokstaver .
Blokgrafer er eksempler på pseudomediansk grafer : for hver tre hjørner findes enten et unikt toppunkt, der tilhører de korteste stier mellem alle tre hjørner, eller der findes en unik trekant, hvis kanter ligger på disse tre korteste stier.
De liniegrafer af træer er nøjagtig blok grafer, hvor hvert snit vertex er hændelsen til højst to blokke, eller tilsvarende de klo-fri blok grafer. Linjediagrammer over træer er blevet brugt til at finde grafer med et givet antal kanter og hjørner, hvor den største inducerede subgraf, der er et træ, er så lille som muligt.
Blokgraferne, hvor hver blok højst har tre størrelser, er en særlig type kaktusgraf , en trekantet kaktus. Den største trekantede kaktus i enhver graf kan findes i polynomisk tid ved hjælp af en algoritme til matroid paritetsproblemet . Da trekantede kaktusgrafer er plane grafer , kan den største trekantede kaktus bruges som en tilnærmelse til den største plane undergraf, et vigtigt delproblem i planarisering . Som en tilnærmelsesalgoritme har denne metode tilnærmelsesforhold 4/9, den bedst kendte for det maksimale plane subgrafproblem.
Bloker grafer for ikke -dirigerede grafer
Hvis G er en uorienteret graf, er blokgrafen for G , betegnet B ( G ), skæringspunktgrafen for blokkene i G : B ( G ) har et toppunkt for hver toforbundet komponent i G og to hjørner af B ( G ) er tilstødende, hvis de tilsvarende to blokke mødes ved et artikuleringspunkt. Hvis K 1 betegner grafen med et toppunkt, er B ( K 1 ) defineret til at være den tomme graf . B ( G ) er nødvendigvis en blokgraf: den har en sammenkoblet komponent for hvert artikulationspunkt i G , og hver dobbeltforbundet komponent dannet på denne måde skal være en klik. Omvendt hver blok graf er grafen B ( G ) for nogle graf G . Hvis G er et træ, derefter B ( G ) falder sammen med linjediagrammet af G .
Grafen B ( B ( G )) har et toppunkt for hvert artikulationspunkt i G ; to knudepunkter er hosliggende i B ( B ( G )), hvis de tilhører samme blokeret G .
