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,Cluster graphs, Information System on Graph Classes and their Inclusions, accessed 2016-06-26. illetve 2-levélhatványok..
Kapcsolódó gráfcsaládok Minden klasztergráf blokkgráf, kográf, továbbá karommentes gráf. 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 mindig 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,. 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..
Számítási problémák 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.. 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,. de rögzített paraméter mellett kezelhető..
Fordítás
Jegyzetek
Kategória:Gráfcsaládok Kategória:Perfekt gráfok