Blokk grafikon

A blokkgráf ( klikkfa [1] ) az irányítatlan gráfok egyik fajtája , amelyben minden két összekapcsolt komponens (blokk) egy klikk [2] .

A blokkgráfok tetszőleges irányítatlan gráfok blokkmetszete gráfjaival írhatók le [3] .

Leírás

A blokkgráfok pontosan azok a gráfok, amelyekben minden négy csúcsra , , és a három távolság közül a legnagyobb kettő , mindig [ 4] [5] [6] .

Leírhatók tiltott részgráfok formájában is , mint olyan gráfok, amelyek nem tartalmaznak gyémántokat vagy négy vagy annál hosszabb ciklusokat generált részgráfként . Vagyis gyémánt nélküli akkordgráfok [6] . Ezek Ptolemaiosz-gráfok ( akkordtávolság -örökölt gráfok [7] ), amelyekben bármely két, kettő távolságra lévő csúcsot egyetlen legrövidebb út köt össze [4] , valamint akkordgráfok, amelyekben bármely két klikknek legfeljebb egy közös csúcs [4] .

A gráf akkor és csak akkor blokkgráf, ha a gráfcsúcsok bármely két összekapcsolt részhalmazának metszéspontja üres vagy összefüggő. Így a csúcsok összefüggő részhalmazai egy összefüggő blokkgráfban konvex geometriát alkotnak , és semmilyen más típusú gráf nem rendelkezik ezzel a tulajdonsággal [8] . Emiatt a tulajdonság miatt egy összefüggő blokkgráfban minden csúcshalmaznak van egy egyedi minimális összekapcsolt szuperhalmaza, a halmaz zárása egy konvex geometriában. Az összekapcsolt blokkgráfok pontosan azok a gráfok, amelyekben van egy egyedi generált útvonal , amely bármely két csúcspárt összeköti [1] .

Kapcsolódó gráfosztályok

A blokkgráfok akkordális [9] és távolság öröklött gráfok . A távolságtól örökölt gráfok olyan gráfok, amelyekben két csúcs közötti bármely két gyermekút azonos hosszúságú, ami gyengébb, mint a blokkgráfokra vonatkozó követelmény, hogy bármely két csúcs között egyetlen gyermekút legyen. Mivel az akkordgráfok és a távolság öröklött gráfok is a tökéletes gráfok alosztályai, a blokkgráfok is tökéletesek.

Bármely fa blokkgráf. Mills egy másik példa a blokkgráfok osztályára .

Bármely blokkgráf négyszögletessége nem haladja meg a kettőt [10] [11] .

A blokkgráfok a pszeudo- medián gráfok példái  – bármely három csúcshoz vagy van egyetlen csúcs, amely a három legrövidebb úton fekszik e három csúcs között, vagy van egyetlen háromszög, amelynek élei ezeken a legrövidebb útvonalakon fekszenek. [tíz]

A favonal-gráfok olyan blokkgráfok, amelyekben bármely vágási csúcs legfeljebb két blokkra esik, vagy ennek megfelelően karmok nélküli blokkgráfok . A fák vonalgráfjait arra használjuk, hogy adott számú élű és csúcsú gráfot keressünk, amelyben a legnagyobb generált részgráf, ami a lehető legkisebb méretű fa [12] .

Irányítatlan gráfok blokkgráfjai

Egy adott gráf blokkgráfja (jelölése ) a gráf blokkjainak metszésponti gráfja : van egy csúcsa a gráf minden egyes összekapcsolt komponenséhez, és a gráf két csúcsa szomszédos, ha a megfelelő két blokk osztozik (van egy közös) csuklópánt (harari kifejezéssel artikulációs pont) [13] . Ha egy gráf egy csúcsú, akkor definíció szerint üres gráf lesz. ismert, hogy blokk - a gráf minden egyes artikulációs pontjához van egy kettõs kapcsolódású komponense , és minden így kialakított kettõs komponens egy klikk lesz. Ezzel szemben bármely blokkgráf egy bizonyos [3] grafikonja . Ha  egy fa, akkor egybeesik a gráf vonalgráfjával .

A gráfnak minden gráf artikulációs ponthoz van egy csúcsa . Két csúcs szomszédos -ben, ha ugyanahhoz a blokkhoz tartoznak a [3] -ban .

Jegyzetek

  1. 1 2 Kristina Vušković. Páros lyuk nélküli grafikonok: felmérés // Alkalmazható elemzés és diszkrét matematika. - 2010. - T. 4 , sz. 2 . – S. 219–240 . - doi : 10.2298/AADM100812027V .
  2. A blokkgráfokat néha tévesen Husimi-fáknak nevezik, Cody Husimi japán fizikus után , de Husimi a kaktuszt (gráfelméletet) tekintette  – olyan gráfokat, amelyekben bármely kétszeresen összefüggő komponens egy ciklus.
  3. 1 2 3 Frank Harary. A blokkgráfok jellemzése // Canadian Mathematical Bulletin. - 1963. - T. 6 , sz. 1 . — S. 1–6 . - doi : 10.4153/cmb-1963-001-x .
  4. 1 2 3 Edward Howorka. Egyes klikkgráfok metrikus tulajdonságairól // 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 ; 151. o., 10.2.6. tétel
  6. 1 2 Hans-Jürgen Bandelt, Henry Martyn Mulder. Távolság-örökletes gráfok // 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 ; 130. oldal, Következmény 8.4.2
  8. Paul H. Edelman, Robert E. Jamison. A konvex geometriák elmélete // Geometriae Dedicata. - 1985. - T. 19 , sz. 3 . – S. 247–270 . - doi : 10.1007/BF00149365 .
  9. A gráfosztályok következő hierarchiája van: Ptolemaiosz blokk szigorúan akkordális akkord Brandstadt, Le, Spinrad, 2005, o. 126. fejezet, 8.2 További aciklicitástípusok; klikk és szomszédsági hipergráfok
  10. 1 2 blokkgrafikon archiválva 2019. november 21-én a Wayback Machine Graph Class Hierarchy Information System- nél
  11. Brandstädt, Le, Spinrad, 2005 p. 54, 4.5. fejezet Dobozosság, metszésméret és pontszorzat
  12. Erdős Paul, Michael Saks, Vera T. Sos. Maximum induced trees in graphs // Journal of Combinatorial Theory, Series B. - 1986. - V. 41 , no. 1 . – 61–79 . - doi : 10.1016/0095-8956(86)90028-6 .
  13. F. Harari. Gráfelmélet. - Moszkva: URSS, 2003. - ISBN 5-354-00301. 3. fejezet Blokkok, 41-46

Irodalom