A matematika, azon belül a gráfelmélet területén egy gráf komplementere (complement) alatt azt a gráfot értjük, melynek csúcsai megegyeznek csúcsaival, és két csúcs pontosan akkor szomszédos -ban, ha azok nem szomszédosak -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.. 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 egyszerű gráf és álljon összes kételemű részhalmazából. Ekkor megegyezik komplementerével,. Electronic edition, page 4. ahol az halmaz -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), 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 gráf komplementerének bármely feszített részgráfja megegyezik a -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,. bár az állítás fordítottja nem igaz.
Önkomplementer gráfok és gráfosztályok
Egy önkomplementer gráf olyan gráf, ami izomorf saját komplementerével. 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.. 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.. 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.. 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ő..
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. 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...
Fordítás
Jegyzetek
Kategória:Gráfműveletek