Blokkgráf
A matematika, azon belül a gráfelmélet területén egy blokkgráf (block graph) vagy klikkfa (clique tree)[1] olyan irányítatlan gráf, melynek minden kétszeresen összefüggő komponense (blokkja) klikk. A blokkgráfokat néha tévesen Husimi-fáknak is nevezik (Kôdi Husimi után),[2] de ez a név inkább a kaktuszgráfokra illik, melyekben minden nemtriviális kétszeresen összefüggő komponens kör.[3] A blokkgráfok karakterisztikusan jellemezhetők tetszőleges irányítatlan gráfok blokkjainak metszetgráfjaiként is.[4]
Karakterizáció
[szerkesztés]A blokkgráfok éppen azok a gráfok, melyek bármely négy u, v, x, y csúcsát tekintve a három távolságösszeg, d(u,v) + d(x,y), d(u,x) + d(v,y), és d(u,y) + d(v,x) közül a két legnagyobb mindig megegyezik.[2][5] Létezik tiltott gráfok szerinti osztályozásuk is, miszerint a gráfok, melyek nem tartalmazzák sem a gyémántgráfot, sem legalább négy hosszúságú kört feszített részgráfként; tehát a gyémántmentes merev körű gráfok.[5] A blokkgráfok továbbá azok a ptolemaioszi gráfok is (merev körű távolság-örökletes gráfok), melyekben bármely két, egymástól kettő távolságra kévő csúcsot egyedi legrövidebb út köt össze,[2] továbbá azok a merev körű gráfok, melyekben bármely két maximális klikknek legfeljebb egy közös csúcsa van.[2] Egy G gráf pontosan akkor blokkgráf, ha G csúcsaiból képzett bármely két összefüggő részhalmazának metszete vagy üres, vagy összefüggő. Ezért az összefüggő blokkgráf csúcsainak összefüggő részhalmazai ún. konvex geometriát alkotnak, ami a nem blokkgráfokra általában nem igaz.[6] Ezen tulajdonságuk miatt egy összefüggő blokkgráf minden csúcshalmazának egyedi a minimális összefüggő bővebb halmaza, avagy a konvex geometrián belüli lezárása. Az összefüggő blokkgráfok pontosan azok a gráfok, melyekben minden csúcspárt egyedi feszített út köt össze.[1]
Kapcsolódó gráfcsaládok
[szerkesztés]A blokkgráfok távolság-örökletes és merev körű gráfok. A távolság-örökletes gráfokban két tetszőleges csúcs között minden feszített út azonos hosszúságú, ami a blokkgráfok azon feltételének gyengített változata, miszerint két tetszőleges csúcs között csak egy feszített út lehet. Mivel a merev körű gráfok és a távolság-örökletes gráfok is a perfekt gráfok közé tartoznak, ezért a blokkgráfok is perfektek. Minden fa, klasztergráf és szélmalomgráf is blokkgráf. A blokkgráfok boxicitása (hipertéglatest-dimenziója) legfeljebb kettő.[7] A blokkgráfok a pszeudomediángráfok közé tartoznak: bármely három csúcsot tekintve vagy létezik olyan egyedi csúcs, ami mindhárom csúcspár közti legrövidebb út része, vagy létezik olyan egyedi háromszög, melynek élei ezen a három legrövidebb úton vannak.[7] A fák élgráfjai pontosan azok a blokkgráfok, melyekben minden artikulációs pont legfeljebb két blokkal szomszédos, vagy ezzel ekvivalens definíció szerint a karommentes blokkgráfok. A fák élgráfjait felhasználták olyan, adott csúcs- és élszámú gráfok keresésére, melyek legnagyobb feszített fa részgráfja a lehető legkisebb méretű.[8] Azok a blokkgráfok, melyek minden blokkja legfeljebb három csúcsból áll, a kaktuszgráfok egy speciális fajtáját alkotják, a háromszögű kaktuszokat. A legnagyobb háromszögű kaktuszt tetszőleges gráfban polinom időben meg lehet keresni matroidparitás-probléma egy algoritmusa segítségével. Mivel a háromszögű kaktuszok síkba rajzolhatók, a legnagyobb háromszögű kaktusz felhasználható a legnagyobb síkbarajzolható részgráf keresésekor, ami a planarizáció fontos részproblémája. Approximációs algoritmusként az elért approximációs arány 4/9, ami a legnagyobb síkbarajzolható részgráf problémájánál ismert legjobb arány.[9]
Irányítatlan gráfok blokkgráfjai
[szerkesztés]Ha G egy irányítatlan gráf, akkor G blokkgráfja, jelölése B(G) a G blokkjainak metszetgráfjával egyezik meg: B(G) minden csúcsa G egy kétszeresen összefüggő komponensének felel meg, B(G) két csúcsát pedig akkor köti össze él, ha a nekik megfelelő két blokkot egy artikulációs csúcs köti össze. Ha K1 az egy csúcsból álló gráfot jelöli, B(K1) definíció szerint az üres gráf. B(G) mindenképpen blokkgráf: G minden artikulációs csúcsához egy-egy kétszeresen összefüggő komponense tartozik, és minden, ilyen módon létrejövő komponensnek klikknek kell lennie. Megfordítva, minden blokkgráf felírható valamely G gráf B(G) blokkgráfjaként.[4] Ha G egy fa, akkor B(G) megegyezik a G élgráfjával. A B(B(G)) gráf minden csúcsa G egy artikulációs csúcsának felel meg; két csúcs akkor szomszédos B(B(G))-ben, ha G ugyanazon blokkjába tartoznak.[4]
Fordítás
[szerkesztés]Ez a szócikk részben vagy egészben a Block graph című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.
Jegyzetek
[szerkesztés]- ↑ a b Vušković, Kristina (2010), "Even-hole-free graphs: A survey", Applicable Analysis and Discrete Mathematics 4 (2): 219–240, DOI 10.2298/AADM100812027V.
- ↑ a b c d Howorka, Edward (1979), "On metric properties of certain clique graphs", Journal of Combinatorial Theory, Series B 27 (1): 67–74, DOI 10.1016/0095-8956(79)90069-8.
- ↑ Lásd pl. MR0659742, Robert E. Jamison egy 1983-as értékelését egy másik cikkről, ami a blokkgráfokat Husimi-fáknak nevezi; Jamison a hibát Mehdi Behzad és Gary Chartrand könyvének tulajdonítja.
- ↑ a b c Harary, Frank (1963), "A characterization of block-graphs", Canadian Mathematical Bulletin 6 (1): 1–6, DOI 10.4153/cmb-1963-001-x.
- ↑ a b Bandelt, Hans-Jürgen & Mulder, Henry Martyn (1986), "Distance-hereditary graphs", Journal of Combinatorial Theory, Series B 41 (2): 182–208, DOI 10.1016/0095-8956(86)90043-2.
- ↑ Edelman, Paul H. & Jamison, Robert E. (1985), "The theory of convex geometries", Geometriae Dedicata 19 (3): 247–270, DOI 10.1007/BF00149365.
- ↑ a b Block graphs, Information System on Graph Class Inclusions.
- ↑ Erdős, Paul; Saks, Michael & Sós, Vera T. (1986), "Maximum induced trees in graphs", Journal of Combinatorial Theory, Series B 41 (1): 61–79, DOI 10.1016/0095-8956(86)90028-6.
- ↑ Călinescu, Gruia; Fernandes, Cristina G & Finkler, Ulrich et al. (2002), "A Better Approximation Algorithm for Finding Planar Subgraphs", Journal of Algorithms, 2 27: 269– 302, DOI 10.1006/jagm.1997.0920
