Cada gráfico simple no dirigido con más de

8

Si un gráfico con n vértices tiene más de (n1)(n2)2 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 |E|>n1 bordes

usuario1675999
fuente
44
pista: ¿Qué sucede si tiene un vértice aislado (no conectado a ningún otro vértice), cuál es el número máximo de aristas en el gráfico?
Joe

Respuestas:

19

No estoy seguro de lo que te molesta, pero según lo veo, estás confundido acerca de los siguientes dos hechos

  1. Si un gráfico está conectado, entonces en1.

  2. Si un gráfico tiene más de e>(n1)(n2)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 .

Jernej
fuente
7

Creo que su problema podría ser demostrar que no puede construir un gráfico no dirigido con(n1)(n2)2bordes que no están conectados. Estás pensando en eso de la manera incorrecta. losE=n1 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?

rrenaud
fuente
4

1. Como mencionaste tenemos:

G is connected|V|1|E|

Pero la otra dirección no es cierta, es decir:

G is connected|V|1|E|

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):

G=Kn1K1

G tiene (n12) bordes y n nodos y (n12)>n1 para n>4.

2. Por otro lado, para demostrar que:

(|V|12)<|E|G is connected

Podemos hacerlo de la siguiente manera:

Supongamos que no, entonces G es la unión disjunta de dos gráficos G=G1G2, con |G1|=k,|G2|=nk,0<k<n, si conectamos todos los vértices de G1,G2 juntos para hacer un gráfico G", entonces El |misol"El |(norte2) (porque sol" tiene como máximo bordes de gráfico completos) pero:

(n12)+1+k(nk)|EG"|(n2)

(k1)(nk1)+10 Contradictos con 0<k<n.


fuente
-4

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.

Yugandhar Reddy Akkisetty
fuente
1
Los árboles son gráficos conectados con sustancialmente menos de C(n1,2)bordes Supongo que querías decir que cada gráfico con más deC(n1,2)los bordes deben estar conectados. Pero incluso eso no funciona porque todo lo que ha mostrado es que un gráfico con tantos bordes no puede tener un vértice aislado: es posible desconectarse pero no tener vértices aislados. En cualquier caso, la pregunta no es realmente pedir una prueba de que cada gráfico con más deC(n1,2) bordes está conectado: se pregunta por qué n1 bordes no es suficiente.
David Richerby