Metszetgráf

Példa egymást metsző halmazok által meghatározott gráfra.

A matematika, azon belül a gráfelmélet területén egy metszetgráf (angolul: intersection graph) olyan gráf, ami halmazok metszeteinek feleltethető meg. Bármely gráf megjeleníthető metszetgráfként, de a gráfok egyes fontos és speciális osztályai az alapján definiálhatók, hogy milyen típusú halmazok metszeteként jelennek meg.

A metszetgráfokról és fontos osztályaikról (McKee & McMorris 1999) ad szakszerű áttekintést.

Formális definíció

Formálisan, egy S_i, i = 0, 1, 2, ... halmazcsalád metszetgráfja irányítatlan gráf, melyet a következőképpen kapunk: minden S_i halmazhoz létrehozunk egy v_i csúcsot, majd a v_i és v_j csúcsokat akkor kötjük össze éllel, ha a nekik megfelelő halmazok metszete nem üres, tehát

E(G) = {{v_i, v_j} | S_i ∩ S_j ≠ ∅}.

Minden gráf metszetgráf

Bármely G irányítatlan gráf megjeleníthető metszetgráfként: G minden v_i csúcsához hozzunk létre egy S_i halmazt, ami a v_i-vel szomszédos élekből áll; két ilyen halmaznak akkor és csak akkor nem üres a metszete, ha a megfelelő csúcsokat él köti össze. (Erdős, Goodman & Pósa 1966) hatékonyabb konstrukciót talált ki (abban az értelemben, hogy a szükséges S_i halmazok összes elemszáma kisebb lehet), amiben a halmazok elemeinek száma legfeljebb n²/4, ahol n a gráf csúcsainak száma. Erdősék (Szpilrajn-Marczewski 1945)-nek tulajdonítják a megfigyelést, hogy minden gráf metszetgráf, de figyelemre érdemes még (Čulík 1964) is. Egy gráf interszekciós száma a gráf metszetgráfként való megjelenítéshez minimálisan szükséges elemek száma.

Metszetgráfok osztályozása

Számos fontos gráfcsalád leírható bizonyos fajtájú halmazcsaládok, például valamely mértani alakzatból kinyerhető halmazok metszetgráfjaként:

• Az intervallumgráfok a valós számegyenes intervallumainak, vagy egy útgráf összefüggő részgráfjainak metszetgráfjai.
• Az egység-intervallumgráfok a valós számegyenes egységnyi intervallumainak metszetgráfjai.
• A körívgráf egy körön vett, zárt körívekből képzett metszetgráf.
• A sokszög–kör-gráf (polygon-circle graph) egy körön lévő csúcsokkal rendelkező sokszögek metszetgráfjai.
• A húrgráfok egyik karakterizálása, hogy egy fa összefüggő részgráfjainak metszetgráfjai.
• A trapézgráf két párhuzamos vonal által alkotott trapézok metszetgráfja. A permutációs gráf általánosítása, másrészről az összehasonlíthatósági gráfok komplementerei („cocomparability graphs”) által alkotott gráfcsalád speciális esete.
• Az egységkoronggráfok a sík egységkorongjainak metszetgráfjai.
• A húrmetszetgráf (circle graph) egy kör húrjainak metszetgráfja.
• A körpakolási tétel kimondja, hogy a síkgráfok pontosan a sík nem metsző körökkel határolt zárt körlapjainak metszetgráf-alapú osztályaival egyeznek meg.
• A Scheinerman-tétel kimondja, hogy minden síkgráf kifejezhető egyenes szakaszok metszetgráfjaként. Az egyenes szakaszok metszetgráfjaként előálló gráfok azonban nem mind síkba rajzolhatók, és az egyenes szakaszok metszetgráfjainak felismerése NP-nehéz és PSPACE-beli feladat..
• Egy G gráf élgráfja G éleinek metszetgráfja, ahol az éleket két végpontjuk reprezentálja.
• A füzérgráf síkgörbék metszetgráfja.
• Egy gráf boxicitása akkor k, ha felírható k dimenziós hipertéglatestek metszetgráfjaként, de k-nál kevesebb dimenzióban nem.
• A klikkgráf egy gráf maximális klikkjeinek metszetgráfja
• Egy klikkfa blokkgráfja egy gráf kétszeresen összefüggő komponenseinek metszetgráfja

(Scheinerman 1985) karakterizálta a metszetgráfok alapján meghatározott gráfosztályokat, melyek véges gráfok olyan csoportjai, melyek adott halmazcsalád metszetgráfjaiként írhatók le. Szükséges és elégséges, hogy a gráfosztály a következő tulajdonságokkal rendelkezzen:

• Az osztályban lévő gráfok minden feszített részgráfja is az osztályba tartozik.
• Az osztályban lévő gráfok bármely csúcsának klikkre cserélésével kapott gráf is az osztályba tartozik.
• Az osztályhoz tartozik egy gráfokból álló olyan végtelen sorozat, ahol minden gráf a következő gráf feszített részgráfja, és az osztály minden gráfja beletartozik a sorozatba.

Ha a metszetgráf-reprezentációnál megköveteljük, hogy különböző csúcsokat különböző halmazoknak kell megjelenítenie, akkor a klikkbővítési tulajdonság elhagyható.

Kapcsolódó fogalmak

A metszetgráfok rendezéselméleti analógiái a bennfoglalási rendezési relációk. Ahhoz hasonlóan, ahogy a gráf metszetgráf-reprezentációjában minden csúcsot egy-egy halmaz címkéz meg, és a csúcsok pontosan akkor szomszédosak, ha a halmazaiknak nem üres a metszete, egy részbenrendezett halmazon értelmezett f bennfoglalási reláció a halmaz minden elemét egy-egy halmazzal címkézi meg oly módon, hogy a részbenrendezés bármely x és y elempárjára a x ≤ y reláció pontosan akkor áll fenn, ha f(x) ⊆ f(y).

Fordítás

• Ez a szócikk részben vagy egészben az Intersection 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

• Čulík, K. (1964), "Applications of graph theory to mathematical logic and linguistics", Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963), Prague: Publ. House Czechoslovak Acad. Sci., pp. 13–20.
• Erdős, Paul; Goodman, A. W. & Pósa, Louis (1966), "The representation of a graph by set intersections", Canadian Journal of Mathematics 18 (1): 106–112, doi:10.4153/CJM-1966-014-3, <http://www.renyi.hu/~p_erdos/1966-21.pdf>.
• Golumbic, Martin Charles (1980), Algorithmic Graph Theory and Perfect Graphs, Academic Press, ISBN 0-12-289260-7.
• McKee, Terry A. & McMorris, F. R. (1999), Topics in Intersection Graph Theory, vol. 2, SIAM Monographs on Discrete Mathematics and Applications, Philadelphia: Society for Industrial and Applied Mathematics, ISBN 0-89871-430-3.
• Szpilrajn-Marczewski, E. (1945), "Sur deux propriétés des classes d'ensembles", Fund. Math. 33: 303–307.
• Schaefer, Marcus (2010), "Complexity of some geometric and topological problems", Graph Drawing, 17th International Symposium, GS 2009, Chicago, IL, USA, September 2009, Revised Papers, vol. 5849, Lecture Notes in Computer Science, Springer-Verlag, pp. 334–344, ISBN 978-3-642-11804-3, doi:10.1007/978-3-642-11805-0_32.
• Scheinerman, Edward R. (1985), "Characterizing intersection classes of graphs", Discrete Mathematics 55 (2): 185–193, DOI 10.1016/0012-365X(85)90047-0.

További információk

• Jan Kratochvíl, A video lecture on intersection graphs (June 2007)
• E. Prisner, A Journey through Intersection Graph County