Blockdiagram

En blockgraf ( klickträd [1] ) är en typ av oriktad graf där varje dubbelkopplad komponent (block) är en klick [2] .

Blockgrafer kan beskrivas med blockskärningsgrafer av godtyckliga oriktade grafer [3] .

Beskrivning

Blockgrafer är exakt de grafer där för varje fyra hörn , , och de största två av de tre avstånden , , alltid är [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 också beskrivas i termer av förbjudna subgrafer , som grafer som inte innehåller diamanter eller cykler med längd fyra eller mer som en genererad subgraf . Det vill säga att de är ackordsgrafer utan diamanter [6] . De är också Ptolemaios-grafer ( ackorddistans -ärvda grafer [7] ), där vilka två hörn som helst på ett avstånd av två är sammankopplade med en enda kortaste väg [4] , och ackordsgrafer, där två valfria klick har högst en gemensam vertex [4] .

En graf är en blockgraf om och endast om skärningspunkten mellan två anslutna delmängder av grafens hörn är antingen tom eller sammankopplad. Således bildar anslutna delmängder av hörn i en ansluten blockgraf en konvex geometri , och ingen annan typ av grafer har denna egenskap [8] . På grund av denna egenskap, i en sammankopplad blockgraf, har varje uppsättning av hörn en unik minimal sammankopplad supermängd, stängningen av uppsättningen i en konvex geometri. Sammankopplade blockgrafer är exakt de grafer där det finns en unik genererad väg som förbinder två par av hörn [1] . $G$ $G$

Relaterade grafklasser

Blockgrafer är kordala [9] och avståndsärvda grafer . Avståndsärvda grafer är grafer där två underordnade vägar mellan två hörn är av samma längd, vilket är svagare än kravet på att blockgrafer ska ha en enda underordnad bana mellan två hörn. Eftersom både ackordsgrafer och avståndsärvda grafer är underklasser av perfekta grafer , är blockgrafer också perfekta.

Vilket träd som helst är ett blockdiagram. Mills ger ett annat exempel på en klass av blockgrafer .

Varje blockgraf har en rektangularitet som inte överstiger två [10] [11] .

Blockgrafer är ett exempel på pseudomediangrafer — för alla tre hörn, antingen finns det en enda vertex som ligger på de tre kortaste banorna mellan dessa tre hörn, eller så finns det en enda triangel vars kanter ligger på dessa kortaste banor. [tio]

Trädlinjegrafer är blockgrafer där varje skärande hörn faller mot högst två block, eller på motsvarande sätt blockgrafer utan klor . Linjediagram av träd används för att hitta grafer med ett givet antal kanter och hörn, där den största genererade subgrafen, som är ett träd av minsta möjliga storlek [12] .

Blockgrafer för oriktade grafer

Blockgrafen för en given graf (betecknad med ) är skärningsgrafen för blocken i grafen : den har en vertex för varje tvåkopplad komponent i grafen och två hörn av grafen ligger intill om motsvarande två block delar (har en vanligt) gångjärn (i Hararis termer, en artikulationspunkt) [13] . Om är en graf med en vertex, så kommer det per definition att vara en tom graf. är känt för att vara block - den har en dubbelkopplad komponent för varje artikulationspunkt i grafen , och varje dubbelkopplad komponent som bildas på detta sätt kommer att vara en klick. Omvänt är varje blockgraf en graf för vissa [3] . Om är ett träd, så sammanfaller det med grafens linjediagram . $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 en vertex för varje grafartikulationspunkt . Två hörn ligger intill om de tillhör samma block i [3] . $B(B(G))$ $G$ $B(B(G))$ $G$

Anteckningar

↑ 1 2 Kristina Vušković. Jämna hålfria grafer: En undersökning // Tillämplig analys och diskret matematik. - 2010. - T. 4 , nr. 2 . — S. 219–240 . - doi : 10.2298/AADM100812027V .
↑ Blockgrafer kallas ibland felaktigt för Husimi-träd, efter den japanska fysikern Cody Husimi ), men Husimi betraktade Cactus (grafteori) - grafer där vilken som helst dubbelkopplad komponent är en cykel.
↑ 1 2 3 Frank Harary. En karakterisering av blockdiagram // Canadian Mathematical Bulletin. - 1963. - T. 6 , nr. 1 . — S. 1–6 . - doi : 10.4153/cmb-1963-001-x .
↑ 1 2 3 Edward Howorka. Om metriska egenskaper hos vissa klickgrafer // 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, sats 10.2.6
↑ 1 2 Hans-Jürgen Bandelt, Henry Martyn Mulder. Distance-hereditary graphs // Journal of Combinatorial Theory, Series B. - 1986. - V. 41 , nr. 2 . — S. 182–208 . - doi : 10.1016/0095-8956(86)90043-2 .
↑ Brandstädt, Le, Spinrad, 2005 ; sid 130, följd 8.4.2
↑ Paul H. Edelman, Robert E. Jamison. Teorin om konvexa geometrier // Geometriae Dedicata. - 1985. - T. 19 , nr. 3 . — S. 247–270 . - doi : 10.1007/BF00149365 .
↑ Det finns följande hierarki av grafklasser: Ptolemaios block strikt ackord ackord $\delmängd$ $\delmängd$ $\delmängd$ Brandstadt, Le, Spinrad, 2005, s. 126, kapitel 8.2 Ytterligare acyklicitetstyper; klick och grannskapshypergrafer
↑ 1 2 Block Graphs Arkiverade 21 november 2019 på Wayback Machine , Graph Class Hierarchy Information System
↑ Brandstädt, Le, Spinrad, 2005 sid. 54, kapitel 4.5 Boxicitet, skärningsdimension och punktprodukt
↑ Paul Erdős, Michael Saks, Vera T. Sos. Maximalt inducerade träd i grafer // Journal of Combinatorial Theory, Series B. - 1986. - V. 41 , nr. 1 . — s. 61–79 . - doi : 10.1016/0095-8956(86)90028-6 .
↑ F. Harari. Grafteori. - Moskva: URSS, 2003. - ISBN 5-354-00301. Kapitel 3. Block, s. 41-46

Litteratur

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