Un grafo simple no dirigido es conexo si existe un camino entre cada par de vértices del grafo. Prueba: si H es un grafo simple conexo no dirigido con n vértices, entonces H tiene ≥ n - 1 aristas. Usa la inducción.
El profesor tiene la habilidad de dar problemas de práctica que combinan múltiples conceptos. No sé cómo empezar a utilizar la inducción para demostrar el problema anterior. Se agradece cualquier ayuda.
¿Se mantiene el resultado para 2 vértices? Pregúntate, ¿cuántas aristas tiene un grafo conectado con 2 vértices? ¿Es al menos $n-1=2-1=1$ ?
Ahora, supongamos que tienes un gráfico conectado en $n$ vértices donde $n>2$ . Elimina con cuidado un vértice que no desconecte el gráfico (debes convencerte a ti mismo, y al lector de tu prueba, de que esto es posible o utilizar algún teorema de tu texto/notas) di $G-v$ está conectado. $G-v$ tiene un vértice menos, así que por inducción tiene al menos $(n-1)-1$ bordes. Añada $v$ de nuevo junto con todas esas aristas que inciden en $v$ (¿Cuál es el menor número de aristas añadidas en este paso?). Ahora, cuente (obtenga un límite inferior) el número de aristas en $G$ . Es de esperar que el número de aristas sea al menos $n-1$ .
Demostrar el caso n=1 es sólo dar un ejemplo, así que te lo dejo a ti.
Se puede subdividir un gráfico en subgráficos con enlaces entre ellos. Así, si $H_{n+1}$ es un gráfico de n+1 nodos se puede considerar como dos gráficos de $H_n$ y $H_1$ . Como el gráfico es conexo, debe haber al menos una arista entre $H_n$ y $H_1$ .
Así que su paso inductivo es asumir que $H_n$ tiene al menos (n-1) nodos. Entonces $H_{n+1}$ debe tener una arista más para unir los subgráficos.
Creo que la inducción fuerte podría ser el mejor enfoque aquí, para evitar tener que encontrar un vértice no cortado (un vértice que, cuando se elimina junto con sus aristas incidentes, no desconecta el gráfico). Las pruebas de inducción requieren una familia de proposiciones $P(n)$ , indexado por números naturales $n$ . Normalmente me resulta más fácil definirlo explícitamente:
$P(n) :$ Para todo gráfico conectado $G$ con $n$ vértices, $G$ tiene al menos $n - 1$ bordes.
Tenemos que demostrar $P(1)$ primero. Es decir, si $G$ es un gráfico conectado con $1$ vértice, entonces $G$ tiene al menos $0$ bordes. Esto es evidente en cualquier gráfico, no sólo en los conectados con $1$ vértice, por lo que $P(1)$ es cierto.
Suponemos ahora que, para un $n > 1$ , $P(k)$ es cierto para todos los $k < n$ , y proceder a demostrar $P(n)$ . Tenemos que demostrar que, dada cualquier conexión $G$ gráfico con $n$ vértices, tenemos al menos $n - 1$ aristas, así que supongamos que tenemos un gráfico $G$ que se ajustan a estas premisas.
Tome cualquier vértice $v$ de $G$ y la borramos, junto con todas sus aristas incidentes, para formar un nuevo gráfico $G'$ . Tenga en cuenta que $v$ no puede tener grado cero, porque entonces no estaría conectado al resto del gráfico. No podemos suponer $G'$ está conectada (lo que sería útil, para poder aplicar $P(n - 1)$ ), pero lo que podemos hacer es considerar los componentes conectados de $G'$ . Sea $G_1, G_2, \ldots, G_m$ sea el número de componentes conectados de $G$ . Para cada $i = 1, \ldots, m$ , dejemos que $n_i$ y $e_i$ sea el número de vértices y aristas respectivamente de $G_i$ .
Tenga en cuenta que $G'$ tiene $n - 1 = n_1 + \ldots + n_m$ vértices y $e_1 + \ldots + e_n$ bordes. En particular, $n_i < n$ para todos $i = 1, \ldots, m$ . Por lo tanto, podemos utilizar nuestra hipótesis de inducción y concluir que $P(n_i)$ es cierto para todos los $i$ . Es decir, $e_i \ge n_i - 1$ . Resumiendo, tenemos, $$n - 1 = n_1 + \ldots + n_m = (n_1 - 1) + \ldots + (n_m - 1) + m \le e_1 + \ldots + e_m + m$$ Desde la eliminación de $v$ creado $m$ componentes conectados, se deduce que $v$ debe haber tenido al menos $m$ aristas incidentes en ella (al menos una arista debe haberse conectado a cada componente conectado de $G'$ para conectarlos todos en $G$ ). Por lo tanto, si $e$ es el número de aristas en $G$ tenemos $$n - 1 \le e_1 + \ldots + e_m + m \le e,$$ como se requiere. Así, por inducción (fuerte), $P(n)$ es válida para todos los $n$ .
Este no es el tipo de prueba que buscas (ver la respuesta de Paddling Ghost para ello) porque no utiliza la inducción.
Dejemos que $V(H)=\{v_0,v_1,v_2,\dots,v_{n-1}\}.$
Para cada $i\in\{1,2,\dots,n-1\},$ elegir un vértice $w_i$ para que $v_iw_i$ es la primera arista de un camino más corto desde $v_i$ a $v_0;$ en otras palabras, $w_i$ es vecino de $v_i$ tal que $d(w_i,v_0)\lt d(v_i,v_0).$
Para terminar la prueba, demuestre que las aristas $v_iw_i\ (i=1,2,\dots,n-1)$ son distintos. (En otras palabras, si se pasa de $v_i$ a $v_j$ es el primer paso en un camino más corto desde $v_i$ a $v_0,$ y luego pasar de $v_j$ a $v_i$ no puede ser el primer paso en un camino más corto desde $v_j$ a $v_0.$ )
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
