GRAFOS
4.1 Importancia:
La importancia de los grafos radica en su capacidad para modelar relaciones y estructuras
complejas, como redes sociales, sistemas de transporte o redes de comunicación. Son fundamentales
para resolver problemas de optimización, rutas, y análisis de datos en diversas disciplinas como
matemáticas, informática y ciencias sociales.
Definición: Un grafo es una estructura matemática que consta de:
• Vértices (nodos): Los elementos principales del grafo.
• Aristas: Conexiones entre los vértices.
Formalmente, un grafo se define como G=(V,A), donde V es el conjunto de vértices y A es el conjunto
de aristas.
Representación gráfica:
Universidad de Pamplona. (2012). Teoría de grafos.
[Link]
/[Link]
4.2 Tipos de grafos
1. Grafo simple
Definición: Un grafo G = (V, E) donde V es el conjunto de vértices y E es el conjunto de
aristas. No tiene bucles ni aristas múltiples.
• Ejemplo:
Conjunto de vértices: V={A,B,C}
Conjunto de aristas: E={{A,B},{B,C},{A,C}}
No hay aristas repetidas ni bucles, es decir, no hay una arista de un vértice hacia sí
mismo.
2. Grafo dirigido (Dígrafo)
Definición: Un grafo en el que cada arista tiene una dirección, representado por pares
ordenados de vértices.
• Ejemplo:
Conjunto de vértices: V={A,B,C}
Conjunto de aristas: E={(A,B),(B,C),(C,A)}
Aquí (A,B) indica que hay una arista desde A hasta B, pero no necesariamente desde
B hacia A.
3. Grafo no dirigido
Definición: Las aristas no tienen dirección.
• Ejemplo:
Conjunto de vértices: V={A,B,C,D}
Conjunto de aristas: E={{A,B},{A,C},{B,C},{C,D}}
Las aristas no están dirigidas, solo conectan dos vértices de manera indistinta.
4. Grafo ponderado
Definición: A las aristas se les asigna un peso.
• Ejemplo:
Conjunto de vértices: V={A,B,C}
Conjunto de aristas con peso: E={{A,B,3},{B,C,5},{A,C,2}}
La arista entre A y B tiene un peso de 3, entre B y C tiene un peso de 5, y entre A y C
tiene un peso de 2.
5. Grafo bipartito
Definición: El conjunto de vértices puede dividirse en dos subconjuntos disjuntos, y todas las
aristas conectan vértices de subconjuntos diferentes.
• Ejemplo:
-Conjunto de vértices: V={A,B,C,D,E}
-Subconjuntos: V1={A,B} V2={C,D,E}
-Conjunto de aristas: E={{A,C},{A,D},{B,E}}
Las aristas solo conectan vértices de V1 con vértices de V2.
6. Grafo completo
Definición: Cada par de vértices está conectado por una arista.
• Ejemplo:
Conjunto de vértices: V={A,B,C}
Conjunto de aristas: E={{A,B},{A,C},{B,C}}
Todos los pares de vértices están conectados por aristas.
7. Grafo conexo
Definición: Existe al menos un camino entre cada par de vértices.
• Ejemplo:
Conjunto de vértices: V={A,B,C,D}
Conjunto de aristas: E={{A,B},{B,C},{C,D}}
Puedes viajar desde cualquier vértice hasta cualquier otro siguiendo las aristas, por lo
que el grafo es conexo.
8. Grafo acíclico
Definición: Un grafo sin ciclos, es decir, no existe un camino que comience y termine en el
mismo vértice.
• Ejemplo:
Conjunto de vértices: V={A,B,C,D}
Conjunto de aristas: E={{A,B},{B,C},{C,D}}
No hay ciclos en este grafo; no puedes regresar al punto de partida sin repetir aristas.
9. Multigrafo
Definición: Un grafo en el que puede haber varias aristas entre el mismo par de vértices.
• Ejemplo:
Conjunto de vértices: V={A,B}
Conjunto de aristas: E={{A,B},{A,B},{A,B}}
Hay tres aristas distintas entre los vértices A y B.
10. Grafo regular
Definición: Todos los vértices tienen el mismo grado, es decir, el mismo número de aristas
conectadas.
• Ejemplo:
Conjunto de vértices: V={A,B,C,D}
Conjunto de aristas: E={{A,B},{A,C},{B,D},{C,D}}
Cada vértice tiene exactamente 2 aristas conectadas, por lo que es un grafo regular de
grado 2.
11. Grafo plano
Definición: Un grafo que puede dibujarse en un plano de forma que sus aristas no se crucen.
• Ejemplo:
Conjunto de vértices: V={A,B,C,D}
Conjunto de aristas: E={{A,B},{A,C},{B,D},{C,D}}
Este grafo puede dibujarse en un plano sin que sus aristas se crucen.
12. Grafo dirigido acíclico (DAG)
Definición: Un dígrafo sin ciclos dirigidos.
• Ejemplo:
Conjunto de vértices: V={A,B,C}
Conjunto de aristas: E={(A,B),(B,C)}
No existe un camino que regrese al punto de partida, por lo que es acíclico.
13. Grafo euleriano
Definición: Un grafo en el que existe un ciclo que recorre todas las aristas exactamente una
vez.
Ejemplo:
Conjunto de vértices: V={A,B,C,D}
Conjunto de aristas: E={{A,B},{B,C},{C,D},{D,A}}
Puedes recorrer todas las aristas comenzando en un vértice y regresando al mismo sin repetir
ninguna arista.
14. Grafo hamiltoniano
Definición: Un grafo en el que existe un ciclo que pasa por todos los vértices exactamente
una vez.
• Ejemplo:
Conjunto de vértices: V={A,B,C,D}
Conjunto de aristas: E={{A,B},{B,C},{C,D},{D,A}}
Puedes visitar todos los vértices una sola vez y regresar al punto de partida.
4.3 Características: Grado, Adyacencia, Incidencia, Conectividad
El grado de un vértice es el número de aristas que están incidentes a él. Para un grafo dirigido,
se distingue entre el grado entrante y el grado saliente.
• Ejemplo de grafo no dirigido:
Vértices: A, B, C, D
Aristas: (A, B), (B, C), (C, D), (A, D)
Grado de A: 2 (A está conectado a B y D)
Grado de B: 2 (B está conectado a A y C)
Grado de C: 2 (C está conectado a B y D)
Grado de D: 2 (D está conectado a A y C)
Adyacencia:
Definición: Dos vértices son adyacentes si están conectados por una arista.
• Ejemplo:
Vértices: A, B, C
Aristas: (A, B), (B, C)
A y B son adyacentes, al igual que B y C, pero A y C no lo son.
Incidencia:
Definición: Una arista incide en un vértice si conecta ese vértice con otro.
• Ejemplo:
Vértices: A, B, C
Aristas: (A, B), (B, C)
La arista (A, B) incide en A y B.
La arista (B, C) incide en B y C.
Conectividad:
Definición: Un grafo es conexo si hay un camino entre cualquier par de vértices. Si no existe
tal camino, el grafo es desconexo.
• Ejemplo:
Grafo 1 (conexo): Vértices A, B, C, D con las aristas (A, B), (B, C), (C, D)
Hay un camino entre cualquier par de vértices, por lo tanto es conexo.
Grafo 2 (desconexo): Vértices A, B, C con las aristas (A, B)
No hay un camino entre A y C, por lo tanto es desconexo.
4.4 Trayectoria: Simple, Elemental, Cerrado, Ciclo
Trayectoria Simple:
Definición: Una trayectoria en la que no se repiten vértices.
• Ejemplo:
Vértices: A, B, C, D
Aristas: (A, B), (B, C), (C, D)
Trayectoria simple: A → B → C → D
No se repiten vértices ni aristas.
Trayectoria Elemental:
Definición: Una trayectoria en la que no se repiten vértices ni aristas.
• Ejemplo:
Vértices: A, B, C, D
Aristas: (A, B), (B, C), (C, D), (D, A)
Trayectoria elemental: A → B → C → D → A
No se repiten vértices ni aristas.
Trayectoria Cerrada:
Definición: Una trayectoria en la que el primer y último vértice son el mismo, pero se pueden
repetir los vértices intermedios.
• Ejemplo:
Vértices: A, B, C
Aristas: (A, B), (B, C), (C, A)
Trayectoria cerrada: A → B → C → A
El primer y último vértice son A, pero los vértices intermedios (B y C) no se repiten.
Ciclo:
Definición: Un caso especial de trayectoria cerrada en la que no se repiten vértices (excepto el
primero y último).
• Ejemplo:
Vértices: A, B, C, D
Aristas: (A, B), (B, C), (C, D), (D, A)
Ciclo: A → B → C → D → A
Es una trayectoria cerrada y no se repiten vértices, salvo el primero y último.
4.5 Árboles, Definición y Representación.
Árboles:
Un árbol es una estructura fundamental en la teoría de grafos y las estructuras discretas.
Es ampliamente utilizada en ciencias de la computación y matemáticas para modelar relaciones
jerárquicas y resolver problemas que implican ordenaciones. A continuación, se detalla su
definición, características, y representación.
Formalmente, un árbol es un grafo no dirigido, conexo y acíclico.
En términos de nodos y aristas: Está formado por un conjunto de nodos (o vértices) y un
conjunto de aristas (o arcos) que los conectan.
Existe exactamente un único camino entre cualquier par de nodos.
Si se orienta como una estructura jerárquica, se denomina árbol enraizado, donde: Un nodo
especial se identifica como raíz.
Los nodos se dividen en:
• Raíz: Nodo inicial en los árboles enraizados.
• Hoja: Nodo sin hijos.
• Nodos internos: Nodos que no son hojas ni la raíz.
• Altura de un árbol: Longitud máxima del camino desde la raíz a cualquier hoja.
Representación de los Árboles
Lista de Adyacencia:
Representa las conexiones del árbol como listas para cada nodo.
• Ejemplo para un árbol:
Nodo 1: [2, 3]
Nodo 2: [1, 4, 5]
Nodo 3: [1]
Un árbol binario es una estructura de datos que consiste en nodos conectados entre sí, donde
cada nodo tiene como máximo dos hijos (izquierdo y derecho). Los árboles binarios son
utilizados en una variedad de aplicaciones, como la búsqueda y el almacenamiento de datos.
Estructura de un árbol binario
Un árbol binario está compuesto por nodos, que tienen las siguientes propiedades:
1. Valor: Cada nodo tiene un valor asociado.
2. Hijo izquierdo: Cada nodo puede tener un hijo izquierdo, que es otro nodo.
3. Hijo derecho: Cada nodo puede tener un hijo derecho, que es otro nodo.
Ejemplo de un árbol binario
1
/ \
2 3
/\ /\
4 56 7
```
En este ejemplo, el nodo 1 es la raíz del árbol, y tiene dos hijos: el nodo 2 y el nodo 3. El nodo
2 tiene dos hijos: el nodo 4 y el nodo 5. El nodo 3 tiene dos hijos: el nodo 6 y el nodo 7.
Recorrido Preorden
En un recorrido preorden, se visita primero la raíz del árbol, luego se recorre el subárbol
izquierdo y finalmente se recorre el subárbol derecho.
• Ejemplo:
Supongamos que tenemos el siguiente árbol binario:
1
/ \
2 3
/\ /\
4 56 7
```
El recorrido preorden sería:
1, 2, 4, 5, 3, 6, 7
Recorrido En Orden
En un recorrido en orden, se recorre primero el subárbol izquierdo, luego se visita la raíz del
árbol y finalmente se recorre el subárbol derecho.
• Ejemplo:
Usando el mismo árbol binario del ejemplo anterior:
1
/ \
2 3
/\ /\
4 56 7
```
El recorrido en orden sería:
4, 2, 5, 1, 6, 3, 7
Recorrido Postorden
En un recorrido postorden, se recorre primero el subárbol izquierdo, luego se recorre el
subárbol derecho y finalmente se visita la raíz del árbol.
• Ejemplo:
Usando el mismo árbol binario del ejemplo anterior:
1
/ \
2 3
/\ /\
4 56 7
```
El recorrido postorden sería:
4, 5, 2, 6, 7, 3, 1
Referencia:
[Link]
rrido_arboles.pdf
[Link]
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms
(3rd ed.). MIT Press.
Diestel, R.(2017).Graph Theory(5th ed.).Springer.
ISBN: 978-3-662-53621-6.
DOI: 10.1007/978-3-662-53622-3