Loading AI tools
Från Wikipedia, den fria encyklopedin
En komplementgraf är inom matematik, specifikt grafteori, en graf som konstrueras utifrån en given graf G genom att låta graferna ha samma nodmängd, men att två noder i komplementgrafen har en båge mellan sig om och endast om de inte har en båge mellan sig i G.
Om är en graf och K består av alla delmängder av N med två element så är komplementgrafen till G:
Observera att en komplementgraf inte är detsamma som ett mängdteoretiskt komplement.
Flera grafteoretiska koncept är varandras motsatser sett i komplementgrafer. En bågfri grafs komplementgraf är en komplett graf, en oberoende mängd i en graf blir en klick i dess komplementgraf, en triangelfri graf blir en klofri graf.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.