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] .
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] .
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] .
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 .