Tengo que demostrar que existe un conjunto finito de grafos planares con la propiedad de que el grafo G es isomorfo con su complemento gráfico.Me puedes dar algunas sugerencias o consejos ?Gracias
Respuesta
¿Demasiados anuncios?
Ralf
Puntos
113
Pido disculpas por la publicación de la respuesta completa. De alguna manera me perdí que sólo necesitan consejos. Os dejo la respuesta completa a continuación y dan algunos consejos aquí.
- Sugerencia 1 żcuántas aristas hace un auto-complementarios gráfico?
- Sugerencia 2 ¿cuáles son las implicaciones de la fórmula de Euler para los grafos planares?
Solución completa de la siguiente manera.
Deje $G$ ser un auto-complementarios gráfico de la orden de $n.$ $G$ $\frac{n(n+1)}{4} = \mathcal{O}(n^2)$ bordes. Pero a partir de Euler de la fórmula, todos los grafos planares ha $\mathcal{O}(n)$ bordes. Por lo tanto, hay sólo un número finito de auto-complementarios grafos planares.
Para ser más precisos, de Euler fórmula implica que para que un plano gráfico de $G$ orden $n \geq 3$ hemos $$|E(G)| \leq 3n-6$$ hence if $G$ is self complementary we have $$ \frac{n(n+1)}{4} \leq 3n-6$$ which implies $3 \leq n \leq 8.$ Por lo tanto, una auto-complementarios plano gráfico puede tener en la mayoría de los 8 vértices.
Como parece que hay sólo 14 de los gráficos de este tipo y que se puede ver en la figura adjunta!
