Si un gráfico con vértices tiene más de bordes entonces está conectado.
Estoy un poco confundido acerca de esta pregunta, ya que siempre puedo demostrar que para un gráfico conectado necesita más de bordes
graph-theory
usuario1675999
fuente
fuente
Respuestas:
No estoy seguro de lo que te molesta, pero según lo veo, estás confundido acerca de los siguientes dos hechos
Si un gráfico está conectado, entoncese≥n−1.
Si un gráfico tiene más dee>(n−1)(n−2)2 Entonces está conectado.
Observe que las implicaciones en 1 y 2 están en direcciones opuestas.
Para una prueba de 2. puedes consultar este enlace .
fuente
Creo que su problema podría ser demostrar que no puede construir un gráfico no dirigido con(n−1)(n−2)2 bordes que no están conectados. Estás pensando en eso de la manera incorrecta. losE=n−1 fórmula sobre los pocos bordes que puedes usar para conectar todos los vértices.
Imagina que eres un adversario que intenta diseñar un horrible sistema de carreteras para que una ciudad se desconecte. No importa cuán ineficientemente gastes tus caminos, aún tendrás que conectar todas las ciudades si hay tantos caminos.
Considere cuál podría ser el peor diseño posible, por ejemplo, el que usa tantas carreteras como sea posible pero que todavía deja una ciudad desconectada. ¿Cuántos bordes tiene eso? ¿Qué sucede cuando agregas una ventaja más a eso?
fuente
1. Como mencionaste tenemos:
Pero la otra dirección no es cierta, es decir:
Es una declaración incorrecta.
Por lo tanto, no puede usarlo para seguir razonando. Ejemplo de contador de muestra es este gráfico (Kt es un gráfico completo en t vértices y ∪ significa unión disjunta de gráficos):
2. Por otro lado, para demostrar que:
Podemos hacerlo de la siguiente manera:
Supongamos que no, entoncesG es la unión disjunta de dos gráficos G=G1∪G2 , con |G1|=k,|G2|=n−k,0<k<n , si conectamos todos los vértices de G1,G2 juntos para hacer un gráfico G" , entonces El |miG "El | ≤ (norte2) (porque G " tiene como máximo bordes de gráfico completos) pero:
fuente
El gráfico G tiene n nodos n = (n-1) +1 Un gráfico que debe desconectarse debe tener al menos un vértice aislado. Un gráfico con un vértice aislado tiene un máximo de C (n-1,2) bordes.
por lo que cada gráfico conectado debe tener más de C (n-1,2) aristas.
fuente