Komplementer gráf

A Wikipédiából, a szabad enciklopédiából
A Petersen-gráf a bal oldalon és komplementere a jobb oldalon

Valamely G=(V,E) gráf komplementer gráfja az a gráf, amelynek csúcshalmaza megegyezik a G gráf csúcshalmazával, az élhalmaza pedig a G gráf élhalmazának a komplementer halmaza (a teljes gráf élhalmazára, mint alaphalmazra nézve).

Definíció[szerkesztés | forrásszöveg szerkesztése]

A G=(V,E) gráf komplementere a \overline{G}:=(V,F) gráf, ha tetszőleges u, v \in V csúcsokra fennáll, hogy \big\{ u,v \big\} \in E \Leftrightarrow \big\{ u,v \big\} \not \in F

Elemi tulajdonságok[szerkesztés | forrásszöveg szerkesztése]

Egyszerű megfontolásokkal adódnak az alábbi összefüggések a komplementer gráf fokszámaira:

\deg_{\overline{G}}(u) = |V| - 1 - \deg_{G}(u), ahol u egy tetszőleges csúcsot jelöl.

illetve a komplementer gráf éleinek számosságára:

{|V|^2 - |V| \over 2}-|E|.