En teoría de grafos, el grafo complemento o complementario de un grafo es otro grafo, con el mismo conjunto de vértices del original, y tal que dos vértices están conectados por una aristasi y solo si esa arista no existe en el primero.[1] Para obtener el complemento de un grafo, se pueden completar todas las aristas faltantes para hacerlo completo, y quitar todas las aristas del grafo G original. Note que esta definición aplica tanto para grafos dirigidos como no dirigidos.[1] Este concepto no debe confundirse con el del complemento de un conjunto, pues solo se complementan las aristas.
El grafo de Petersen (a la izquierda) y su grafo complemento (a la derecha).
Por definición, los conjuntos de aristas de un grafo y su grafo complemento forman una partición; es decir, su intersección es vacía y su unión es el conjunto de todas las aristas posibles que tendría el grafo completo del mismo número de vértices.[1]
Este tipo de grafos no debe confundirse con el grafo inverso. Si dos vértices de un grafo no están conectados por aristas, el grafo inverso conservará dicha ausencia de aristas, mientras que el grafo complemento los conectará con aristas en ambos sentidos. Asimismo, si dos vértices de un grafo dirigido están conectados en ambos sentidos, el grafo inverso conservará dichas aristas, mientras que el grafo complemento eliminará las aristas entre ambos vértices.[1]
Definición formal
Dado un grafo , con su conjunto de vértices, , y su conjunto de aristas o arcos, el grafo complemento de es el grafo definido por:
El grafo complemento se utiliza en muchos ámbitos de la teoría de grafos y en demostraciones, tales como la Teoría de Ramsey o diferentes reducciones para pruebas de NP-Completitud.
Wasserman, Stanley; Faust, Katherine (2013) [1994]. Análisis de redes sociales: Métodos y aplicaciones. Madrid: Centro de Investigaciones Sociológicas. ISBN978-84-7476-631-8. OCLC 871814053.
Datos:Q902252
Multimedia:Category:Complement graph
Noviembre 21, 2021
grafo, complemento, teoría, grafos, grafo, complemento, complementario, grafo, otro, grafo, mismo, conjunto, vértices, original, vértices, están, conectados, arista, solo, arista, existe, primero, para, obtener, complemento, grafo, pueden, completar, todas, ar. En teoria de grafos el grafo complemento o complementario de un grafo es otro grafo con el mismo conjunto de vertices del original y tal que dos vertices estan conectados por una arista si y solo si esa arista no existe en el primero 1 Para obtener el complemento de un grafo se pueden completar todas las aristas faltantes para hacerlo completo y quitar todas las aristas del grafo G original Note que esta definicion aplica tanto para grafos dirigidos como no dirigidos 1 Este concepto no debe confundirse con el del complemento de un conjunto pues solo se complementan las aristas El grafo de Petersen a la izquierda y su grafo complemento a la derecha Por definicion los conjuntos de aristas de un grafo y su grafo complemento forman una particion es decir su interseccion es vacia y su union es el conjunto de todas las aristas posibles que tendria el grafo completo del mismo numero de vertices 1 Se llama grafo autocomplementario a aquel que es isomorfo a su propio complemento Este tipo de grafos no debe confundirse con el grafo inverso Si dos vertices de un grafo no estan conectados por aristas el grafo inverso conservara dicha ausencia de aristas mientras que el grafo complemento los conectara con aristas en ambos sentidos Asimismo si dos vertices de un grafo dirigido estan conectados en ambos sentidos el grafo inverso conservara dichas aristas mientras que el grafo complemento eliminara las aristas entre ambos vertices 1 Indice 1 Definicion formal 2 Aplicaciones 3 Vease tambien 4 Referencias 5 BibliografiaDefinicion formal EditarDado un grafo G V E displaystyle G V E con V displaystyle V su conjunto de vertices n V displaystyle n V y E displaystyle E su conjunto de aristas o arcos el grafo complemento de G displaystyle G es el grafo G V E displaystyle G V E definido por V V displaystyle V V y E E K E displaystyle E E K setminus E donde E K displaystyle E K es el conjunto de aristas del grafo completo K n V E K displaystyle K n V E K Aplicaciones EditarEl grafo complemento se utiliza en muchos ambitos de la teoria de grafos y en demostraciones tales como la Teoria de Ramsey o diferentes reducciones para pruebas de NP Completitud Vease tambien EditarGrafo inversoReferencias Editar a b c d Wasserman y Faust 2013 Grafos y matrices por Dawn Iacobucci pp 121 188 Bibliografia EditarWasserman Stanley Faust Katherine 2013 1994 Analisis de redes sociales Metodos y aplicaciones Madrid Centro de Investigaciones Sociologicas ISBN 978 84 7476 631 8 OCLC 871814053 Datos Q902252 Multimedia Category Complement graph Obtenido de https es wikipedia org w index php title Grafo complemento amp oldid 135134458, wikipedia, wiki, leyendo, leer, libro, biblioteca,
