Unidad 2 Arboles Redes 2017 PDF

Preview

Summary

Download Unidad 2 Arboles Redes 2017 PDF

Description

Mag. Nancy Alonso – MSc. Elisa Oliva

MATEMÁTICA DISCRETA L.S.I.-L.C.C.

ÁRBOLES – REDES 2–1

Árboles arraigados

Los árboles arraigados, las redes de transporte y las redes de Petri se presentan a continuación como aplicación de la Teoría de Grafos.

Definición Un árbol arraigado de raíz v 0 es un grafo dirigido G  ( V, R) que verifica: 1. Existe un vértice v 0 , denominado raíz del árbol que no admite trayectorias en sí mismo. 2. Para cada vértice vi  v 0 , existe una única trayectoria Tvo vi en el grafo G. Notamos con dist(v0 , v i )  longTv 0v i , donde Tvo vi es la que menciona la definición.

Elementos de un árbol arraigado Raíz -

•

Vértice v 0 que destaca la definición. Vástago - Si (v i , v j )  R , el vértice v j es un vástago, sucesor o hijo del vértice v i .

•

Hoja (vértice terminal) -

•

Vértice interno - Vértice que no es raíz ni hoja.

•

Nivel 0 -

•

Nivel 1 - Conjunto de vástagos de la raíz.

•

Nivel k - Conjunto de vástagos de los vértices del nivel k1 v i Nivel k  dist( v 0, v i )  k . Altura de G: max { dist( v 0, vi ) ,viV}. Si el árbol tiene k+1 niveles, la altura es k.

•

•

Vértice que no tiene vástagos.

Conjunto unitario cuyo elemento es la raíz del árbol.

Ejemplo 1 Determinamos elementos del siguiente árbol arraigado. Raíz b.

G  ( V,R)

b

Hojas a, e, d, q, s, h.

Vértices internos c, f y g Nivel 0 = {b}

Nivel 1={a,c,e}

Nivel 2 = {d,g,f}

Nivel 3 = {q,s,h}.

a

c

e

d

g

f

q

s

h

Altura = máx {dist (b,vi), viV} = 3 (último nivel)

Unidad 2  1

Mag. Nancy Alonso – MSc. Elisa Oliva

MATEMÁTICA DISCRETA L.S.I.-L.C.C.

Si en un árbol arraigado los vástagos de un vértice se denominan “hijos” entonces: 

Cada vértice v i distinto de la raíz v 0 , tiene un único padre. Las hojas no tienen hijos.



Los vértices, que no son hojas, pueden tener uno o más hijos.



Los vástagos de un mismo vértice se denominan “hermanos”.



Si ( v i, v j ) es un arco, v i es “antecesor” de v j y v j “sucesor” de v i .



“Descendientes” de v h , vértices v k para los que existe una trayectoria Tvhvk .



“Antepasados” de v h , vértices v k para los que existe una Trayectoria Tvk vh .

Ejemplo 2 Información que se extrae de la trayectoria Tv iv j  vi , x1,..., xn 1, v j de un árbol arraigado

vi



v i es padre (antecesor) de x1 , x k es padre de x k 1 .



x1 es hijo (sucesor) de v i y cada vértice xk 1 es hijo de x k .



vi , x1 , x2 ,..., x n1 son antepasados de v j , si vi  v 0 pueden

xk

x k1

xn1

vj

existir otros antepasados. 

Tviv j

x1

x 1, x 2,..., xn 1, v j son descendientes de v i . Si v j no es hoja, si vi o algún xi tiene más de un vástago, pueden existir otros descendientes de vi.

Subárbol arraigado Definición Un subárbol con raíz v i , de un árbol G, es el árbol con raíz v i y sus descendientes. Para construir un subárbol de raíz vi consideramos todos los vértices vj para los que existe una trayectoria Tviv j en el árbol G, que son descendientes de vi.

Ejemplo 3 Subárbol de raíz c c

Mostramos subárboles del árbol arraigado G  ( V, R) . G  ( V,R)

b a

c

e

d

g

f

q

s

h

Subárbol de raíz g g Subárbol de raíz f h f q s h

d q

g s

f h

Unidad 2  2

Mag. Nancy Alonso – MSc. Elisa Oliva

MATEMÁTICA DISCRETA L.S.I.-L.C.C.

Propiedades geométricas de árboles arraigados Las siguientes propiedades geométricas se demuestran aplicando el método de reducción al absurdo (se niega la tesis, se utiliza la hipótesis y se llega a una contradicción).

Proposición 1 En un árbol arraigado G se verifican las siguientes propiedades 1.-

La raíz del árbol arraigado es única.

2.-

La raíz no tiene entradas

3.-

Todo vértice vi  v 0 tiene sólo una entrada.

4.-

G es un grafo acíclico.

Demostración H) G  ( V, R) árbol arraigado de raíz v 0

1.-

T) La raíz v 0 de G es única

Suponemos T) , existirán por lo menos dos raíces distintas v 0 y v 0 . Si v 0 es raíz, como v0  v 0 en el árbol existe Tv 0v 0 (1).

v0

Si v es raíz, como v 0  v , en el árbol existe Tv 0v 0 (2).  0

T v0 v*0

* 0

v *0

Tv * v

0 0

Componiendo las trayectorias de (1) y (2) obtenemos Tv 0 v0  Tv *0v 0 =Tv 0 v 0 , trayectoria de

v 0 en sí misma, luego v 0 no puede ser raíz del árbol y si lo era, esta contradicción provino de suponer que existe más de una raíz, por lo tanto la raíz es única. 2.-

H) G  ( V, R) árbol arraigado de raíz v 0

c.q.d.

T) La raíz no tiene entradas.

Suponemos T) , por lo tanto existe una entrada vk  v 0 a la raíz v 0 , esta entrada Tv 0v k Tv 0v 0 determina una trayectoria Tvk v 0 de longitud 1 (1) v0 vk Como vk  v 0 , por H) existe Tv0 vk (2) v 0 Tvk v 0 Componemos (2) y (1): Tv 0v k  Tv k v 0  Tv 0v 0 trayectoria de v 0 en sí misma y en un árbol no pueden existir trayectorias Tv 0v 0 , la contradicción provino de suponer que la raíz v 0 tiene entrada, por lo tanto no las tiene. 3.-

H) G  ( V, R) árbol arraigado de raíz v 0

c.q.d. T) Todo vértice v i  v 0 tiene sólo una

entrada. Suponemos T) , existe por lo menos un vértice vi  v 0 con dos entradas (vh, v i ) y (v k , v i ) , luego existen trayectorias Tvhvi y Tvk vi (1) Suponemos v k  v 0 y v h  v 0 , si una de las entradas es v 0 , la demostración es válida. por H) existen trayectorias Tv ov k y Tv ov h (2) , ver diagrama.

Tv ov h

Componemos trayectorias de (2) y (1): Tvovk  Tvk vi = Tv ov i 

vh

v0

Tvov k vk

Tv h vi vi2  Tv3v Unidad k i

Mag. Nancy Alonso – MSc. Elisa Oliva

MATEMÁTICA DISCRETA L.S.I.-L.C.C.

Tv ovh  Tvh vi = Tvo vi Encontramos dos trayectorias distintas desde v 0 a v i , contradice la unicidad de la trayectoria entre ellos y provino de suponer que v i tiene más de una entrada por lo tanto cada vértice vi  v 0 tiene sólo una entrada. 4.-

H) G  ( V, R) árbol arraigado de raíz v 0

c.q.d. T) G es acíclico (no admite ningún ciclo).

Suponemos T) , existe un ciclo Tv iv i  vi , x1,..., xn 1, vi

v0

Tv ov i

Por ser árbol no existe Tvo v 0 , luego vi  v 0. Por H) existe trayectoria Tv ov i .

* v 0v i

Tviv i

vk

vi

vh

T

Componemos Tv ov i con el ciclo Tv iv i , obtenemos Tv*0 v i  Tv0 vi  T vi vi .

Tv ov i y Tvo vi son distintas desde v 0 a v i , contradice que existe sólo una y provino de suponer que existe un ciclo, por lo tanto G es acíclico.

c.q.d.

Nota Se puede probar que en un árbol arraigado G  ( V, R) , su relación R tiene las siguientes propiedades: 1.-

Es irreflexiva, ningún vértice se relaciona consigo mismo, v i : (v i, v i )  R .

2.-

Es asimétrica.

3.-

No es transitiva

4.-

Es antisimétrica

Método matricial para analizar si un grafo es árbol arraigado El siguiente método permite analizar si G  ( V, R) es árbol arraigado. Las propiedades geométricas de un árbol arraigado permiten distinguir características de la matriz asociada MG  (rij ) , y de la matriz MR   (rij ) de conectividad. 1. Si un árbol G=(V,R) tiene n vértices, tiene n  1, MG  (rij ) tiene (n–1) unos. 2. En MG  (rij ) sólo la columna de la raíz tiene todos ceros.

Propiedad: “La raíz no tiene entradas y es única”. 3. Cada columna distinta de la que tiene todos ceros, tiene sólo un 1 fuera de la

diagonal principal. Propiedad: “Cada vértice vi  v0 tiene sólo una entrada y la relación es irreflexiva”

Unidad 2  4

Mag. Nancy Alonso – MSc. Elisa Oliva

4.

Si MG  (rij )

MATEMÁTICA DISCRETA L.S.I.-L.C.C.

tiene 1 en el lugar i,j tiene 0 en el lugar j,i, verifica

i j(i  j): (rij  1  rji  0) . Propiedad: La relación R del grafo es antisimétrica.   5. La diagonal principal MR   (rij ) verifica i :rii  0, tiene solamente ceros.

Propiedad: “El árbol es acíclico, no existe ningún lopp (ciclo Tv iv i )”.

Tipos de árboles 

Etiquetado: Tienen vértices y/o arcos con etiquetas o nombres.



n-ario: Los vértices, que no son hojas, tienen a lo sumo n vástagos.



n-ario completo: Todos los vértices, que no son hojas, tienen n vástagos.



Ordenado: Sólo si se ha prefijado un orden en su conjunto de vértices, por niveles o por ramas. La búsqueda se realiza según el tipo de orden, 1.

Vértices ordenados por niveles: Se preceden de izquierda a derecha.

2.

Vértices ordenados por ramas: Se preceden desde la raíz a la hoja.

Ejemplo 4 Clasificamos los árboles arraigados G1, G2 , G3 y G4. G2 G3 G1 0 Ordenado por ramas

b

1

4

5

Ordenado c por niveles

3

2

6

G4

a a1 a3

d

e

f

g

a2 a4

7

a5

8

G1 Es 3-ario (ternario) completo, todos los vértices con vástagos, tienen 3. No es etiquetado (vértices y arcos sin etiquetas) G2 Es 4-ario (cuaternario) no completo, el vértice que tiene más vástagos tiene 4 (no todos tienen 4). Es etiquetado (vértices con etiquetas). Es Ordenado por ramas, se verifica 0  3  7  8; 0  3  6 .... . G3 Es 2-ario (binario) completo, todos los vértices con vástagos tienen 2 vástagos. Es etiquetado (vértices con etiquetas). Es Ordenado por niveles, se verifica b  c ; d  e ; f  g . G4 Es 2-ario (binario) no completo, el vértice con más vástagos tiene 2 vástagos (no todos tienen 2). Es etiquetado (arcos con etiquetas). No es ordenado.

Unidad 2  5

Mag. Nancy Alonso – MSc. Elisa Oliva

MATEMÁTICA DISCRETA L.S.I.-L.C.C.

Árboles de expresiones algebraicas Para representar las expresiones algebraicas, en sus operaciones se tiene en cuenta el uso de paréntesis y la prioridad para resolver una operación antes que otra. Por ejemplo, en el álgebra de números, si no existen paréntesis, resolvemos primero producto y luego suma, en el álgebra de conjuntos resolvemos intersección antes que unión ... etc.

Reglas de construcción de un árbol algebraico El árbol arraigado que representa una expresión algebraica tiene raíz y vértices internos etiquetados con operaciones del álgebra y hojas etiquetadas con elementos del portador. 1.- La raíz del árbol se etiqueta con la operación principal de la expresión algebraica Arbol de: 1+(… …)

2.- Si la etiqueta de un nodo es una operación binaria, se dibujan

+

dos vástagos, ver diagrama, un vástago con 1 y el otro con “ ”. 

1

Las etiquetas de los vástagos dependen de los miembros que componen la operación, si es una expresión algebraica se etiqueta con la operación principal, si es hoja se etiqueta con un elemento del álgebra. 3.- Si la etiqueta de un nodo es una operación unitaria se dibuja sólo un vástago. La etiqueta de este vástago es un elemento (hoja) o es una expresión algebraica, en este segundo caso la etiqueta es la operación principal. Por ejemplo, para las expresiones lógicas A y ( A  B ): Para A

─

Para A  B

─



A A

B

4.- Finaliza el proceso cuando todas las ramas finalizan en hojas etiquetadas con un elemento del álgebra.

Unidad 2  6

Mag. Nancy Alonso – MSc. Elisa Oliva

MATEMÁTICA DISCRETA L.S.I.-L.C.C.

NOTA.- En la construcción de un árbol algebraico, se respeta la expresión algebraica y se tiene en cuenta la prioridad de paréntesis, para que exista sólo un árbol para esa expresión. Si se permite utilizar expresiones equivalentes, para evitar abrir menos ramas, el árbol no es único.

Ejemplo 5 Construimos un árbol arraigado para cada expresión algebraica. 1) ( a  bx)  ( ( x  b )  (a  y ) ) en el conjunto R de números reales 2) (C  F)  (D  (E  C)

(lógica proposicional)

Árbol de (a  bx)  ( ( x  b)  ( a  y) )

Árbol de (C  F)  (D  (E  C) _

+ _

_ a





b

x x

→

+ b a

→



y

C

_

F



D E

_

C

Arboles Lógicos Una variable lógica puede ser una Proposición del Cálculo Proposicional o una Fórmula clausurada del Cálculo de Predicados de Primer Orden (desarrollaremos más adelante). Convenimos que: 

Sólo el uso de paréntesis da prioridad a algunas operaciones sobre otras.



Cuando interviene la operación binaria y hay más de dos elementos, se necesitan paréntesis que asocien de a dos. Por ejemplo A  B  C  ( A  B)  C 

A  (B  C) y

A  B  E  C  ( A  B)  (E  C) (por prioridad), aunque esta

última se podría pensar que representa A  ((B  E)  C) o (( A  B)  E)  C … 

Sólo reemplazaremos una expresión por otra equivalente si se evita construir más ramas.

Unidad 2  7

Mag. Nancy Alonso – MSc. Elisa Oliva

MATEMÁTICA DISCRETA L.S.I.-L.C.C.

Reglas de Construcción de un Árbol Lógico El árbol lógico (arraigado) que representa una expresión lógica tiene raíz etiquetada con la expresión lógica y vértices internos etiquetados con expresiones lógicas o variables lógicas, sus hojas se etiquetan con variables lógicas y/o contradicciones. Una hoja se etiqueta con una contradicción si en esa rama interviene una variable y su negación. Utilizamos símbolos A y B para representar variables y/o expresiones lógicas. Conjunción

Disyunción

A B

Condicional

A B

Bicondicional

A B

A B

A B

A

B

B

A

A B

A B A

A

B

B

NOTA.- En la construcción de un árbol algebraico, se respeta la expresión algebraica y se tiene en cuenta la prioridad de paréntesis, para que exista sólo un árbol para esa expresión. Si se permite utilizar expresiones equivalentes, para evitar abrir meno s ramas, el árbol no es único.

Ejemplo 6 Construimos

el

árbol

lógico

para

las

expresiones

F  (E  (B  C))

y

(D  E)  ((F  G)  C ). Árbol lógico de F  (E  (B  C))

Árbol lógico de (D  E)  ((F  G)  C )

F  (E  (B  C))

(D  E)  ((F  G)  C )

F

D E (F  G)  C

E  (B  C) E

BC B

C

FG F G F G D E

C D E

D E

D E

Unidad 2  8

Mag. Nancy Alonso – MSc. Elisa Oliva

MATEMÁTICA DISCRETA L.S.I.-L.C.C.

Aplicación de árboles arraigados en la codificación Código de Huffman Los caracteres y símbolos se representan en una computadora con cadenas de bits de longitud fija, el código ASCII (American Estándar Code For Information Interchange) representa a cada caracter con un arreglo de siete bits. El código de Huffman representa los caracteres con cadenas de 0 y/o 1 de longitud variable, tiene prefijado un alfabeto cuyos símbolos están codificados con estas cadenas. Cada código de Huffman se define por medio de un árbol arraigado binario completo, ordenado, con hojas etiquetadas con símbolos del alfabeto y las siguientes características. 

La raíz y vértices internos no están etiquetados.



Las hojas están etiquetas con símbolos del alfabeto.



Cada vértice, no hoja, tiene dos vástagos, el arco izquierdo

0 X

1 0

0

1 1 Y

etiquetado con 0 y el arco derecho etiquetado con 1.

Método para determinar la palabra que codifica una cadena Paso 1.- Se lee el primer valor de la cadena. Paso 2.- Si el valor leído en el paso anterior es 0, se selecciona el vástago izquierdo, si es 1 se selecciona el vástago derecho. Paso 3.- Si el vástago seleccionado en el Paso 2.- es una hoja, se elige su etiqueta como símbolo de la palabra, se vuelve a la raíz, se lee el siguiente valor de la cadena y se repite el proceso. Si el vástago seleccionado en el Paso 2.- no es una hoja, se lee el siguiente valor de la cadena y se repite al Paso 2.La lectura continúa hasta que se leen todos los valores de la cadena. La “palabra” que corresponde a la cadena de 0 y/o 1 que se ha analizado, se forma con los símbolos del alfabeto en el orden que fueron encontrados.

Codificación de una palabra Cuando en un árbol de Huffman leemos una cadena de 0s y 1s determinamos una palabra, vemos ahora el proceso inverso, dado un árbol de Huffman y una palabra determinamos la cadena que la codifica.

Método para determinar la cadena que codifica una palabra. Paso 1.- Se determina la cadena que codifica cada uno de los símbolos del alfabeto. Paso 2.- Se lee el primer símbolo de la palabra, se selecciona la cadena que lo codifica. Unidad 2  9

Mag. Nancy Alonso – MSc. Elisa Oliva

MATEMÁTICA DISCRETA L.S.I.-L.C.C.

Paso 3.- Se lee el siguiente símbolo de la palabra leído en el Paso anterior y se selecciona la cadena que lo codifica. Paso 4.- Se repite el Paso 3.- hasta agotar los símbolos de la palabra. Paso 5.- Se forma una cadena con las cadenas seleccionadas en los pasos anteriores, en el orden que fueron seleccionadas.

Ejemplo 7 1

0

Dado el árbol arraigado que representa un código de Huffman:

A

1.- Determinamos las palabras que codifican las cadenas

0 0

11010010 y 101010000110 0

2.- Determinamos el código para las palabras ARMAS y SARA

1 C

1 M

1

R

S

El árbol define un código de Huffman con alfabetoX  { A, C,M, R, S} Para 1.- Determinamos las cadenas que codifican los símbolos del alfabeto

0 11  , , A

C

1 01 , 10 0 0 , 10 01    M

R

S

11 0 1001 0 La palabra que codifica la cadena 11010010 es CASA,   C

A

S

A

101 0 1000  0 11 0 . La palabra que codifica la cadena 101010000110 ...