Un grafo es autocomplementario si es isomorfo a su complemento. Para todos los gráficos autocomplementarios en n vértices, n es
(A) Un múltiplo de 4
(B) Par
(C) Impar
(D) Congruente con 0 mod 4, o 1 mod 4
Respuesta: (D)
Explicación: Un gráfico autocomplementario de n vértices tiene exactamente la mitad del número de aristas de el gráfico completo, es decir, n(n − 1)/4 aristas, y (si hay más de un vértice) debe tener un diámetro de 2 o 3. Dado que n(n −1) debe ser divisible por 4, n debe ser congruente con 0 o 1 mod 4; por ejemplo, un gráfico de 6 vértices no puede ser autocomplementario.
Fuente: http://en.wikipedia.org/wiki/Self-complementary_graph
Prueba de esta pregunta
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA