Komplementer gráf

A matematika, azon belül a gráfelmélet területén egy G gráf komplementere (complement) alatt azt a H gráfot értjük, melynek csúcsai megegyeznek G csúcsaival, és két csúcs pontosan akkor szomszédos H-ban, ha azok nem szomszédosak G-ben. Vizuálisan, egy gráf komplementerének előállításához be kell húzni a teljes gráfhoz szükséges éleket, majd kitörölni az addig jelen lévőket.^[1] A gráf komplementere nem egyezik meg a gráf halmazelméleti komplementerével, hiszen csak az élhalmaz komplementerét képezzük.

A Petersen-gráf (balra) és komplementere (jobbra).

Definíció

Legyen G = (V, E) egyszerű gráf és K álljon V összes kételemű részhalmazából. Ekkor H = (V, K \ E) megegyezik G komplementerével,^[2] ahol K \ E az E halmaz K-ra vonatkozó (halmazelméleti) komplementere. Irányított gráfokban a komplementert hasonlóan definiálhatjuk, csak az előző képletben kételemű részhalmazok helyett a kételemű rendezett párokat kell venni. Multigráf komplementere nem definiált. Az olyan gráfokban, melyekben a hurok megengedett (de többszörös élek nem), G komplementere esetleg definiálható az előzőekhez képest azzal a kiegészítéssel, hogy a hurkot nem tartalmazó csúcsokhoz a komplementer gráfban hurkot adunk és megfordítva; ez azonban már jelentősen különbözne az egyszerű gráfokon értelmezett komplementerképzés műveletétől.

Alkalmazások és példák

A komplementerképzés művelete több gráfelméleti fogalmat párba állít:

• Az élmentes gráf komplementere a teljes gráf, és viszont.
• A G gráf komplementerének bármely feszített részgráfja megegyezik a G-ben neki megfelelő feszített részgráf komplementerével.
• Egy gráf bármely független csúcshalmaza a komplementer gráfban klikket alkot és vice versa. Ez voltaképpen az előző két fogalompár speciális esete, hiszen egy független csúcshalmaz egy élmentes feszített részgráf, a klikk pedig egy teljes feszített részgráf.
• Egy gráf automorfizmuscsoportja a komplementer gráf automorfizmuscsoportja is.
• Minden háromszögmentes gráf komplementere karommentes gráf,^[3] bár az állítás fordítottja nem igaz.

Önkomplementer gráfok és gráfosztályok

A négy csúcsból álló út önkomplementer.

Bővebben: Önkomplementer gráf

Egy önkomplementer gráf olyan gráf, ami izomorf saját komplementerével.^[1] Példa erre a négy csúcs hosszúságú útgráf és az öt hosszúságú körgráf. Számos gráfcsalád tekinthető önkomplementernek, abban az értelemben, hogy a családba tartozó bármely gráf komplementere is a családba tartozik.

• Egy perfekt gráf olyan a gráf, melynek minden feszített részgráfjának kromatikus száma megegyezik a maximális klikkjének méretével. Lovász László perfektgráf-tétele értelmében minden perfekt gráf komplementere is perfekt.^[4]
• A kográfok azok a gráfok, melyek egyetlen csúcsból kiindulva előállíthatók a komplementerképzés és a diszjunkt unió gráfműveletek segítségével. Önkomplementer gráfcsaládot alkotnak, bármely kográf komplementere egy másik kográf. Mivel az egynél több csúcsú kográfok esetében egy komplementer-kográfpárosból mindig csak egy gráf összefüggő, ezért a kográfok egy ekvivalens definíciója szerint minden összefüggő feszített részgráfjuk komplementere nem összefüggő. Egy másik, önkomplementer definíció szerint a kográfok azok a gráfok, melyek nem tartalmazzak a négy csúcsból álló utat feszített részgráfként.^[5]
• Egy másik önkomplementer család a split gráfoké; ezek a gráfok, melyek csúcsai egy klikkbe és egy független csúcshalmazba particionálhatók. Ugyanez a partíció a komplementer gráfban is egy független halmazt, illetve klikket ad.^[6]
• A küszöbgráfok azok a gráfok, melyek egyetlen csúcsból kiindulva előállíthatók egy független (szomszédok nélküli) csúcs, illetve egy univerzális csúcs (minden korábbi csúccsal szomszédos csúcs) hozzáadásának műveleteivel. Ez a két művelet komplementer jellegű, és együtt gráfok önkomplementer családját állítják elő.^[7]

Algoritmikus aspektusok

A gráfalgoritmusok analízise során a gráf és komplementere közötti különbségtétel általában lényeges, hiszen egy ritka gráf (a csúcsaihoz képest kevés éllel rendelkező gráf) komplementere általában nem ritka, ezért egy a gráf éleinek számával arányos algoritmus a ritka gráf komplementerének valamely explicit reprezentációján sokkal hosszabb ideig futhat. Ezért a kutatók olyan algoritmusokat is vizsgálnak, melyek a gráfokkal kapcsolatos számításokat a bemeneti gráf komplementerén végzik, egy olyan implicit gráfreprezentációt felhasználva, melyhez nem szükséges a komplementer gráf explicit megkonstruálása. Lehetséges például a komplementer gráfon akár mélységi, akár szélességi keresést végezni a gráf mérete szerint lineáris időben, még akkor is, ha a komplementer gráf mérete sokkal nagyobb.^[8] Ezek a szimulációk használhatók a komplementer gráf összefüggőségét érintő egyéb tulajdonságok számításánál is.^[8][9]

Fordítás

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