Blokový graf

Blokový graf ( klikový strom [1] ) je typ neorientovaného grafu , ve kterém je každá bipropojená složka (blok) klikou [2] .

Blokové grafy lze popsat pomocí blokových průsečíkových grafů libovolných neorientovaných grafů [3] .

Popis

Blokové grafy jsou přesně ty grafy, ve kterých pro každé čtyři vrcholy , , a největší dvě ze tří vzdáleností , jsou vždy [4] [5] [6] .

Mohou být také popsány v termínech zakázaných podgrafů , jako grafy, které neobsahují kosočtverce nebo cykly o délce čtyři nebo více jako generovaný podgraf . To znamená, že jsou to akordické grafy bez diamantů [6] . Jsou to také Ptolemaiovy grafy ( akordické grafy zděděné vzdáleností [7] ), ve kterých jsou libovolné dva vrcholy ve vzdálenosti dvou spojeny jedinou nejkratší cestou [4] , a grafy tětivy, ve kterých mají libovolné dvě kliky nejvýše jednu společný vrchol [4] .

Graf je blokový graf právě tehdy, když je průsečík libovolných dvou spojených podmnožin vrcholů grafu prázdný nebo spojený. Souvislé podmnožiny vrcholů v souvislém blokovém grafu tedy tvoří konvexní geometrii a žádný jiný druh grafů tuto vlastnost nemá [8] . Kvůli této vlastnosti má v souvislém blokovém grafu jakákoliv sada vrcholů jedinečnou minimální spojenou nadmnožinu, uzavření množiny v konvexní geometrii. Souvislé blokové grafy jsou přesně ty grafy, ve kterých existuje jedinečná vygenerovaná cesta spojující libovolné dva páry vrcholů [1] .

Související třídy grafů

Blokové grafy jsou chordální [9] a grafy zděděné vzdáleností . Grafy zděděné vzdáleností jsou grafy, ve kterých mají libovolné dvě podřízené cesty mezi dvěma vrcholy stejnou délku, což je slabší než požadavek, aby blokové grafy měly jednu podřízenou cestu mezi libovolnými dvěma vrcholy. Protože jak akordické grafy, tak grafy zděděné vzdáleností jsou podtřídami dokonalých grafů , blokové grafy jsou také dokonalé.

Každý strom je blokový graf. Mills poskytuje další příklad třídy blokových grafů .

Libovolný blokový graf má pravoúhlost nepřesahující dvě [10] [11] .

Blokové grafy jsou příkladem pseudomediánových grafů  – pro jakékoli tři vrcholy buď existuje jeden vrchol, který leží na třech nejkratších cestách mezi těmito třemi vrcholy, nebo existuje jeden trojúhelník, jehož hrany leží na těchto nejkratších cestách. [deset]

Stromové grafy jsou blokové grafy, ve kterých jakýkoli řezný vrchol dopadá na nejvýše dva bloky, nebo ekvivalentně blokové grafy bez drápů . Spojnicové grafy stromů slouží k nalezení grafů s daným počtem hran a vrcholů, ve kterých je vygenerován největší podgraf, což je strom o nejmenší možné velikosti [12] .

Blokové grafy neorientovaných grafů

Blokový graf pro daný graf (označený ) je průsečíkem bloků grafu : má vrchol pro každou bipropojenou složku grafu a dva vrcholy grafu sousedí, pokud odpovídající dva bloky sdílejí (mají společný) závěs (podle Harariho kloubní bod) [13] . Pokud je graf s jedním vrcholem, pak to bude podle definice prázdný graf. je známo, že je blok - má jednu bi-spojenou komponentu pro každý artikulační bod grafu a každá bi-spojená komponenta vytvořená tímto způsobem bude klikou. Naopak libovolný blokový graf je pro některé grafem [3] . Pokud  je strom, pak se shoduje se spojnicovým grafem grafu .

Graf má vrchol pro každý bod artikulace grafu . Dva vrcholy sousedí v , pokud patří do stejného bloku v [3] .

Poznámky

  1. ↑ 1 2 Kristina Vušković. Grafy bez sudých děr: Průzkum // Použitelná analýza a diskrétní matematika. - 2010. - T. 4 , no. 2 . — S. 219–240 . - doi : 10.2298/AADM100812027V .
  2. ↑ Blokové grafy se někdy mylně nazývají stromy Husimi, podle japonského fyzika Codyho Husimiho ), ale Husimi zvažoval Cactus (teorii grafů)  - grafy, ve kterých je jakákoliv dvojitě spojená složka cyklem.
  3. ↑ 1 2 3 Frank Harary. Charakteristika blokových grafů // Canadian Mathematical Bulletin. - 1963. - T. 6 , no. 1 . — S. 1–6 . - doi : 10.4153/cmb-1963-001-x .
  4. ↑ 1 2 3 Edward Howorka. O metrických vlastnostech určitých klikových grafů // Journal of Combinatorial Theory, Series B. - 1979. - Vol. 27 , no. 1 . — S. 67–74 . - doi : 10.1016/0095-8956(79)90069-8 .
  5. ↑ Brandstädt, Le, Spinrad, 2005 ; str. 151, Věta 10.2.6
  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 .
  7. ↑ Brandstädt, Le, Spinrad, 2005 ; strana 130, Důsledek 8.4.2
  8. ↑ Paul H. Edelman, Robert E. Jamison. Teorie konvexních geometrií // Geometriae Dedicata. - 1985. - T. 19 , no. 3 . — S. 247–270 . - doi : 10.1007/BF00149365 .
  9. ↑ Existuje následující hierarchie tříd grafů: Ptolemaiův blok přísně akordický akordický Brandstadt, Le, Spinrad, 2005 Pp. 126, kapitola 8.2 Další typy acykličnosti; klikové a sousedské hypergrafy
  10. ↑ 1 2 Block Graphs Archived 21. listopadu 2019 na Wayback Machine , Graph Class Hierarchy Information System
  11. ↑ Brandstädt, Le, Spinrad, 2005 s. 54, kapitola 4.5 Boxicita, rozměr průniku a bodový součin
  12. ↑ Paul Erdős, Michael Saks, Vera T. Sos. Maximální indukované stromy v grafech // Journal of Combinatorial Theory, Series B. - 1986. - V. 41 , no. 1 . — s. 61–79 . - doi : 10.1016/0095-8956(86)90028-6 .
  13. ↑ F. Harari. Teorie grafů. - Moskva: URSS, 2003. - ISBN 5-354-00301. Kapitola 3. Bloky, s. 41-46

Literatura