Comencemos con una definición de una entidad llamada como Árbol.
Definición 1:
Un árbol es un gráfico simple conectado sin ciclos. Una hoja es un vértice de grado 1.
- Cómo aprender qué algoritmo usar en un conjunto de problemas en particular
- ¿De qué juez en línea puedo aprender algoritmos estándar y estructuras de datos?
- ¿Qué son los algoritmos gráficos?
- ¿Existe un algoritmo que pueda combinar y separar números?
- ¿Cuál es el mejor algoritmo para encontrar si 3 números son coprimos? ¿Como funciona?
Lema 1:
Un árbol en más de un vértice contiene una hoja.
Prueba: consideramos un camino más largo posible en un árbol [math] T [/ math]. Como no hay ciclos en [matemática] T [/ matemática], los vértices finales de esta ruta no deben tener otros bordes incidentes con ellos (de ahí el grado uno).
Teorema 1:
Un árbol de vértices [matemático] n – [/ matemático] tiene exactamente bordes [matemático] n – 1 [/ matemático] para [matemático] n ≥ 1 [/ matemático] .
Prueba: por inducción en [matemáticas] n [/ matemáticas].
Un árbol de un vértice tiene [matemática] n – 1 = 0 [/ matemática] borde (s)
Deje que un árbol [matemática] T [/ matemática] tenga vértices [matemática] n> 1 [/ matemática]. Por el Lema 1 , [matemáticas] T [/ matemáticas] tiene un vértice [matemáticas] v [/ matemáticas] de grado [matemáticas] 1 [/ matemáticas]. Denote con [math] T ′ = T −v [/ math] la subgrafía obtenida de [math] T [/ math] eliminando [math] v [/ math]. Entonces [math] T ′ [/ math] también está conectado y es acíclico, y por lo tanto [math] T ′ [/ math] es un árbol en vértices [math] n − 1 [/ math].
Por supuesto de inducción, [matemática] T ′ [/ matemática] tiene [matemática] n – 1 – 1 [/ matemática] bordes, y entonces [matemática] T [/ matemática] tiene [matemática] n – 1 – 1 + 1 = n – 1 [/ matemática] bordes.
Teorema 2: dos vértices de un árbol están conectados a través de exactamente una ruta.
Prueba: dado que un árbol [matemático] T [/ matemático] está conectado por la definición, cualquiera de los dos vértices [matemático] u, v [/ matemático] están conectados a través de una ruta. Si hubiera dos caminos distintos [matemática] P1, P2 [/ matemática] entre [matemática] u, v [/ matemática], entonces su diferencia simétrica (conjuntos de bordes wrt) —un subgrafo [matemático] H = P1∆P2 [/ matemática] del conjunto de bordes no vacío: tiene todos los grados pares y no todos cero. Por otro lado, [matemática] H [/ matemática] como un subgrafo de un árbol es acíclico, y por lo tanto sus componentes son árboles (no todos los vértices aislados), y según el Lema 1 tiene que haber un vértice de grado [matemática] 1 [/ math] en [math] H [/ math], una contradicción.
Corolario 1:
Si se agrega un solo borde nuevo a un árbol, esto da como resultado la creación de exactamente un ciclo.
Prueba: si [math] u, v [/ math] no son vecinos en un árbol [math] T [/ math], entonces el nuevo borde [math] uv [/ math] forma un ciclo con el único [math] u −v [/ math] ruta del teorema 2.
Por lo tanto, según el Corolario 1 , podemos decir que un gráfico conectado con nodos [math] n [/ math] y más de los bordes [math] n-1 [/ math] debe contener el ciclo. [matemáticas] \ blacksquare [/ matemáticas]
Por un lado divertido, a veces las ramas de los árboles (cosas verdes vivas) crecen juntas para formar bucles. Los árboles (jerga matemática) son gráficos sin bucles.
Aclamaciones
