A matematika, azon belül a gráfelmélet területén egy Ggráfkomplementere(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.
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:
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 ö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.
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.
