1

Grafos y árboles

Dahana Michel Garzón Yagari

Universidad Nacional Abierta Y A Distancia – Unad

Escuela De Ciencias Básicas, Tecnología E Ingeniería -Ecbti

Ingeniería De Sistemas

2022

1
 2

Ejercicio 1

Con el siguiente grafo:

Grafo 4: N-R, R-O, O-O, O-P

a) Describa formalmente el grafo

Grafo con 4 vértices que se describí de la siguiente forma:

𝑉 = 𝑣𝑒𝑟𝑡𝑖𝑐𝑒𝑠

𝑉(𝐺4 ) = {𝑁, 𝑅, 𝑂, 𝑃}

E = 𝑎𝑟𝑖𝑠𝑡𝑎𝑠

E(𝐺4 ) = {(𝑁, 𝑅), (𝑅, 𝑂), (𝑂, 𝑂)(𝑂, 𝑃)

b) Halle el grado y paridad de cada vértice

Para hallar el grado del vértice, se debe observar cuantas aristas son incidentes al vértice

𝐺𝑟(𝑁) = 1 𝑖𝑚𝑝𝑎𝑟

𝐺𝑟(𝑅) = 2 𝑝𝑎𝑟

𝐺𝑟(𝑂) = 4 𝑝𝑎𝑟

𝐺𝑟(𝑃) = 1 𝑖𝑚𝑝𝑎𝑟

c) Verifique si cumple que la suma de los grados de los vértices de un grafo es igual a dos

veces el número de aristas

2
 3

Utilizaremos el teorema denominado informalmente como el apretón de mano, el cual

nos dice que

𝑆𝑒𝑎 𝐺 = (𝑉, E), 𝑢𝑛 𝑔𝑟𝑎𝑓𝑜. 𝐸𝑛𝑡𝑜𝑛𝑐𝑒𝑠 ∑ 𝐺𝑟(𝑣) = 2|E|

Es decir que la suma de los grados de todos los vértices es igual a dos veces el numero de

aristas

|E| = 4

∑ 𝐺𝑟(𝑣) = 1 + 2 + 4 + 1 = 8
𝑣∈𝑉

8 =2∗4

8=8

Con lo anterior afirmamos que la suma de los grados de los vértices de un grafo es igual a

dos veces el número de aristas.

3
 4

Ejercicio 2

a) Responda lo siguiente: ¿Cuál es la diferencia entre un dígrafo, un grafo y un

multígrafo?

La diferencia entre un dígrafo, un grafo y un multígrafo, es que el dígrafo es un grafo

dirigidos donde a cada arista se le asigna un orden en sus extremos, mientras un

multígrafo es un grafo con varias aristas entre dos vértices y un grafo es un conjunto

A de pares no ordenados de elementos distintas y otro conjunto de elementos V,

donde v es el conjunto de vértices del grafo y E como el conjunto aristas del grafo, en

conclusión todos son grafos, pero con características o compartimentos diferentes.

b) Determine gráficamente si el multígrafo G4 = {V, E}, es grafo o multígrafo, donde

V = {a, b, c, d} y E = {{a, b}, {a, c}, {a, d}, {b, c}, {c, d}, {b, a}}

a b

c d

G4 = {V, E}, es grafo multígrafo por que posee aristas paralelas en los vértices a y b

4
 5

Ejercicio 3

Realice el grafo a partir de la información dada en la matriz de adyacencia y descríbalo

formalmente:

G4 = {V, E}

𝑉 = 𝑣𝑒𝑟𝑡𝑖𝑐𝑒𝑠

𝑉(𝐺4 ) = {𝑎, 𝑏, 𝑐, 𝑑, 𝑒}

E = 𝑎𝑟𝑖𝑠𝑡𝑎𝑠

E(𝐺4 ) = {(𝑎, 𝑎), (𝑏, 𝑎), (𝑐, 𝑎), (𝑑, 𝑎), (𝑒, 𝑎), (𝑎, 𝑒), (𝑏, 𝑐), (𝑐, 𝑐), (𝑑, 𝑏), (𝑒, 𝑏)

a b

c e
d
G4 = {V, E}, es grafo multígrafo por que posee aristas paralelas en los vértices a y e, así

como también bucles en las aristas a y c

5
 6

Ejercicio 4

Para el siguiente árbol

determine

a. Nodos hoja, nodos rama

Nodos hoja (Tiene grado uno)

𝐷, 𝐸, 𝐺, 𝐻, 𝐿, 𝑂

Nodos rama(El resto de nodos, menos la raíz)

𝐵, 𝐶, 𝐹, 𝐼, 𝐽, 𝐾, 𝑀, 𝑁

b. La raíz del árbol

6
 7

c. Las relaciones entre vértices de un árbol enraizado.

• Hijos • Padres • Hermanos

𝐵, 𝐹, 𝐼 𝑦 𝑀, 𝑠𝑜𝑛 ℎ𝑖𝑗𝑜𝑠 𝑑𝑒 𝐴 𝐴 𝑒𝑠 𝑝𝑎𝑑𝑟𝑒 𝑑𝑒 𝐵, 𝐹, 𝐼 𝑦 𝑀 𝐵, 𝐹, 𝐼 𝑦 𝑀 𝑆𝑜𝑛 ℎ𝑒𝑟𝑚𝑎𝑛𝑜𝑠

𝐶 𝑒𝑠 ℎ𝑖𝑗𝑜 𝑑𝑒 𝐵 𝐵 𝑒𝑠 𝑝𝑎𝑑𝑟𝑒 𝑑𝑒 𝐶 𝐷 𝑦 𝐸 𝑠𝑜𝑛 ℎ𝑒𝑟𝑚𝑎𝑛𝑜𝑠

𝐷 𝑦 𝐸, 𝑠𝑜𝑛 ℎ𝑖𝑗𝑜𝑠 𝑑𝑒 𝐶 𝐶 𝑒𝑠 𝑝𝑎𝑑𝑟𝑒 𝑑𝑒 𝐷 𝑦 𝐸 𝐺 𝑦 𝐻 𝑠𝑜𝑛 ℎ𝑒𝑟𝑚𝑎𝑛𝑜𝑠

𝐺 𝑦 𝐻, 𝑠𝑜𝑛 ℎ𝑖𝑗𝑜𝑠 𝑑𝑒 𝐹 𝐹 𝑒𝑠 𝑝𝑎𝑑𝑟𝑒 𝑑𝑒 𝐺 𝑦 𝐻

𝐽 𝑒𝑠 ℎ𝑖𝑗𝑜 𝑑𝑒 𝐼 𝐼 𝑒𝑠 𝑝𝑎𝑑𝑟𝑒 𝑑𝑒 𝐽

𝐾 𝑒𝑠 ℎ𝑖𝑗𝑜 𝑑𝑒 𝐽 𝐽 𝑒𝑠 𝑝𝑎𝑑𝑟𝑒 𝑑𝑒 𝐾

𝐿 𝑒𝑠 ℎ𝑖𝑗𝑜 𝑑𝑒 𝐾 𝐾 𝑒𝑠 𝑝𝑎𝑑𝑟𝑒 𝑑𝑒 𝐿

𝑁 𝑒𝑠 ℎ𝑖𝑗𝑜 𝑑𝑒 𝑀 𝑀 𝑒𝑠 𝑝𝑎𝑑𝑟𝑒 𝑑𝑒 𝑁

𝑂 𝑒𝑠 ℎ𝑖𝑗𝑜 𝑑𝑒 𝑁 𝑁 𝑒𝑠 𝑝𝑎𝑑𝑟𝑒 𝑑𝑒 𝑂

d. Subárboles

Primer subárbol

7
 8

Segundo subárbol

Tercer subárbol

8
 9

Cuarto subárbol

Quinto subárbol

9
 10

Sexto subárbol

Séptimo subárbol

10
 11

Octavo subárbol

e. Nivel y la altura del árbol

Segundo nivel

Tercer nivel

Cuarto nivel

Quinto nivel

Por lo tanto, la altura del árbol es 5

11
 12

Ejercicio 5

Este ejercicio se sustentará por medio del vídeo. Consulte y explique con un ejemplo

propio los conceptos de circuitos eulerianos y circuitos hamiltonianos.

Para que un circuito sea euleriano debe cumplir con dos cosas

1. Debe ser un camino euleriano, ¿qué significa?, que debe pasar por todas las aristas

una sola vez

2. Debe terminar donde inicia

Ejemplo :

P L

A
S
M

Para que un circuito sea hamiltoniano debe cumplir con dos cosas

1. Debe ser un camino hamiltoniano, ¿qué significa?, que debe pasar por todos los vértices

una sola vez

2. Debe terminar donde inicia

Ejemplo :

12
 13

P L

A
S Nota: Utilice el mismo ejemplo del
M circuito anterior , pero pinte de

negro el circuito que satisface que

13
 14

Bibliografía

Villalpando, B. J. F. (2014). Definiciones básicas. Matemáticas Discretas Aplicaciones y

ejercicios. (pp. 186- 189). https://elibro-

net.bibliotecavirtual.unad.edu.co/es/ereader/unad/39454

Villalpando, B. J. F. (2014). Terminología y caracterización de los grafos. Matemáticas Discretas

Aplicaciones y ejercicios. (pp. 190- 198). https://elibro-

net.bibliotecavirtual.unad.edu.co/es/ereader/unad/39454

Villalpando, B. J. F. (2014). Paseos y circuitos. Matemáticas Discretas Aplicaciones y ejercicios.

(pp. 199- 209). https://elibro-net.bibliotecavirtual.unad.edu.co/es/ereader/unad/39454

Villalpando, B. J. F. (2014). Representaciones matriciales. Matemáticas Discretas Aplicaciones y

ejercicios. (pp. 213- 215). https://elibro-

net.bibliotecavirtual.unad.edu.co/es/ereader/unad/39454

Villalpando, B. J. F. (2014). Isomorfismo de grafos. Matemáticas Discretas Aplicaciones y

ejercicios. (pp. 216 - 217). https://elibro-

net.bibliotecavirtual.unad.edu.co/es/ereader/unad/39454

Villalpando, B. J. F. (2014). Árboles. Matemáticas Discretas Aplicaciones y ejercicios. (pp. 242-

243). https://elibro-net.bibliotecavirtual.unad.edu.co/es/ereader/unad/39454

Villalpando, B. J. F. (2014). Árboles enraizados. Matemáticas Discretas Aplicaciones y

ejercicios. (pp. 244- 248). https://elibro-

net.bibliotecavirtual.unad.edu.co/es/ereader/unad/39454

Villalpando, B. J. F. (2014). Recorridos de un árbol. Matemáticas Discretas Aplicaciones y

ejercicios. (pp. 257 - 260). https://elibro-

net.bibliotecavirtual.unad.edu.co/es/ereader/unad/39454

14