Diferencia entre revisiones de «Grafo complemento»

[[Archivo:Complement_graph_sample.png|derechathumb|UnEl [[grafo de Petersen]] (a la izquierda) y su grafo complemento (a la derecha).]]

En [[teoría de grafos]], el '''grafo complemento''' o '''inversocomplementario''' de un [[grafo ''G:=(V,E)'']] es unotro grafo ''G':=(V,E')'', con el mismo conjunto de [[vértice (teoría de grafos)|vértices]] del original, y tal que dos vértices dedel ''G'nuevo ''grafo son ''[[arista (teoría de grafos)|adyacentes'']] [[bicondicional|si y solo si]] no son adyacentes en ''G''el primero.<ref name=WF13.c4>{{harvsp|Wasserman|Faust|2013|loc=«Grafos y matrices» (por Dawn Iacobucci), pp. 121-188.}}</ref> Para obtener el complemento de un grafo, se deben completar todas las aristas faltantes para hacerlo [[grafo completo|completo]], y quitar todas las aristas del grafo ''G'' original. Este concepto no debe confundirse con el del [[complemento de un conjunto]], pues solo se complementan las aristas.