Matemática Discreta

Marco A. Tigre

ITS Sucúa

9 de febrero de 2021

Marco A. Tigre (ITS Sucúa) Matemática Discreta 9 de febrero de 2021 1 / 23

Contenidos

1 Objetivo

2 Teorı́a de gráficas
Introducción
Vértices y aristas

3 Árboles
Definición
Caracteristicas de árboles

Marco A. Tigre (ITS Sucúa) Matemática Discreta 9 de febrero de 2021 2 / 23

Objetivo

 Estudiar conceptos básicos de la teorı́a de árboles.

 Resolver ejercicios.

Marco A. Tigre (ITS Sucúa) Matemática Discreta 9 de febrero de 2021 3 / 23

Teorı́a de gráficas
8.1 ◆ Introducción 319

Sheridan

Greybull
Gillette
Buffalo

Worland

Shoshoni

Casper
Lander

Douglas

Muddy Gap

Figura 8.1.1 Parte del sistema de carreteras de Wyoming.

Figura: ¿Es esto posible? ¿Puede decidir antes de seguir?
formes de las condiciones de los caminos, la visibilidad de las líneas pintadas, el estado de las
WWW señales, etcétera. Como el inspector vive en Greybull, la manera más económica de inspec-
Marco A. Tigre (ITS Sucúa) Matemática Discreta 9 de febrero de 2021 4 / 23
aristas. Por esta razón, la gráfica de la figura 8.1.2 pudo haberse dibujado como la figura 8.1.3.

e1 e6 Wor e 2
Gre She Sho Gre
e 11
e2 e3
e4 Buf Lan
Wor Gil
e5 e 12
e6 e7 e8 e9 e4 e1
e9 e 10 e 13 Mud
Sho Dou Dou Gil
e 11 e 13 Cas e8
Mud e 10 e5
Lan e 12 G Cas e7 She
Buf e 3
G
(a) (b)

Figura: a) Modelo de gráficas para el sistema de carreteras. b) Modelo de gráficas

alternativo, pero equivalente, del sistema de carreteras
Si se inicia en el vértice v0, se viaja por una arista al vértice v1, por otra arista al vér-
tice v2, etcétera, y con el tiempo se llega al vértice vn; este viaje completo recibe el nombre
Los puntos se ollaman
de trayectoria ruta de v0 a vn. yLalastrayectoria
vértices lı́neas queque conectan
comienzaa en
losShe,
vértices
va a Buf se llaman
y termina
en Gil corresponde a un viaje en el mapa de la figura 8.1.1 que comienza en Sheridan, va
aristas.
a Buffalo y termina en Gillette. El problema del inspector de carreteras se enuncia de otra
manera para el modelo de gráficas G: ¿Existe una ruta del vértice Gre al vértice Gre que
pase Marco
[Link] por todas las aristas?
Tigre (ITS Sucúa) Matemática Discreta 9 de febrero de 2021 5 / 23
 e6 Wor e 2
Sho Gre
e 11
Lan

e9 e 12 e4 e1
e 13 Mud
Dou Gil
e8
e 10 e5
Cas e7 She
Buf e 3
G

La gráfica (no dirigida)

G consiste en el conjunto de vértices

V = {Gre, She, Wor , Buf , Gil, Sho, Cas, Dou, Lan, Mud} (1)

y el conjunto de aristas
E = {e1, e2, ..., e13} (2)

Marco A. Tigre (ITS Sucúa) Matemática Discreta 9 de febrero de 2021 6 / 23

Definiciones
Una gráfica (o gráfica no dirigida) G consiste en un conjunto V de vértices
(o nodos) y un conjunto E de aristas (o arcos) tal que cada arista e ∈ E se
asocia con un par no ordenado de vértices. Si existe una arista única e asociada
con los vértices u y w , se escribe e = (v , w ) o e = (w , v ). En este contexto,
(v , w ) denota una arista entre v y w en una gráfica no dirigida y no es un par
ordenado.
Una gráfica dirigida (o digráfica) G consiste en un conjunto V de vértices (o
nodos) y un conjunto E de aristas (o arcos) tales que cada arista e ∈ E está
asociada con un par ordenado de vértices. Si hay una arista única e asociada
con el par ordenado (v , w ) de vértices, se escribe e = (v , w ), que denota una
arista de v a w .
Se dice que una arista e en una gráfica (no dirigida o dirigida) que se asocia
con el par de vértices v y w es incidente sobre v y w , y se dice que v y w son
incidentes sobre e y son vértices adyacentes.

Marco A. Tigre (ITS Sucúa) Matemática Discreta 9 de febrero de 2021 7 / 23

Ejercicios - No tiene trayectoria
Explique por qué ninguna gráfica en los ejercicios que se muestran a continuación
tiene una trayectoria del vértice a al vértice a que pasa por cada arista justo una
vez.

e b
a b c

d c
f d
e

g h i
a b

c
d

Marco A. Tigre (ITS Sucúa) Matemática Discreta 9 de febrero de 2021 8 / 23

Ejercicios - Tiene Trayectoria
Pruebe que cada gráfica en los ejercicios tiene una trayectoria del vértice a al vértice
a que pasa por cada arista justo una vez, encontrando la trayectoria por inspección.

b c
a
d e f
b c

a b c
d e
e
d f
f

g h i

Marco A. Tigre (ITS Sucúa) Matemática Discreta 9 de febrero de 2021 9 / 23

 8.1 ◆ Introducción 321

el par ordenado de vértices (v6, v6). La arista e1 se denota (v2, v1), y la arista e7 se deno-
ta (v6, v6).

▼
Las aristas e1 y e2 se asocian ambas con el par de vértices v1 , v2 . Estas aristas
se llaman aristas paralelas. Una arista incidente en un mismo vértice se llama
La definición 8.1.1 permite que diferentes aristas se asocien con el mismo par de vér-
tices. lazo.
Por ejemplo, en la figura 8.1.5, las aristas e y e se asocian ambas con el par de vér-
1 2
tices {v v2}. Estas
La1, arista e3 =aristas
(v2 , v2se) es un lazo.
llaman Unparalelas.
aristas vértice como
Unavarista
4 queincidente
no incideenenunninguna
mismo
vérticearista, se llama
se llama vértice
lazo. Por en la figura 8.1.5, la arista e3 = (v2, v2) es un lazo. Un
aislado.
ejemplo,
vérticeUna
como v4 en sin
gráfica la figura
lazos 8.1.5, que no
ni aristas incide en
paralelas seninguna arista, se
llama gráfica llama vértice aisla-
simple.
do. Una gráfica sin lazos ni aristas paralelas se llama gráfica simple.

Figura 8.1.5 Una gráfica con aristas paralelas y

un lazo.

Marco A. Tigre (ITS Sucúa) Matemática Discreta 9 de febrero de 2021 10 / 23

ran usando un taladro controlado por computadora. Para ahorrar tiempo y dinero, el taladro
debe moverse tan rápido como sea posible. Se modelará la situación como una gráfica.
Con frecuencia en la manufactura, es necesario hacer agujeros en hojas de me-
Los vértices de la gráfica corresponden a los agujeros (figura 8.1.7). Cada par de vér-
tal. Luego
tices se conecta porse una
atornillan las cada
arista. En componentes a estaselhojas
arista se escribe depara
tiempo metal. Loselagujeros
mover se
taladro en-
perforan usando un taladro controlado por computadora. Para ahorrar
tre los hoyos correspondientes. Una gráfica con números en las aristas (como en la figura tiempo
8.1.7)ysedinero, el taladro
llama gráfica debe moverse
ponderada. Si la tan
aristarápido como sea
e se etiqueta posible.
k, se Seelmodelará
dice que la
peso de la
situación como una gráfica.

b
8
a
6
2
4 c 9
6
3 5 12
d
4
a) Hoja de metal con e
agujeros para tornillos.
b) Modelo de gráficas de la hoja
de metal de la figura 8.1.6. El
peso de la arista es el tiempo para
mover el taladro.

Marco A. Tigre (ITS Sucúa) Matemática Discreta 9 de febrero de 2021 11 / 23

en, tiene longitud mínima. Por supuesto, un par diferente de vértices de inicio y termina-
ión produciría una ruta aún más corta.

TABLAlos8.1.1
Se ve que la ruta que visita ■ Trayectorias
vértices a, b, c, d,ene,laen ese orden, tiene longitud
gráfica de la figura 8.1.7 de a adee inicio
mı́nima. Por supuesto, un par diferente de vértices que y terminación producirı́a
pasan por todos los vértices justo una
una ruta aún más corta.
vez, y sus longitudes.
Trayectoria Longitud
a, b, c, d, e 21
a, b, d, c, e 28
a, c, b, d, e 24
a, c, d, b, e 26
a, d, b, c, e 27
a, d, c, b, e 22

▼
Numerar todas las trayectorias de un vértice v a un vértice w, como se hizo en el
jemplo 8.1.5, es una manera bastante tardada para encontrar la trayectoria de longitud mí-
ima de v a w que visita todos los vértices una vez. Por desgracia, nadie conoce un méto-
o que sea mucho más práctico para gráficas arbitrarias. Este problema es una versión del
roblema delA. Tigre
Marco agente viajero. Se estudiaráMatemática
(ITS Sucúa) ese problema
Discreta en la sección 8.3. 9 de febrero de 2021 12 / 23
 Gráfica completa 8.1 ◆ Introducción 325

La gráfica completa sobre n vértices, denotada por Kn, es la gráfica simple con n vértices

▼
en la que hay una arista entre cada par de vértices distintos.
La gráfica completa sobre n vértices, denotada por Kn , es la gráfica simple con n
vértices en la que hay una arista entre cada par de vértices distintos.
La gráfica completa sobre cuatro vértices, K4, se reproduce en la figura 8.1.12.

a) Gráfica completa K4.

▼
Una gráfica G = (V, E) es bipartita si existen subconjuntos V1 y V2 (cualquiera de los dos
posiblemente vacío)
Marco A. Tigre de V tales que V1 ∩Matemática
(ITS Sucúa) V2 = ∅, V1 ∪ V2 = V, y cada arista
Discreta en E
9 de febrero es inci-
de 2021 13 / 23
Gráfica bipartita
Definición 8.1.11 Una gráfica G = (V, E

▼
posiblemente vacío) de
dente sobre un vértice
Una gráfica G = (V , E ) es bipartita si existen subconjuntos
T V1 S
y V2 (cualquiera de
los dos posiblemente vacı́o) de V tales que V1 V2 = {}, V 1 V 2 = V , y cada
Ejemplo en V8.1.12

▼
arista en E es incidente sobre un vértice La gráfica de la figura
1 y un vértice en V2 .

V1
v1
cada arista incide en un
v4
v2 Observe que la d
tita, entonces e incide
v5
un vértice en V1 y v2 es
v3 la gráfica de la figura
V1 = {v1, v2, v3} y un v
b) Gráfica bipartita. tices de V1 y V2 están e

Ejemplo 8.1.13 ▼ La gráfica de la figura

ca no es bipartita por c
Marco A. Tigre (ITS Sucúa) Matemática Discreta 9 de febrero de 2021 14 / 23
La gráfica bipartita completa sobre m y n vértices, denotada por Km,n, es la gráfica simple
Gráfica
donde bipartita
el conjunto completa
de vértices tiene una partición en V1 con m vértices y V2 con n vértices
y donde el conjunto de aristas consiste en todas las aristas de la forma (v1, v2) con v1 ∈ V1 y
v2 ∈ V2.

▼
La gráfica bipartita completa sobre m y n vértices, denotada por Km,n
La gráfica bipartita completa sobre dos y cuatro vértices, K2,4, se ilustra en la figura 8.1.15.

a) Gráfica bipartita
completa K2,4.

▼
Sugerencias para resolver problemas
Marco A. Tigre (ITS Sucúa) Matemática Discreta 9 de febrero de 2021 15 / 23
Árboles

Seles
Seles
Navratilova
Graf
Sabatini
CAMPEÓN DE
Graf
WIMBLEDON
Graf
FINALES
SEMIFINALES

a) Semifinales y finales en Wimbledon.

v4 v7 v6 v5 v4
v2
v5
v1 v3 v2
v6

v3 v1
v7
(a) (b)
b) El torneo de la
figura (a) como un Árbol de la figura a) girado, b) comparado con
árbol. un árbol natural.

Marco A. Tigre (ITS Sucúa) Matemática Discreta 9 de febrero de 2021 16 / 23

Definición
Un árbol T (libre) es una gráfica simple que satisface lo siguiente: si v y w son
vértices en T, existe una trayectoria simple única de v a w. Un árbol con raı́z es un
árbol en el que un vértice especı́fico se designa como raı́z.

Ejemplo

Si se designa e como la raíz del árbol T de la figura, se obtiene el árbol con raíz T
de la
▼

figura. Los vértices a, b, c, d, e, f, g, h, i, j están (respectivamente) en los niveles 2, 1, 2,

1, 0, 1, 1, 2, 2, 3. La altura de T
es 3.

i e Raíz
d g d f
a j b g
e
b h
a c i h
f
c j
T T

Un árbol T y un árbol con raíz T
. T
se obtiene de T designando a e como la raíz.

▼
Marco A. Tigre (ITS Sucúa) Matemática Discreta 9 de febrero de 2021 17 / 23
hipotética, se da en la figura 9.1.6.

Presidente

Vicepresidente Vicepresidente
de asuntos asuntos
académicos administrativos

Decano de Director de
Decano Director
artes/ciencias planeación
de negocios de compras
académica

Jefe de Jefe de Jefe de

matemáticas computación contabilidad

Figura 9.1.6 Organigrama administrativo organizacional.

Figura: Organigrama administrativo organizacional.

▼
Marco A. Tigre (ITS Sucúa) Matemática Discreta 9 de febrero de 2021 18 / 23
 Equipo
…

Escritorio Documentos Imágenes

Imprimir Mecánica de fluidos

Actividades Test

Métodos Númericos

PVI Problemas de Frontera EDP

Parabólicas Hiperbólicas

Figura: Estructura de explorador Windows mostrada como un árbol con raı́z.

Marco A. Tigre (ITS Sucúa) Matemática Discreta 9 de febrero de 2021 19 / 23

 9.1 ◆ Introducción 383

Libro

Autor Localización Editorial

Disponibilidad

Figura 9.1.9 Árbol de definición jerárquica.

Figura: Árbol de definición jerárquica.

▼
Códigos Huffman
La manera más común de representar caracteres internamente en una computadora es usan-
do cadenas de bits de longitud fija. Por ejemplo, el código estándar para intercambio de in-
formación ASCII (siglas en inglés de American Standard Code for Information Interchange)
representa los caracteres por una cadena de siete bits. En la tabla 9.1.1 se incluyen algunos
ejemplos.
Marco A. Tigre (ITS Sucúa) Matemática Discreta 9 de febrero de 2021 20 / 23
 e
i
j

h g
d c b
f

a
i) ii)

Figura: Grafos que no son árboles.

Con frecuencia, es necesario considerar una colección de árboles disjuntos, a dicha

colección se le denomina bosque.

Marco A. Tigre (ITS Sucúa) Matemática Discreta 9 de febrero de 2021 21 / 23

Caracteristicas de árboles

A continuación, se detallan algunas de las propiedades que distinguen a los

árboles.
Existe un único paseo entre dos vértices cualesquiera.
El número de vértices es mayor que el número de lados.
Un árbol con dos o más vértices tiene al menos una hoja.

Además de su definición, es posible identificar si un grafo dado es un árbol a partir

de las siguientes caracterı́sticas:
Un grafo G = (V , E ) en el cual existe un único paseo entre cada par de vértices
es un árbol.
Un grafo conexo G = (V , E ) con |E | = |V | − 1 es un árbol, donde |E | y |V |
son el tamaño y orden del grafo, respectivamente.
Un grafo G = (V , E ) con |E | = |V | − 1 que no tiene circuitos es un árbol.
Estas propiedades y los resultados pueden verificarse con mucha facilidad a partir
de la definición de árbol.

Marco A. Tigre (ITS Sucúa) Matemática Discreta 9 de febrero de 2021 22 / 23

Marco A. Tigre (ITS Sucúa) Matemática Discreta 9 de febrero de 2021 23 / 23