Prueba de Conectividad del gráfico

Question

Tengo la siguiente prueba: vamos a $G$ un gráfico con $n$ vértices y $n-1$ bordes, demostrar que $G$ está conectado iff $G$ no tiene ciclos.

Me proceder probar "sólo si" primero. Suponga $G$ tiene algún ciclo de consumo $|C| \le n$ vértices y $|C|$ bordes. Estamos, pues, de izquierda a intentar conectar $n-|C|$ vértices y $n-1-|C|$ bordes. Este subgrafo debe contener, al menos, $|C|+1$ componentes conectados y porque $|C| \gt 0$, $|C|+1 \gt 1$, por lo tanto, G no puede ser conectado.

Ahora probando que si $G$ no tiene ciclos, entonces se conecta. Debido a $G$ $n \epsilon N, n \gt 0$ vértices, se puede caminar a lo largo de ellos, que los conecta. Tome $v \epsilon V, v={v_1, ..., v_n}$ donde $|v|=n$. A continuación, conecte primero $v_1$$v_2$, el consumo de uno de los bordes. A continuación, conecte $v_2$ $v_3$ consumen otro borde. Continuar de esta manera hasta que $v_{n-1}$ $v_n$ están conectados, después de lo cual, $n-1$ bordes se han consumido. $v$ claramente no tiene ciclos y está conectado.

Realiza esta prueba es correcta?

Answer 1

La primera parte está bien, la segunda podría ser mejorado.

El problema es que usted necesita para probar esto para cualquier gráfica y cualquier conjunto de aristas, mientras que sugieren que agregar bordes como desee (por caminar los vértices). Usted puede hacer esto en una adecuada prueba, pero te sugiero que el otro enfoque, es decir, asumir que el gráfico no está conectado, ha $n-1$ bordes y demostrar que tiene un ciclo (hay al menos dos componentes conectados, y uno de ellos tiene el tamaño de $k$ y al menos el $k$ bordes, por lo que tiene un ciclo).

Espero que esto ayude a $\ddot\smile$

Answer 2

Esto viene casi en línea recta de uno de mis viejos cuadernos. Tal vez pueda ayudar. Creo que estamos tratando de hacer el mismo argumento.

$\textbf{Theorem:}$ Deje $G$ un gráfico con $n$ vértices y $n-1$ bordes. $G$ está conectado si y sólo si $G$ no contiene ciclos.

$\textbf{Proof:}$ Deje $G$ ser un grafo conexo con $n$ vértices y $n-1$ bordes. Supongamos $G$ contiene un ciclo de $C$ con edge $e$. A continuación, $G-e$ está conectado con $n$ vértices y $n-2$ bordes. Pero un grafo conexo con $n$ vértices debe tener al menos $n-1$ bordes, y así que esto es imposible. Por lo tanto, $G$ es acíclico.

Por el contrario, vamos a $G$ ser un gráfico acíclico con $n$ vértices y $n-1$ bordes. Deje $V_1, V_2, ...,V_k$ ser los componentes de $G$ donde cada una de las $V_i$ $n_i$ vértices ($1 \leq i \leq k$). Ya que cada gráfico de $V_i$ es acíclico, cada gráfico de $V_i$ $n_i-1$ bordes. Por lo tanto $$ n-1=\sum_{i=1}^k(n_i-1)=n-k \Rightarrow k=1. $$ Por lo tanto $G$ está conectado, y el teorema de la siguiente manera.

(mejoras están siempre anima.)

Answer 3

Un poco de topología va un largo camino. La siguiente respuesta utiliza el espíritu de la topología, pero todavía se restringe a las herramientas elementales de la finita de la teoría de grafos.

La característica de Euler $\chi(G)$ de un número finito de gráfico de $G = (V,E)$ se define a ser $\# V - \# E$. Si los componentes conectados de $G$$G_1,\ldots,G_c$,$\chi(G) = \sum_{i=1}^n \chi(G_c)$.

Lema: Para la conexión de un finito gráfico $G$, $\chi(G) \leq 1$, con la igualdad iff $G$ es un árbol.

Prueba: debido a que cada finito árbol con más de un vértice tiene un grado de un vértice, una forma fácil de "poda" argumento demuestra por inducción que cada finito árbol ha $\chi(G) = 1$. Por el contrario, si $G$ está conectado y no es un árbol, podemos eliminar un número positivo de los bordes con el fin de obtener un árbol, por lo $\chi(G) < 1$.

Ahora vamos a $c$ el número de componentes. Por hipótesis

$1 = \chi(G) = \sum_{i=1}^c \chi(G_i)$.

Si $c = 1$, luego por el Lema $G = G_1$ es un árbol. Si $c > 1$ alguna $i$ debemos tener $\chi(G_i) < 1$, y por lo tanto al menos uno de los componentes tiene un ciclo.