Klasztergráf
A matematika, azon belül a gráfelmélet területén egy klasztergráf (cluster graph) olyan gráf, mely teljes gráfok diszjunkt uniójával állítható elő. Ekvivalens definíció szerint egy gráf pontosan akkor klasztergráf, ha nem tartalmaz három csúcs hosszúságú utat feszített részgráfként; emiatt a klasztergráfokat P3-mentes gráfoknak is nevezik. A teljes többrészes gráfok komplementerei,[1] illetve 2-levélhatványok.[2]
Kapcsolódó gráfcsaládok
[szerkesztés]Minden klasztergráf blokkgráf, kográf, továbbá karommentes gráf.[1] Egy klasztergráf minden maximális független csúcshalmaza klaszterenként 1-1 csúcsot tartalmaz, ezért mérete a klaszterek számával egyezik meg; mivel minden maximális független csúcshalmaz mérete megegyezik, ezért a klasztergráfok jól fedettek. A Turán-gráfok olyan klasztergráfok komplementerei, ahol minden teljes részgráf egyenlő vagy közel egyenlő méretű. A lokálisan klaszterezett gráfok (locally clustered graphs) –, melyekben minden szomszédság egy klasztergráf – éppen a gyémántmentes gráfok, egy másik, a klasztergráfokat tartalmazó gráfcsalád. Ha egy klasztergráf klikkjei azonos méretűek, a teljes gráf homogén gráf, vagyis két feszített részgráfjának izomorfizmusát minidig ki lehet terjeszteni a teljes gráf egy automorfizmusára. Két kivételtől eltekintve (ezek a 3×3-as bástyagráf és az öt hosszúságú kör) a klasztergráfok és komponensei éppen a véges homogén gráfok,[3] a végtelen klasztergráfok viszont a megszámlálhatóan végtelen homogén gráfok sok fajtája közül csak az egyiket adják.[4]
Számítási problémák
[szerkesztés]Egy gráf részszínezése a csúcsainak feszített klasztergráfokba való particionálása. A klasztergráfok pontosan azok a gráfok, melyek részkromatikus száma 1.[5] A klaszterszerkesztés (a gráfszerkesztés alesete) számítási problémája megtalálni egy gráfhoz azt a minél kevesebb élt, melyet a gráfhoz hozzáadva vagy elvéve klasztergráffá alakítható. NP-teljes probléma,[6] de rögzített paraméter mellett kezelhető.[7]
Fordítás
[szerkesztés]- Ez a szócikk részben vagy egészben a Cluster 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 Cluster graphs, Information System on Graph Classes and their Inclusions, accessed 2016-06-26.
- ↑ Nishimura, N.; Ragde, P. & Thilikos, D.M. (2002), "On graph powers for leaf-labeled trees", Journal of Algorithms 42: 69–108, DOI 10.1006/jagm.2001.1195.
- ↑ Gardiner, A. (1976), "Homogeneous graphs", Journal of Combinatorial Theory, Series B 20 (1): 94–102, DOI 10.1016/0095-8956(76)90072-1.
- ↑ Lachlan, A. H. & Woodrow, Robert E. (1980), "Countable ultrahomogeneous undirected graphs", Transactions of the American Mathematical Society 262 (1): 51–94, DOI 10.2307/1999974.
- ↑ Albertson, M. O.; Jamison, R. E. & Hedetniemi, S. T. et al. (1989), "The subchromatic number of a graph", Discrete Mathematics 74 (1–2): 33–49, DOI 10.1016/0012-365X(89)90196-9.
- ↑ Shamir, Ron; Sharan, Roded & Tsur, Dekel (2004), "Cluster graph modification problems", Discrete Applied Mathematics 144 (1-2): 173–182, DOI 10.1016/j.dam.2004.01.007.
- ↑ Böcker, Sebastian & Baumbach, Jan (2013), "Cluster editing", The nature of computation, vol. 7921, Lecture Notes in Comput. Sci., Springer, Heidelberg, pp. 33–44, DOI 10.1007/978-3-642-39053-1_5.
