1

Teoría de Números

Tarea 4 – Arboles y Grafos

Alfonso Miguel Estrada Padilla, Luis Miguel Armenta Hurtado, Yuris Paola
Ramos Guerra, Jesús Javier Hernández García y Daniel de Jesús Candelario Macias

Grupo_1

Tutor

Otto David Alvarado Esquivel

Universidad Nacional Abierta y a Distancia UNAD

Escuela de Ciencias de la Educación
Licenciatura en Matemáticas

2024
 2

Introducción

El siguiente trabajo tiene como propósito estudiar la definición de lo que es un

grafo, identificar sus elementos y sus principales características para su elaboración.

De manera colaborativa cada docente en formación asumirá un rol y realizará los

respectivos ejercicios planteados en la guía de actividades, cada ejercicio permitirá

obtener una mayor comprensión de los que es un grafo y de que manera se puede

representar este, teniendo en cuenta que los grafos se pueden representar de manera

grafica o también por medio de su matriz de adyacencia.

Se busca finalmente que los docentes en formación comprender con claridad el

concepto de grafo sus elementos mas importante y la manera como se realizan una

matriz de adyacencia de un grafo y viceversa, como dibujar un grafo dada su matriz de

adyacencia.
 3

Tabla 1
Distribución de Ejercicios

Nombre del Estudiante Ejercicios Realizados

Alfonso Miguel Estrada Padilla Punto 1 – Literal b, e

Punto 2 – Literal b
Punto 3 – Literal b
Punto 5 – Literal b
Punto 6 – Literal b
Luis Miguel Armenta Hurtado Punto 1 – Literal a
Punto 2 – Literal a
Punto 3 – Literal a
Punto 5 – Literal a
Punto 6 – Literal a
Yuris Paola Ramos Guerra Punto 1 – Literal c
Punto 6 – Literal c
Jesús Javier Hernández García Punto 1 – Literal d
Punto 6 – Literal d
Daniel de Jesús Candelario Macias Punto 1 – Literal f
 4

1. Para cada uno de los grafos en los siguientes ejercicios:

Literal A. Determine todas las aristas que inciden en 𝑣1

Para determinar todas las aristas que inciden en 𝒗𝟏, lo primero será buscar el
vértice 𝒗𝟏 en cada uno de los dos grafos, buscando tanto las conexiones y bucles (Lazos)
que aparecen entre cada uno de los vértices que forman el grafo. Luego escribimos las
aristas que conectan con el vértice 𝒗𝟏, incluyendo también los bucles teniendo en cuenta
que estos salen de un vértice y vuelven a él.

Para esto en el 𝑔𝑟𝑎𝑓𝑜 1 desde el vértice 𝒗𝟏 inciden: 𝒆𝟏, 𝒆𝟐, 𝒆𝟑, 𝒆𝟒, 𝒆𝟓

Para él 𝐺𝑟𝑎𝑓𝑜 2 desde el vértice 𝒗𝟏 inciden: 𝒆𝟏, 𝒆𝟐, 𝒆𝟑, 𝒆𝟒, 𝒆𝟓, 𝒆𝟔
 5

Literal B. Encuentre todos los vértices adyacentes a 𝑣3

Teniendo en cuenta la definición formal de lo que es un vértice adyacente:

Sea G un grafo. Los vértices 𝑢, 𝑣 ∈ 𝑉(𝐺) se denominan adyacentes si existe una

arista 𝑒 ∈ 𝐸(𝐺) tal que 𝑒 = (𝑢, 𝑣). Esto significa que son vértices adyacentes, aquellos
vértices que están unidos por alguna arista.
Ahora bien, teniendo claro el concepto podemos concluir lo siguiente:
Habiendo identificado el V3 en el grafo 1 podemos decir que:

El 𝑣3 es adyacente a 𝑣1, 𝑣4 𝑦 𝑣5

Para el grafo 2

Habiendo identificado el 𝑣3 podemos decir que:

El 𝑣3 es adyacente a 𝑣1 𝑦 𝑣7

Literal C. Determine todos los bucles

Bucle: Arista que conecta un vértice consigo mismo.

Grafo 1: e6, e8, e14.
Grafo 2: e7, e1, e8

Literal D. Busque todas las aristas adyacentes a 𝑒1

En el Grafo 1, localizamos el nodo correspondiente a e1. Luego, revisamos qué

aristas están conectadas a e1:

Identificar e1: En el grafo, e1 está conectado a otros nodos.

Aristas adyacentes a e1: Al observar el grafo, las aristas que se conectan a e1

son: 𝑒2, 𝑒3, 𝑒4, 𝑒5, 𝑒7, 𝑒11

Para el Grafo 2, repetimos el proceso:

Identificar e1: Buscamos e1 y revisamos sus conexiones.

Aristas adyacentes a e1: Las aristas conectadas a e1 son: 𝑒2, 𝑒3, 𝑒4, 𝑒5, 𝑒6
 6

Literal E. Encuentre todas las aristas paralelas.

Definición de aristas paralelas: Dos aristas son paralelas si los vértices de

entrada y llegada son el ismo para ambos.

Aristas paralelas en Grafo 1: 𝑒4 𝑦 𝑒5; 𝑒9 𝑦 𝑒10; 𝑒12 𝑦 𝑒13

Aristas paralelas en Grafo 2: 𝑒45𝑦 𝑒6; 𝑒10 𝑦 𝑒11

Literal F. Encuentre todos los vértices aislados

En el Grafo 1, los vértices aislados son aquellos que no tienen ninguna arista
conectada. Al analizar el grafo, encontramos que:
Vértice 8 está aislado porque no tiene conexiones.
Vértice 9 también está aislado por la misma razón.
Por lo tanto, la respuesta es que los vértices aislados en el Grafo 1 son 8 y 9.
En el Grafo 2, el vértice 5 no tiene aristas conectadas, por lo que es un vértice
aislado.

2. Dibujar el grafo que cumple con:

Literal A. El grafo 𝐺 tiene el conjunto de vértices {𝑣1 , 𝑣2, 𝑣3, 𝑣4} y el conjunto de
aristas {𝑒1, 𝑒2, 𝑒3, 𝑒4, 𝑒5}, con la función de punto extremo-arista definida
como sigue:

Para dibujar el grafo 𝐺 con los conjuntos de vértices dados {𝑣1 , 𝑣2, 𝑣3, 𝑣4} y el
conjunto de aristas {𝑒1, 𝑒2, 𝑒3, 𝑒4, 𝑒5}.
 7

Lo primero que se realiza es Dibujar los cuatro vértices como puntos, luego
dibujando las aristas:

𝒗𝟏 − 𝒗𝟑 Se le colocara la arista 𝒆𝟏

𝒗𝟐 − 𝒗𝟑 Se le colocara la arista 𝒆𝟐

𝒗𝟏 − 𝒗𝟐 Se le colocara la arista 𝒆𝟑

También se dibujará un bucle en 𝒗𝟒 (Vértice aislado) se le colocará la arista 𝒆𝟒

Por último, se dibuja un bucle en el vértice 𝒗𝟏 que será la arista 𝒆𝟓

Literal B. El grafo H tiene el conjunto de vértices {𝑣1, 𝑣2, 𝑣3, 𝑣4, 𝑣5} y el conjunto
de aristas {𝑒1, 𝑒2, 𝑒3, 𝑒4, 𝑒5} con la función punto extremo-arista definida como
sigue:
 8

Para diseñar el grafo se tienen en cuenta las condiciones

dadas en la tabla. Son cinco aristas de las cuales cada
arista tiene conexión con los vértices dados.
Podemos verificar que el grafo diseñado cumple con las
condiciones dadas en cada una de las aristas.

3. Resuelve los siguientes ejercicios

Literal A. Encuentre los grafos dirigidos que tienen las siguientes matrices de

adyacencia.

Se realizan los grafos Dirigidos según las matrices de adyacencia brindadas

𝑴𝟏 𝑴𝟐
 9

Literal B. Determine las matrices de adyacencia para los siguientes grafos (no

dirigidos)

4. Cada integrante del grupo realiza, crea o inventa un grafo no dirigido con su
respectiva matriz de adyacencia (el grafo debe corresponder en coherencia a
la matriz). Para su elaboración pueden ser creativos en cuanto a la forma o
estructura del grafo y en como se conectan los vértices con las aristas. Deben
tener en cuenta los siguientes aspectos: mínimo 6 vértices, un bucle o lazo, un
vértice aislado, una arista paralela

Docente en Formación: Luis Miguel Armenta Hurtado

El grafo va a tener 6 vértices como lo menciona el enunciado los cuales estarán
definidos de la siguiente forma:
Vértices:

𝑨 𝑩 𝑪 𝑫 𝑬 (𝑸𝒖𝒆 𝒔𝒆𝒓𝒂 𝒆𝒍 𝒗𝒆𝒓𝒕𝒊𝒄𝒆 𝒂𝒊𝒔𝒍𝒂𝒅𝒐) 𝑭

Las aristas serán de:

 10

𝑨 − 𝑩; 𝑨 − 𝑪; 𝑩 − 𝑪; 𝑪 − 𝑫; 𝑫 − 𝑫 (𝐵𝑢𝑐𝑙𝑒 𝑜 𝑙𝑎𝑧𝑜 𝑒𝑛 𝑒𝑠𝑡𝑒 𝑎𝑟𝑖𝑠𝑡𝑎);

𝑭 − 𝑭(𝐵𝑢𝑐𝑙𝑒 𝑜 𝑙𝑎𝑧𝑜 𝑒𝑛 𝑒𝑠𝑡𝑒 𝑎𝑟𝑖𝑠𝑡𝑎); 𝑩 − 𝑭 (𝐴𝑟𝑖𝑠𝑡𝑎𝑠 𝑝𝑎𝑟𝑎𝑙𝑒𝑙𝑎 𝑒𝑛𝑡𝑟𝑒 𝐵 𝑦 𝐹)

𝑬 (𝑣𝑒𝑟𝑡𝑖𝑐𝑒 𝑎𝑖𝑠𝑙𝑎𝑑𝑜)

Matriz de adyacencia Grafo

Docente en Formación: Alfonso Miguel Estrada Padilla

Grafo: Elaboración propia Matriz de Adyacencia
 11

Docente en Formación: Yuris Paola Ramos Guerra

Matriz de Adyacencia Grafo

0 2 1 0 0 0
2 0 0 1 0 0
1 0 1 1 0 0
𝑀=
0 1 1 0 1 0
0 0 0 1 0 0
[0 0 0 0 0 0]

Docente en Formación: Daniel de Jesús Candelario Macias

Matriz Adyacencia Grafo

1100000
1010000
0101000
𝑀 = 0010100
0001010
0000100
[0 0 0 0 0 0 0 ]

Docente en Formación: Jesús Javier Hernández García

Vértices: A, B, C, D, E, F
Conexiones:

A conecta con B y tiene un lazo (se conecta consigo mismo).

B conecta con A, C, y D.
 12

C conecta con B y tiene una arista paralela hacia B (es decir, hay dos
aristas entre C y B).
D conecta con B y E.
E conecta con D y F.
F es un vértice aislado (no se conecta con ningún otro vértice).

Matriz de Adyacencia Grafo

5. Determine si cada par de grafos es isomorfo comparando sus matrices de

adyacencia

Literal A.
 13

Para lograr determinar si los grafos 1 𝑦 2 son isomorfos, se debe comparar sus
matrices de adyacencia. Teniendo en cuenta que Dos grafos son isomorfos si existe una
correspondencia entre sus vértices que preservan las adyacencias.
Ahora se construyen las matrices de adyacencia de cada grafo:

Para el grafo 1 que tiene los vértices 𝟏, 𝟐, 𝟑, 𝟒, 𝟓

Su matriz de adyacencia:
𝟎 𝟎 𝟏 𝟏 𝟏
𝟎 𝟎 𝟏 𝟏 𝟏
𝟏 𝟏 𝟎 𝟏 𝟎
𝟏 𝟏 𝟏 𝟎 𝟎
[𝟏 𝟏 𝟎 𝟎 𝟎]
Para el grafo 2 que tiene los vértices 𝟏, 𝟐, 𝟑, 𝟒, 𝟓

Su matriz de adyacencia:
𝟎 𝟎 𝟏 𝟏 𝟏
𝟎 𝟎 𝟏 𝟏 𝟏
𝟏 𝟏 𝟎 𝟏 𝟎
𝟏 𝟏 𝟏 𝟎 𝟎
[𝟏 𝟏 𝟎 𝟎 𝟎]

Si se comparan las matrices de adyacencia, se observa que estas son iguales,

por lo tanto podemos concluir que estos dos grafos, son isomorfos.
Literal B.
 14

Dos grafos son isomorfos si sus matrices de adyacencia son iguales, en este
sentido vamos a encontrar las matrices de cada grafo
Matriz Adyacencia Grafo 1. Matriz Adyacencia Grafo 2.

Podemos observar que las dos matrices de adyacencia del par de grafos no son
iguales, por lo tanto, concluimos que este par de grafos no cumplen las condiciones para
ser isomorfo, aunque tienen la misma cantidad de vértices, no tienen la misma cantidad
de aristas ni tampoco tienen el mismo valor de grado.

6. La siguiente es una matriz de adyacencia para un grafo:

Responda las siguientes preguntas mediante el examen de la matriz y sus

potencias, no dibuje el grafo. Deben realizar el procedimiento del producto de
matrices:

Literal A. ¿Cuántos caminos de longitud 2 existen de 𝑣3 y 𝑣4

Para poder obtener la solución de la pregunta sin realizar el grafo se aplica la

siguiente propiedad:

En un grafo 𝐺 el número 𝐾 trayectorias esta codificado por la matriz de adyacencia

de la siguiente manera:

La matriz 𝐴𝐾 dice que el número 𝐾 trayectorias que hay desde el vértice 𝒊 al

vértice 𝒋, por lo que si se quiere calcular la longitud 2 se resuelve la matriz 𝐴2 y de longitud
3 a la matriz 𝐴3 .
 15

Ahora se realizará el procedimiento con las multiplicaciones de matrices:

0 0 1 1 0 0 1 1 1 2 1 3
1 1 2 0 1 1 2 0 3 3 3 5
𝐴2 = 𝐴. 𝐴 ( )∗ ( )= ( )
1 1 0 2 1 1 0 2 1 3 5 3
0 1 1 1 0 1 1 1 2 3 3 3
Dando respuesta a la pregunta, en la matriz 𝐴2 se buscará la interacción fila 3
columna 4 y de esta manera se observan que son 5 caminos.

Literal B. ¿cuántos caminos de longitud 2 existen de 𝑣1 y 𝑣2

Lo primero que vamos a realizar es multiplicar dos veces la matriz de adyacencia

dada. Llamaremos la matriz M
0 0 1 1 0 0 1 1 1 2 1 3
1 1 2 0 1 1 2 0 3 3 3 5
𝑀2 = [ ].[ ]= [ ]
1 1 0 2 1 1 0 2 1 3 5 3
0 1 1 1 0 1 1 1 2 3 3 3

El producto de las dos matrices se obtiene en multiplicar los elementos de la

primera fila de la matriz uno con cada uno de los elementos de las columnas de las
matrices dos y así sucesivamente, la fila dos con cada una de las columnas de la
segunda matriz. El resultado de la matriz 𝑀2
𝑀11 𝑀12 𝑀13 𝑀14
𝑀 𝑀22 𝑀23 𝑀24
𝑀2 = [ 21 ]
𝑀31 𝑀32 𝑀33 𝑀34
𝑀41 𝑀42 𝑀43 𝑀44

𝑀11 = 1 𝑀12 =2 𝑀13 = 1 𝑀14 = 3

𝑀21 = 3 𝑀22 =3 𝑀23 = 3 𝑀24 = 5
𝑀31 = 1 𝑀32 =3 𝑀33 = 5 𝑀34 = 3
𝑀41 = 2 𝑀42 =3 𝑀43 = 3 𝑀44 = 3

Observando la matriz 𝑀2 podemos concluir que para la entrada de 𝑣1 a 𝑣2 existes

2 caminos.
 16

Literal C. ¿Cuántos caminos de longitud 3 existen de 𝑣1 y 𝑣3

Llamaremos la matriz M y calculamos el producto de 𝑀2

0 0 1 1 0 0 1 1 1 2 1 3
1 1 2 0 1 1 2 0 3 3 3 5
𝑀2 = [ ].[ ]= [ ]
1 1 0 2 1 1 0 2 1 3 5 3
0 1 1 1 0 1 1 1 2 3 3 3

Como nos pide camino de longitud 3 multiplicamos nuevamente la matriz 𝑀2 por

la matriz M
1 2 1 3 0 0 1 1 3 6 8 6
3 3 3 5 1 1 2 0 6 11 14 14
𝑀2 . 𝑀 = [ ].[ ]= [ ]
1 3 5 3 1 1 0 2 8 11 10 14
2 3 3 3 0 1 1 1 6 9 11 11

Observando la nueva matriz podemos concluir que de 𝑣1 a 𝑣3 existen 8 caminos

Literal D. ¿Cuántos caminos de longitud 3 existen de 𝑣2 y 𝑣4

Habiendo multiplicado la matriz en su potencia 3

1 2 1 3 0 0 1 1 3 6 8 6
3 3 3 5 1 1 2 0 6 11 14 14
𝑀2 . 𝑀 = [ ].[ ]= [ ]
1 3 5 3 1 1 0 2 8 11 10 14
2 3 3 3 0 1 1 1 6 9 11 11

Podemos concluir que de 𝑣2 a 𝑣4 existen 14 caminos