Blokgraf

En blokgraf ( kliketræ [1] ) er en type urettet graf , hvor hver biforbundne komponent (blok) er en klike [2] .

Blokgrafer kan beskrives ved blokskæringsgrafer af vilkårlige urettede grafer [3] .

Beskrivelse

Blokgrafer er præcis de grafer, hvor for hver fjerde toppunkt , , og de største to af de tre afstande , , altid er [4] [5] [6] . $u$ $v$ $x$ $y$ $d(u,v)+d(x,y)$ $d(u,x)+d(v,y)$ $d(u,y)+d(v,x)$

De kan også beskrives i form af forbudte undergrafer , som grafer, der ikke indeholder ruder eller cyklusser af længde fire eller mere som en genereret undergraf . Det vil sige, at de er akkordgrafer uden diamanter [6] . De er også Ptolemæus-grafer ( akkorddistance -arvede grafer [7] ), hvor to vilkårlige hjørner i en afstand af to er forbundet med en enkelt korteste sti [4] , og akkordgrafer, hvor to vilkårlige kliker har højst en fælles toppunkt [4] .

En graf er en blokgraf, hvis og kun hvis skæringspunktet mellem to forbundne undersæt af grafens hjørnepunkter enten er tomt eller forbundet. Forbundne delmængder af hjørner i en forbundet blokgraf danner således en konveks geometri , og ingen anden form for grafer har denne egenskab [8] . På grund af denne egenskab, i en forbundet blokgraf, har ethvert sæt af hjørner et unikt minimalt forbundet supersæt, lukningen af sættet i en konveks geometri. Forbundne blokgrafer er præcis de grafer, hvor der er en unik genereret sti, der forbinder to vilkårlige par af hjørner [1] . $G$ $G$

Relaterede grafklasser

Blokgrafer er akkorde [9] og afstandsnedarvede grafer . Afstandsarvede grafer er grafer, hvor to underordnede stier mellem to knudepunkter er af samme længde, hvilket er svagere end kravet om, at blokgrafer skal have en enkelt underordnet sti mellem vilkårlige to knudepunkter. Da både akkordgrafer og afstandsnedarvede grafer er underklasser af perfekte grafer , er blokgrafer også perfekte.

Ethvert træ er en blokgraf. Mills giver et andet eksempel på en klasse af blokgrafer .

Enhver blokgraf har rektangularitet , der ikke overstiger to [10] [11] .

Blokgrafer er et eksempel på pseudomediangrafer — for alle tre toppunkter er der enten et enkelt toppunkt, der ligger på de tre korteste veje mellem disse tre hjørner, eller også er der en enkelt trekant, hvis kanter ligger på disse korteste veje. [ti]

Trælinjegrafer er blokgrafer, hvor ethvert skærende toppunkt falder ind på højst to blokke, eller tilsvarende blokgrafer uden kløer . Linjegrafer af træer bruges til at finde grafer med et givet antal kanter og toppunkter, hvor den største genererede subgraf, som er et træ af mindst mulig størrelse [12] .

Blokgrafer af urettede grafer

Blokgrafen for en given graf (angivet med ) er skæringsgrafen for grafens blokke : den har et toppunkt for hver todelt komponent i grafen, og to hjørner af grafen støder op til hinanden, hvis de tilsvarende to blokke deler hinanden (har en almindelig) hængsel (i Hararis termer, et artikulationspunkt) [13] . Hvis er en graf med et toppunkt, så vil det per definition være en tom graf. er kendt for at være blok - den har en bi-forbundet komponent for hvert artikulationspunkt i grafen , og hver bi-forbundne komponent dannet på denne måde vil være en klike. Omvendt er enhver blokgraf en graf for nogle [3] . Hvis er et træ, så falder det sammen med grafens linjegraf . $G$ $B(G)$ $G$ $B(G)$ $G$ $B(G)$ $K_1$ $B(K_{1})$ $B(G)$ $G$ $B(G)$ $G$ $G$ $B(G)$ $G$

Grafen har et toppunkt for hvert grafartikulationspunkt . To hjørner er tilstødende i, hvis de tilhører samme blok i [3] . $B(B(G))$ $G$ $B(B(G))$ $G$

Noter

↑ 1 2 Kristina Vušković. Grafer uden lige huller: En undersøgelse // Anvendelig analyse og diskret matematik. - 2010. - T. 4 , no. 2 . — S. 219–240 . - doi : 10.2298/AADM100812027V .
↑ Blokgrafer kaldes nogle gange fejlagtigt Husimi-træer, efter den japanske fysiker Cody Husimi ), men Husimi betragtede Cactus (grafteori) - grafer, hvor enhver dobbeltforbundet komponent er en cyklus.
↑ 1 2 3 Frank Harary. En karakterisering af blokgrafer // Canadian Mathematical Bulletin. - 1963. - T. 6 , no. 1 . — S. 1–6 . - doi : 10.4153/cmb-1963-001-x .
↑ 1 2 3 Edward Howorka. Om metriske egenskaber ved visse klikgrafer // Journal of Combinatorial Theory, Series B. - 1979. - Vol. 27 , nr. 1 . — S. 67–74 . - doi : 10.1016/0095-8956(79)90069-8 .
↑ Brandstädt, Le, Spinrad, 2005 ; s. 151, Sætning 10.2.6
↑ 1 2 Hans-Jürgen Bandelt, Henry Martyn Mulder. Distance-hereditary graphs // Journal of Combinatorial Theory, Series B. - 1986. - V. 41 , no. 2 . — S. 182–208 . - doi : 10.1016/0095-8956(86)90043-2 .
↑ Brandstädt, Le, Spinrad, 2005 ; side 130, konsekvens 8.4.2
↑ Paul H. Edelman, Robert E. Jamison. Teorien om konvekse geometrier // Geometriae Dedicata. - 1985. - T. 19 , no. 3 . — S. 247–270 . - doi : 10.1007/BF00149365 .
↑ Der er følgende hierarki af grafklasser: Ptolemæus blok strengt akkord akkord $\undersæt$ $\undersæt$ $\undersæt$ Brandstadt, Le, Spinrad, 2005 S. 126, kapitel 8.2 Yderligere acyklicitetstyper; klike og kvarters hypergrafer
↑ 1 2 Block Graphs Arkiveret 21. november 2019 på Wayback Machine , Graph Class Hierarchy Information System
↑ Brandstädt, Le, Spinrad, 2005 s. 54, kapitel 4.5 Boxicitet, skæringsdimension og prikprodukt
↑ Paul Erdős, Michael Saks, Vera T. Sos. Maksimalt inducerede træer i grafer // Journal of Combinatorial Theory, Series B. - 1986. - V. 41 , no. 1 . — s. 61–79 . - doi : 10.1016/0095-8956(86)90028-6 .
↑ F. Harari. Grafteori. - Moskva: URSS, 2003. - ISBN 5-354-00301. Kapitel 3. Blokke, s. 41-46

Litteratur

Andreas Brandstädt, Van Bang Le, Jeremy P. Spinrad. Grafklasser: en undersøgelse. - Philadelphia: SIAM, 2005. - (SIAM-monografier om diskret matematik). — ISBN 0-89871-432-X .