Arboles No Dirigidos

ARBOLES NO DIRIGIDOS


CURSO : Matematica Discreta



TRUJILLO - PERU
Árboles no dirigidos
Un árbol no dirigido es la cerradura simétrica de un árbol (véase la sección 4.7); es decir, es un árbol con todas sus aristas bidireccionales. Como se acostumbra con las relaciones simétricas, se representa un árbol no dirigido mediante su gráfica, en vez de sudígrafo. La gráfica de un árbol no dirigido T tendrá una única línea sin flechas que une los vértices a y b siempre que (a, b) y (b, a) pertenezcan a T. El conjunto {a, b}, donde (a, b) y (b, a) están en T, es una arista no dirigida de T (véase la sección 4.4). En este caso, los vértices a y b son vértices adyacentes. Así, cada arista no dirigida {a, b} corresponde a dos aristas ordinarias (a, b) y (b,a). Las líneas en la gráfica de un árbol no dirigido T corresponden a las aristas no dirigidas en T.

Ejemplo 1.
La figura 8.23(a) muestra la gráfica de un árbol no dirigido T. En la figura 8.23 (b) y (c), se muestra los dígrafos de los árboles ordinarios T₁ y T2, respectivamente, que tienen a T como cerradura simétrica. Esto muestra que un árbol no dirigido corresponde, en general, a muchosárboles dirigidos. Se incluye las etiquetas para mostrar la correspondencia de los vértices subyacentes en las tres relaciones. Observe que la gráfica de T en la figura 8.23(a) tiene seis líneas (aristas no dirigidas), aunque la relación T contiene 12 parejas.

Se quiere presentar algunas definiciones alternativas útiles de un árbol no dirigido, y para esto se necesita algunos comentarios acercade las relaciones simétricas.
Sea R una relación simétrica y sea p: v₁, v2,..., v„ una trayectoria en R. Se dice que p es simple si no existen dos aristas de p correspondientes a la misma arista no dirigida. Si, además, v₁ es igual a v„ (de modo que p sea un ciclo), p es un ciclo simple.

Ejemplo 2.
La figura 8.24 muestra la gráfica de una relación simétrica R. La trayectoria a, b, c, e, d essimple, pero la trayectoria f, e, d, c, d, a no lo es, ya que d, c y c, d corresponden a la misma arista no dirigida. También, e, a, d, b, a y d, a, b, d son ciclos simples, pero f, e, d, c, e, f no es un ciclo simple, ya que f, e y e, f corresponden a la misma arista no dirigida.

Una relación simétrica R es acíclica si no contiene ciclos simples. Se puede mostrar que si R contiene ciclos,entonces contiene un ciclo simple. Recuerde (véase la sección 4.4) que una relación simétrica R es conexa si existe una trayectoria en R desde un vértice. Hacia cualquier otro vértice.
El siguiente teorema proporciona una útil proposición equivalente a la definición anterior de un árbol no dirigido.

Teorema 1.
Sea R una relación simétrica en un conjunto A. Entonces las siguientesproposiciones son equivalentes.
(a) R es un árbol no dirigido.
(b) Res conexo aciclico.
Demostración:
Se demostrará que la parte (a) implica la parte (b), y se omitirá la demostración de que la parte (b) implica la parte (a). Suponga que R es un árbol no dirigido, lo que significa que R es la cerradura simétrica de algún árbol T en A.
Observe primero que si (a, b) ∈ R, se debe tener (a, b) ∈ T o (b,a) ∈ T. En términos geométricos, esto significa que cada arista no dirigida en la gráfica de R aparece en el dígrafo de T, dirigida en un sentido o en el otro. Por contradicción, se mostrará que R no tiene ciclos simples. Suponga que R tiene un ciclo simple p: v₁, v₂,..., v„, v₁.
Para cada arista (vi,vj) en p, se elige la pareja (vi,vj) o (vj,vi) que esté en T. El resultado es una figuracerrada con aristas en T, donde cada arista debe apuntar en una dirección. Ahora existen tres posibilidades: todas las flechas apuntan en el sentido de las manecillas del reloj, como en la figura 8.25(a), todas apuntan en sentido contrario al de las manecillas del reloj o alguna pareja aparece cómo en la figura 8.25 (b).

La figura 8.25 (b) es imposible, ya que en un árbol T, cada vértice tiene...