165
UNIVERSIDAD TECNOLÓGICA NACIONAL
FACULTAD REGIONAL CÓRDOBA
⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯
Carrera de Ingeniería en Sistemas de Información
GRAFOS Y ÁRBOLES
UNIDAD 7
Los temas de la presente unidad corresponden a la Unidad Temática 7, de la asignatura Matemá-
tica Discreta, Área de Programación, correspondiente al primer año de la carrera de Ing. en Sis-
temas de Información. Este apunte fue preparado por la Profesora Ing. SILVIA ARIAS y el Profe-
sor Ing. RAÚL E. MORCHIO. Mantenido desde 2019 por Juan C. Vázquez.
UTN – FRC – ISI – Matemática Discreta
Año 2022
Grafos y Árboles 167
_____________________________________________________
Unidad 7
Grafos y Árboles
6.1. Introducción.
6.2. Grafo, Multígrafo y Subgrafo.
6.3. Grados de un Nodo
6.4. Grafo conexo
6.5. Tipos especiales de Grafo
6.6. Grafos Rotulado
6.7. Grafos Dirigido o Digrafo
6.8. Grafos Árboles
6.9. Árboles con Raíz
6.10 Recorrido de un Árbol
6.1. INTRODUCCIÓN
En el presente capitulo introduciremos los conceptos de grafo y árbol, como herramientas de
modelado y resolución de problemas sumamente útiles y comunes a todas las ciencias informáticas.
El trabajo de Leonhard Euler en 1736 sobre el problema de los puentes de Königsberg es con-
siderado el primer resultado de la teoría de grafos. También se considera uno de los primeros resul-
tados topológicos en geometría (que no depende de ninguna medida).
6.2. GRAFO, MULTÍGRAFO Y SUBGRAFO.
Grafo:
Un grafo G es un objeto matemático que consta de dos componentes:
(i) Un conjunto N = {v
1
, v
2
, …, v
n
} finito y no vacío de elementos llamados nodos o vértices.
(ii) Un conjunto S = {s
1
, s
2
, …, s
m
} finito de parejas no ordenadas de nodos {v
i
, v
j
}, llamadas
aristas o segmentos.
Denotamos un grafo G por G = (N, S) cuando queremos destacar los componentes de mismo.
Así, G = ({a,b,c}, {{a,c},{c,b}}), es un grafo de nodos a, b y c, y aristas {a,c} y {c,b}.
EJEMPLO 6.0:
Sea el grafo G = (N, S) en donde N = {A, B, C, D} y S = {{A,B}, {B,C}, {C,D}, {A,C}, {B,D}}
(ver figura 6.1-a). G tiene 5 aristas s
1
,
s
2
,
s
3
, s
4
, s
5
; cada una de estas aristas corresponderán a las
siguientes parejas no ordenadas de nodos diferentes:
s
1
= {A, B}, s
2
= {B, C}, s
3
= {C, D}, s
4
= {A, C}, s
5
= {B, D}.
Representación
Los grafos se pueden representar por diagramas en el plano. Para ello, cada nodo v de N se re-
presenta por un punto (o pequeño círculo) y cada arista s = {v
i
, v
j
} se representa por un segmento
que conecta sus nodos v
1 y
v
2
.
v
i
v
j
s
UTN – FRC – ISI – Matemática Discreta
Año 2022
Grafos y Árboles 168
Nodos adyacentes – Aristas Incidentes
Los nodos v
i
y v
j
se llaman adyacentes, si hay una arista {v
i
, v
j
} que los vincule y se dice que la
arista es incidente en v
i
y v
j
.
EJEMPLO 6.1:
La figura 6-1(a) representa el grafo G del EJEMPLO 6.0 con los cuatro nodos, A, B, C, y D, y las
cinco aristas s
1
= {A, B}, s
2
= {B, C}, s
3
= {C, D}, s
4
= {A, C}, s
5
= {B, D}.
En ese grafo G, los nodos A y B son nodos adyacentes, y también lo son B y C; C y D, A y C, B y
D. Por su parte s
1
es una arista incidente en los nodos A y B, s
4
lo es en los nodos A y C, etc.
Usualmente diseñamos un grafo dibujando su diagrama en lugar de hacer una lista explícita de sus
nodos y aristas.
(a) Grafo
(c) Subgrafo de (a)
Figura 6-1
Multigrafo - Grafo Simple – aristas múltiples o paralelas – lazo o bucle
Un multigrafo es un grafo que posee dos o más de aristas que conectan un mismo par de vér-
tices, llamadas aristas múltiples o paralelas o una arista cuyo par de vértices son un mismo nodo;
estas aristas se llaman lazo o bucle.
La figura 6-l (b) es un multigrafo. La razón de que sea un multigrafo es que s
4
y s
5
son aristas
múltiples o aristas paralelas, es decir aristas que conectan los mismos nodos, y s
6
es un lazo o
bucle es decir una arista cuyos vértices son un mismo nodo.
En alguna bibliografía se denomina Grafo Simple al grafo que no contiene lazos ni aristas múl-
tiples.
Subgrafo:
Un subgrafo de un grafo dado G, es un grafo cuyos conjuntos de vértices y aristas son subcon-
juntos de los de G; es decir, dado G = (N, S), si N´ es un subconjunto de N (N´
N) y S' un subcon-
junto de S (S'
S) con nodos incidentes en los nodos de N', entonces G' = (N', S') es un subgrafo
de G.
6.3. GRADO DE UN NODO – NODO AISLADO
El grado de v, escrito gr(v), es igual al número de aristas que inciden en v.
Un nodo aislado.es un nodo en el que no incide ninguna arista, o sea un nodo de grado cero.
Como cada arista se cuenta dos veces al sumar los grados de los nodos de un grafo, tenemos el
siguiente resultado sencillo pero importante.
s
5
(b)
Multigrafo
s
6
s
4
s
2
s
1
A
B
C
UTN – FRC – ISI – Matemática Discreta
Año 2022
Grafos y Árboles 169
Teorema 6.1: La suma de los grados de los nodos de un grafo es igual al doble del número de
aristas de dicho grafo.
EJEMPLO 6.2:
En la figura 6-l(a) el grado de los nodos del grafo es: gr(A) = 2, gr(B) = 3, gr(C) = 3, gr(D) = 2. La
suma de los grados de los nodos del grafo es diez (10) que, como era de esperar, es el doble del nú-
mero de aristas (5).
Se dice que un nodo es par o impar, según que su grado sea un número par o impar. Así A y D
son nodos pares, mientras que B y C son nodos impares.
El Teorema 6.1 también es cierto para multigrafos ya que en el lazo se cuenta dos veces para el
grado de su nodo.
Así, en la fig. 6-l(b), el gr(D) = 4, ya que la arista s
6
se cuenta dos veces; y D es un nodo par.
6.4. GRAFO CONEXO
Camino – camino cerrado – sendero – trayectoria – ciclo – circuito – longitud – distancia:
Un camino en un grafo o multigrafo consta de una sucesión alternada de nodos y aristas de la
forma v
0
, s
1
, v
1
, s
2
, v
2
, ... s
n-1
, v
n-1
, s
n
, v
n
en donde cada arista s
i
es incidente en v
i-1
y v
i
.
También se puede expresar que un camino es una sucesión de aristas tal que el vértice de cada
una (exceptuando la última) coincide con el vértice de la siguiente en la sucesión.
El camino se dice que es cerrado si v
0
= v
n
.
Cuando no se generen dudas, se puede denotar un camino por su sucesión de aristas s
l
,s
2
.., s
n
o
por su sucesión de nodos v
1
, v
2
,....,v
n
, y se puede decir que el camino va de v
0
a v
n
, o entre v
0
y v
n
, o
que conecta a v
0
con v
n
.
El número n de aristas de un camino se denomina el largo o la longitud del mismo.
Sendero: Un sendero es un camino en el cual todas las aristas son diferentes.
Trayectoria: Una trayectoria es un camino en el cual todos los nodos son diferentes (en alguna
bibliografía se la llama camino simple).
Así toda trayectoria resulta ser un sendero, pero no todo sendero es una trayectoria.
EJEMPLO 6.3: Considere el grafo de la fig. 6-2a:
1. La sucesión P
4
, P
1
, P
2
, P
5
, P
1
, P
2
, P
3
, P
6
es un camino de P
4
a
P
6
pero no es un sendero ya que la arista {P
1
, P
2
} se usa dos veces.
Tampoco es una trayectoria porque no es un sendero, además puede
verse que es así porque pasa dos veces por los nodos P
1
y P
2
.
2. La sucesión P
4
, P
1
, P
5
, P
2
, P
6
no es un camino ya que no hay aris-
ta {P
2
, P
6
}.
En la figura 6-2b:
3. La sucesión P
4
, P
1
, P
5
, P
2
, P
3
, P
5
, P
6
es un sendero ya que ningu-
na arista se usa dos veces; pero no es una trayectoria ya que el nodo P
5
se usa dos veces.
4. La sucesión P
4
, P
1
, P
5
, P
3
, P
6
es una trayectoria de P
4
a P
6
.
5. La mínima trayectoria (con respecto a longitud) de P
4
a P
6
es P
4
, P
5
, P
6
que tiene longitud 2.
1
P
2
P
3
4
P
5
P
6
Figura 6 -2a
P
1
P
4
P
1
P
4
1
P
2
P
3
4
P
5
P
6
Figura 6 -2
P
1
b
UTN – FRC – ISI – Matemática Discreta
Año 2022
Grafos y Árboles 170
Eliminando aristas innecesarias, no es difícil demostrar que cualquier camino de un nodo u a
uno v se puede reemplazar por una trayectoria de u a v. Establecemos este resultado formalmente.
Teorema 6.2: Hay un camino de un nodo u a un nodo v, si y solo si, hay una trayectoria de u a v.
Circuito: Un circuito es un sendero cerrado (camino cerrado en el cual no se repiten aristas).
En la fig. 6.2b el camino P
1
, P
4
, P
5
, P
3
, P
6
, P
5
, P
1
es un circuito, pero no un ciclo.
Ciclo: Un ciclo es una trayectoria cerrada (camino cerrado en el que todos sus vértices son dife-
rentes excepto v
o
= v
n
).
En un grafo (sin aristas paralelas ni bucles), cualquier ciclo debe tener longitud tres o más.
En la fig. 6.2b el camino P
1
, P
4
, P
5
, P
3
, P
2
, P
1
es un ciclo. También P
1
, P
4
, P
5
, P
1
lo es.
Caminos
Abierto
Cerrado
No se repiten aristas
Sendero
Circuito
No se repiten nodos
Trayectoria
Ciclo
Grafo conexo:
Un grafo se dice que es conexo si hay una trayectoria entre dos cualquiera de sus nodos. Si no
es conexo se denomina inconexo o no conexo.
El grafo de la figura fig. 6-2 es conexo, pero el grafo de la fig. 6-3(a) es no conexo porque por
ejemplo, no hay trayectoria entre D y E o entre A y B.
Distancia: La distancia entre dos nodos u y v de un grafo conexo G, que se simboliza d(u, v), es la
longitud de la trayectoria más corta entre u y v.
En la fig. 6-3b, d(A,B)=1, d(A,C)=1, d(A,D)=1, d(A,E)=2, d(A,F)=2, d(A,H)=3.
Si determinamos las distancias entre otros pares cualquiera de nodos, tales como (B,H), (C,H),
etc., vemos que la mayor distancia posible entre dos nodos cualquiera de dicho grafo es d(A,H)=3.
Nota: Aunque las aristas {A, D} y {B, C} se dibujaron cruzándose, no se cruzan en un nodo.
Punto de corte: Un nodo v en un grafo conexo G se llama punto de corte si el grafo resultante de
eliminar el nodo v y todas sus aristas incidentes es inconexo. Este grafo suele denotarse G-v.
El nodo D de la fig. 6-3(b) es un punto corte, como se puede verificar en la fig. 6-3(c), que es el
grafo G - v resultante de eliminar el nodo D en el grafo de la fig. 6-3(b).
Los puntos de corte son nodos críticos de un grafo ya que interrumpen la conexidad. Si se está
modelando con el grafo una red de computadoras, de autopistas o de conexión domiciliaria de agua,
el daño en un nodo punto de corte produce pérdida de servicio para una parte de la red.
B E
A H
C F
(c)
)
Figura 6.3
UTN – FRC – ISI – Matemática Discreta
Año 2022
Grafos y Árboles 171
6.5. TIPOS ESPECIALES DE GRAFO
Hay muchos tipos de grafo, que tienen su propio vocabulario de términos especiales y que sir-
ven para modelar distinto tipo de problemas. Se mencionarán los tipos de mayor uso en informática.
Grafos completos – Grafo trivial
Un grafo es completo si cada nodo está conectado mediante un segmento con todo otro nodo.
Al grafo completo de n nodos se lo denota K
n
.
La figura 6-4 muestra los grafos completos K
1
, K
2
, K
3
, ........, K
6
. En particular, al grafo K
1
que
consta de un único nodo aislado, se le llama el grafo trivial.
●
K
1
K
2
K
4
K
5
K
6
Figura 6-4
Todo grafo completo es, por supuesto, también conexo porque existe un camino de largo uno
entra cualquier par de nodos; pero claramente no todo grafo conexo es completo. El grafo de la fi-
gura 6-3(b) es conexo, pero no es completo ya que no hay un segmento entre los nodos C y F, por
poner solo un ejemplo.
Grafos planos
Un grafo o multígrafo se dice que es plano si es posible dibujarlo en un plano de tal manera
que sus aristas no se corten.
Aunque el grafo completo con cuatro nodos K
4
comúnmente se dibuja con las diagonales del
cuadrado como aristas cruzadas, como en la fig. 6-5(a), también se puede dibujar sin que se crucen
sus aristas, como en la fig. 6-5(b). Así, K
4
, es un grafo plano.
Figura 6-5 Figura 6-6
Mapa
Se llama mapa a la representación de un grafo plano dibujado de tal forma que no se
corten sus aristas. El grafo de la figura 6-5(b) es un mapa de K
4
.
Un mapa dado divide el plano en varias regiones.
Por ejemplo, el mapa de la fig. 6-6 divide al plano en cinco regiones. Observe que cuatro de las
regiones son acotadas, pero la quinta región (r
5
), fuera del diagrama, es no acotada. Así no hay pér-
K
3
UTN – FRC – ISI – Matemática Discreta
Año 2022
Grafos y Árboles 172
dida de generalidad al contar las regiones si suponemos que nuestro mapa está contenido en algún
rectángulo mayor en lugar de en el plano completo.
Euler demostró una fórmula que relaciona el número de nodos N, el número de aristas S y el
número de regiones R para cualquier mapa conexo.
Teorema 6.3 (Fórmula de Euler): En todo mapa de un grafo plano G = (N, S) que genere R re-
giones, se verifica que la cantidad de nodos, menos la cantidad de aristas, más la cantidad de
regiones, es igual a dos: |N| – |S| + R = 2
EJEMPLO 6.4 Para el grafo de la figura 6-6 se tiene N = 6, S = 9, R = 5; de acuerdo con la fórmula
de Euler:
N – S + R = 6 - 9 + 5 = 2
La fórmula de Euler también es cierta para mapas inconexos, siempre y cuando la constante 2
se reemplace por c + 1, en donde c es el número de componentes conexos del mapa.
6.6. GRAFOS ROTULADOS
Un grafo G se llama un grafo rotulado o etiquetado, si a sus aristas y/o nodos se le asignan
datos de alguna clase.
En particular, si a cada arista s de G se le asigna un número no negativo p
s
, denominado el pe-
so de la arista s, entonces también se dice que el grafo es pesado.
La fig. 6-7 muestra un grafo rotulado en donde el peso de cada arista está indicado con un nú-
mero no negativo sobre ella.
Frecuentemente es importante encontrar una trayectoria de peso mínimo entre dos nodos dados
de un grafo rotulado.
Ejemplo de una trayectoria mínima entre P y Q en la fig. 6-7 es el camino P, A
1
, A
2
, A
5
, A
3
, A
6
,
Q que tiene peso 14. (pruebe encontrar otra trayectoria mínima entre los mismos dos nodos.)
Figura 6-7
6.7. GRAFOS DIRIGIDOS O DIGRAFOS
Un grafo dirigido, también llamado un digrafo, es un multigrafo con una dirección asignada a
cada arista.
Esto es, un digrafo D = (N, A) es un tipo especial de grafo, donde el conjunto de aristas dirigi-
das S tiene por elementos a pares ordenados de nodos: A
NN.
Llamaremos arcos a las aristas dirigidas, y escribimos a = (u, v) para denotar un arco que par-
te de un nodo inicial u y llega a un nodo final v.
A
4
A
5
A
6
UTN – FRC – ISI – Matemática Discreta
Año 2022
Grafos y Árboles 173
EJEMPLO 6.4: La figura 6-8 representa un dígrafo con cua-
tro nodos y siete arcos. Observe que en el nodo B se
tiene el lazo dirigido, a
7
= (B, B).
Arcos como a
2
y a
3
en la figura 6-8, que tienen el mis-
mo punto inicial y el mismo punto final, se llaman parale-
los.
En un grafo dirigido D, se definen el grado de salida
gs(v) y el grado de llegada o de entrada ge(v) de un nodo v
como el número de arcos que comienzan y terminan en v,
respectivamente.
Teorema 6.4: En todo grafo dirigido, la suma de los grados de salida de los nodos del grafo es
igual a la suma de los grados de llegada de los nodos, e igual al número de arcos.
Resulta sencillo demostrar este teorema, porque con cada arco en A que tiene un nodo de inicio
y un nodo de fin, se suma 1 al grado de salida del nodo inicial y se suma 1 al grado de llegada del
nodo final.
Fuentes y Sumideros
Un nodo con grado de llegada cero y grado de salida distinto de cero se llama fuente, y un no-
do con grado de salida cero y grado de entrada distinto de cero se llama sumidero.
En la fig. 6-8, el nodo C es un sumidero, pero el dígra-
fo no tiene fuentes. Veamos los grados de salida y llegada
y el número de arcos de dicha figura.
Importante: El lazo en el nodo B se cuenta dos veces,
uno como salida y otro como llegada.
Si se rotulan los arcos y/o nodos de un digrafo con algún tipo de datos, entonces tenemos un
grafo dirigido rotulado.
Tales grafos se usan frecuentemente para representar situaciones dinámicas. Por ejemplo, los
diagramas de flujo son grafos dirigidos en los cuales los nodos (cajas) se rotulan, y los arcos que
salen de una caja de decisión se rotulan.
EJEMPLO 6.5: Tres niños A, B, y C se están lanzando un balón de tal manera que A siempre le lan-
za el balón a B, pero tanto B como C le lanzan el balón a A con tanta frecuencia como entre ellos.
La fig. 6-9 ilustra esta situación dinámica, en donde los arcos están rotulados con sus respecti-
vas probabilidades, o sea, A le lanza el balón a B con probabilidad 1, B se lo lanza a A y C con
probabilidad 1/2 a cada uno, y C se lo lanza a A y B con probabilidad 1/2 a cada uno.
Figura 6-9
n
gs(n)
ge(s)
A
1
2
B
4
2
C
0
2
Sumidero
D
2
1
Total
7
7
arcos = 7
Figura 6-8
UTN – FRC – ISI – Matemática Discreta
Año 2022
Grafos y Árboles 174
Dígrafos y relaciones
Considere un dígrafo D = (N, S) que no tiene arcos paralelos; sea N el conjunto de nodos y A
el conjunto de sus arcos.
Como los arcos representan parejas ordenadas de nodos, A es simplemente un subconjunto de
del producto cartesiano N x N, o sea A N x N, y por lo tanto puede se puede considerar que
A es una relación en N.
Recíprocamente, si R es una relación en un conjunto N, entonces N se puede tomar como el
conjunto de nodos y R como el conjunto de arcos de un dígrafo, D=(N, R), que no tiene arcos para-
lelos.
Así, los conceptos de relaciones en un conjunto y dígrafos sin arcos paralelos son una y la
misma cosa. En efecto, en la Unidad 4 ya habíamos introducido el grafo dirigido como una de las
representaciones posibles de una relación definida sobre un conjunto.
Digrafos y matrices
Sea D un grafo dirigido con nodos v
1
, v
2
, ... , v
m
; D se lo puede representar por una matriz m
m
en donde m es el número de nodos. Indicándola como
M
D
= (m
ij
),
siendo m
i j
los elementos de la matriz, indican el número o cantidad de arcos que comienzan en v
i
y
terminan en v
j
.
Si D no tiene arcos paralelos las entradas de M
D
serán ceros y unos; en caso contrario las entra-
das serán enteros positivos.
Recíprocamente, toda matriz M de dimensiones m
m con enteros no negativos como entradas
define de una manera unívoca un digrafo con m nodos.
La fig. 6-10 muestra un digrafo D y la correspondiente matriz M
D
de dimensiones 4x4 por ser
un digrafo de 4 nodos. Como ya dijimos, la notación m
ij,
donde i señala la fila y j la columna, co-
rresponde al número de arcos que comienzan en el nodo i y terminan en el j. La entrada corres-
pondiente a m
41
(fila v
4
y columna v
1
) indica, por lo tanto, la cantidad de arcos que van del nodo v
4
al nodo v
1
, que como vemos es 2.
Figura 6-10
Camino simple y ciclos
En un dígrafo o grafo dirigido, los conceptos de camino, sendero, circuito, trayectoria y ciclo
se pueden usar tal como se usó en el grafo no dirigido, con la condición de que la dirección del ca-
mino, sendero, circuito, trayectoria, etc., debe coincidir con las direcciones de los arcos.
Específicamente, un camino (dirigido) C en un digrafo D es una sucesión alternada de nodos y
arcos, C = v
0
, a
1
, v
1
, a
2
, v
2
, ..., a
n
, v
n
tal que cada arco a
i
comienza en v
i-1
, y termina en v
i
.
Un camino en un grafo dirigido también puede ser cerrado, si los vértices primero y último en
la secuencia son los mismos.
v
1
v
2
v
3
v
4
v
1
0 1 0 0
v
2
0 1 0 0
M
D
v
3
0 0 0 1
v
4
2 0 1 0
UTN – FRC – ISI – Matemática Discreta
Año 2022
Grafos y Árboles 175
Un camino simple o trayectoria en un grafo dirigido G, es un camino en G en el que cada
vértice es distinto.
Un ciclo en un grafo dirigido G, es un camino en G en el que todos los vértices son distintos
salvo el primero y el último (cerrado). El ciclo depende del nodo que se con-
sidere inicial y final. En la Figura 6-11 si v
0
=A= v
n
el ciclo es el A, B, C, A,
si v
0
=B= v
n
el ciclo es B, C, A, B y si v
0
=C= v
n
el ciclo es C, A, B, C.
Son tres ciclos.
Figura 6-11
6.8. GRAFOS ÁRBOLES O ARBOLES
Definición: Un árbol es un grafo A = (N, S) acíclico conexo.
Por tratarse de un grafo no dirigido, que no contiene ciclos y que es conexo, también se lo pue-
de definir como: Árbol es un grafo en el cual existe un único camino entre cada par de nodos.
La fig. 6-12(a) muestra todos los árboles con seis nodos, y la fig. 6-12(b) muestra ocho de los
árboles con siete nodos.
Figura 6-12 (a) y (b)
En la figura 6-12(c) G
1
corresponde a lo que definimos como árbol; en el caso de G
2
, éste no es
un árbol debido a que contiene un ciclo.
Cuando un grafo G es un árbol, se suele escribir A en lugar de G para darle nombre.
Bosque
Si un grafo es no conexo y cada componente conexa es un árbol, el grafo se denomina bosque.
a b a b
c c
G
1
d G
2
d
e f e f
Figura 6-12 (c)
UTN – FRC – ISI – Matemática Discreta
Año 2022
Grafos y Árboles 176
Ejemplo: En la figura 6-12(c), si en G
1
se suprime la arista {c, d}, se obtiene un bosque de dos ár-
boles.
Árbol trivial
Árbol trivial es aquel en el cual el número de nodos n es n = 1.
Propiedades de los Árboles.
Teorema 6.5a: Si a y b son nodos cualesquiera de un árbol A = (N, S), entonces hay un camino
único que conecta estos nodos.
Teorema 6.5b: En cualquier árbol el número de nodos es igual al número de aristas más uno, o
sea, para un árbol cualquiera A= (N, S), se cumple: |N| = |S| + 1.
Teorema 6.5c: Dado cualquier árbol A = (N, S), si |S|
1, entonces A tiene al menos dos nodos
colgantes. Dicho de otra forma, cualquier árbol no trivial tiene al menos dos nodos colgantes
o extremos.
Teorema 6.5d: Para cualquier árbol A no trivial:
- Cada pareja de nodos está conectada por exactamente una trayectoria.
- A es conexo, pero si se quita cualquiera de sus aristas, el grafo que resulta no es conexo.
- A es libre de ciclos, pero si se le agrega al grafo cualquier arista (sin agregar nodos) el
grafo resultante tiene exactamente un ciclo. Dicho de otra manera, A es acíclico y agregan-
do una arista entre nodos no adyacentes se crea un ciclo y solo uno.
Otras propiedades de los árboles
1). Un árbol es un grafo plano.
2). En un árbol no trivial, cada nodo o es colgante o es un punto de corte.
Árboles maximales
Un subgrafo A de un grafo dado G, se llama árbol maximal de G si A es un árbol e incluye to-
dos los nodos de G.
La fig. 6-13 muestra un grafo G y árboles maximales A
1
, A
2
y A
3
de G.
Si G es un grafo cuyas aristas tienen pesos, entonces un árbol maximal mínimal de G es un ár-
bol maximal de G tal que la suma de los pesos de sus aristas es la menor entre todos los árboles
maximales de G.
En la figura 6-12(c) anterior, G
1
es un subgrafo de G
2
, en el que G
1
contiene los nodos de G
2
y
es un árbol. Por lo tanto es un Árbol máximal de G
2
Debemos destacar que, como algunos segmentos pueden ser del mismo peso, podemos obtener
A
1
A
2
A
3
Figura 6-13
UTN – FRC – ISI – Matemática Discreta
Año 2022
Grafos y Árboles 177
5
diferentes árboles maximales minimales. La fig. 6-14 muestra un grafo conexo rotulado G y un ár-
bol maximal minimal M, pero se pueden plantear otros.
Figura 6-14
6.9. ÁRBOLES CON RAÍZ
Un árbol R con raíz, es un árbol que tiene un nodo particular r designado como la raíz del ár-
bol, de modo que desde r hasta cualquier otro nodo v, existe un único camino dirigido que los une.
En la figura 6-15, al buscar un nodo como raíz vemos que cualquier nodo puede asumir dicho
rol. Al ser el árbol, un grafo simple en el cual existe un único camino entre cada par de nodos, es
claro que cualquier nodo de un árbol puede ser raíz. Por ejemplo, podríamos tomar el nodo r como
raíz como en la figura, pero también podríamos haber elegido el d, f, g, etc. ya que todos cumplen la
condición señalada.
Una vez que hemos elegido un nodo como raíz del árbol, éste se suele pensar como un grafo
árbol dirigido en el cuál la dirección de todos sus caminos dirigidos inician a partir del nodo desig-
nado como raíz. Por lo tanto, todo árbol con raíz, es un árbol dirigido.
Árbol con raíz o árbol dirigido
Definición: Sea el digrafo G= (N, S). Decimos que G es un árbol R dirigido ó árbol R con raíz si
existe un nodo r
que pertenece a N tales que desde r hasta cualquier nodo v que pertenece a N
existe un único camino dirigido que los une.
De esta forma todo nodo N es alcanzable desde r
de forma única. El nodo r se llama raíz del
árbol R dirigido.
Los árboles dirigidos se pueden dibujar con arcos indican-
do la dirección, como en la primera figura, en lugar de aristas.
Pero es más usual dibujarlos cambiando los arcos por aristas,
(como en la segunda figura), y conservando el sentido de las
flechas en forma implícita. Es decir, aún cuando no estén dibujados los arcos, los árboles con raíz
siguen siendo árboles dirigidos.
Un nodo es en sí mismo un árbol, el árbol trivial y ese nodo es la raíz de dicho árbol, por lo
tanto, el árbol trivial es un árbol con raíz
Nivel de un nodo
R
R
Figura 6-15
M
G
UTN – FRC – ISI – Matemática Discreta
Año 2022
Grafos y Árboles 178
Nivel del nodo v, (también profundidad de v) es la longitud de la única trayectoria desde la
raíz r a v. La raíz está situada en el nivel 0.
En la fig. 6-15 anterior, los niveles de sus nodos son: r = 0; a, b, c = 1; d, e, f, g = 2; h, i, j = 3
Altura de un Árbol
La altura de un árbol es el valor del máximo nivel de un nodo, el que denominaremos h.
En la fig. 6-15 anterior, h = 3.
Hojas
Los nodos colgantes de R se llaman hojas del árbol con raíz.
En la fig. 6-15, el árbol tiene como hojas d, f, h, i, j. El nivel de d y f es 2; el de h, i, j es 3.
Rama
Se llama rama a una trayectoria dirigida continua desde un nodo a una hoja de R.
Preceder y seguir
Se dice que un nodo u precede a otro v, o que v sigue a u, si la trayectoria desde la raíz r a v
incluye a u.
En particular, decimos que v sigue inmediatamente después de u si v sigue a u y es adyacente
a u.
En la fig. 6-15 (se la repite) el nodo j sigue a c, y j sigue
inmediatamente a g. Observe que todo nodo, excepto la raíz,
sigue inmediatamente después de algún nodo único, pero puede
ser seguido inmediatamente por más de un nodo, por ejemplo,
los vértices i y j ambos siguen inmediatamente después de g.
Antepasados, descendientes, padres, hijos, hermanos
Un árbol es una estructura jerárquica de un conjunto de ele-
mentos llamados nodos o vértices, uno de los cuales se distin-
gue como raíz, que establece una relación de “parentesco” en-
tre estos elementos (que está dada por la disposición de las aristas) y que impone el uso de términos
como padre, hijo, hermanos, antecesor, sucesor, ancestros, antepasados, descendientes.
Sea G un grafo con raíz v
0
. Supóngase que x, y, z son nodos en G y que (v
0
, v
1
, ..., v
n
), es un ca-
mino en G. Se ejemplifica con la fig. 6-15.
• v(
n-1
) es el padre de v(
n
). Así a es el padre de d y e; c lo es de g y este a su vez de j
• v
0
, v
1
, ..., v(
n-1
) son los antepasados de v(
n
). Así, e, a, r son los antepasados de h.
• v(
n
) es el hijo de v(
n-1
). Así, d y e son hijos de a, y g es hijo de c
En un árbol con raíz, cada nodo diferente de la raíz tiene uno y solo un padre, pero puede te-
ner varios hijos y su nivel es uno más que el nivel de su padre.
• Si x es un antepasado de y, entonces y es un descendiente de x. Así h es un descendiente de
e, a y r porque ellos son sus antepasados.
• Si x e y son hijos de z entonces x e y son hermanos. Así d y e son hermanos y también lo
son i y j. y también a, b y c.
• Si x no tiene hijos entonces x es un nodo terminal (hoja). Así d, f, h, i y j son hojas o no-
dos terminales.
Nodo interno o nudo
-15
UTN – FRC – ISI – Matemática Discreta
Año 2022
Grafos y Árboles 179
Figura 6-16
Si x no es un nodo terminal (una hoja la cual no tiene hijos) entonces x es un nodo interno.
Subárbol
El subgrafo de G que consiste en el nodo x y todos sus descendientes, con x como raíz, es el
subárbol de G que tiene a x como raíz.
Árbol m-ario
Un árbol con raíz se llama árbol m-ario si todos los nodos internos tienen, a lo sumo m hijos.
Un árbol m-ario con m = 2, se llama árbol binario.
Un árbol se llama m-ario completo si todo nodo interno tiene exactamente m hijos.
Árboles como estructuras ordenadas
A menudo los nodos de un árbol se consideran ordenados
de arriba abajo y de izquierda a derecha. De esta forma los árbo-
les de la figura 6-16 son distintos porque, aunque tienen los
mismos nodos (a, b, c) y los hijos de a son los mismos, en los
dos árboles aparecen b y c en distinto orden.
Árboles ordenados con raíz
Árbol ordenado con raíz es un árbol R con raíz, en el que los hijos de cada nodo están ordenados.
Toda representación de un árbol con raíz en modo convencional determina un orden de sus
aristas, y por lo general el orden no se menciona de manera explícita. Si se necesita un orden, se
realiza cuando surge la necesidad y se especifica por la forma en que se traza el dígrafo del árbol.
Los árboles ordenados con raíz son muy usuales en la ciencia de los computadores y en la in-
formática, como se ilustra con los dos ejemplos siguientes.
EJEMPLO 6.5 (Expresiones aritméticas). Cualquier expresión aritmética con solamente operaciones
binarias, por ejemplo, adición, substracción, multiplicación y división, se puede representar por un
árbol ordenado con raíz. Por ejemplo, la expresión aritmética
(a - b) / ((c
d) + e)
se puede representar por el árbol ordenado con raíz en la
fig. 6-17. Observe que las variables en la expresión, a, b, c,
d y e, aparecen como hojas, y las operaciones aparecen co-
mo nodos internos.
Figura 6-17. Árbol de la expresión aritmética
(a - b) / ((c x d) + e)
EJEMPLO 6.6 (Estructura de registro).
Los datos se organizan frecuentemente en jerarquías de campos, registros, y archivos, como se
muestra a continuación.
Un registro es una colección de datos de campo, o campos relacionados que son tratados como
una unidad; y un archivo es una colección de registros similares.
Por ejemplo, un registro de personal para un empleado puede tener los siguientes datos de
campo: DNI, Apellido y Nombre, Dirección, Fecha de nacimiento, Sexo y Sueldo.
El archivo de empleados de la compañía contendrá la lista de registros de los empleados.
Este documento contiene más páginas...
Descargar Completo
MAD2022_Unidad_7 (1).pdf
Estamos procesando este archivo...
Lamentablemente la previsualización de este archivo no está disponible. De todas maneras puedes descargarlo y ver si te es útil.
Descargar
Estamos procesando este archivo...
Lamentablemente la previsualización de este archivo no está disponible. De todas maneras puedes descargarlo y ver si te es útil.