Grafos

Unidad 5. Análisis de algoritmos
Voraces

¿Qué es un grafo?
¿Cómo se conforma un grafo?
Componentes del grafo (aristas, vértices y caminos)
Caminos
Clasificación de Grafos

Elaboró: Mtra. Rosy

Sánchez

Definiciones básicas de teoría de grafos

Open Ended

¿Qué es un grafo?

¿Qué es un grafo?

• Un grafo es un conjunto de objetos llamados

vértices o nodos unidos por enlaces llamados
aristas o arcos, que permiten representar
relaciones

binarias

entre

elementos

de

un

conjunto.

Elaboró: Mtra. Rosy

Sánchez

¿Cómo se conforma un grafo?

• Típicamente,

un

grafo

se

representa

gráficamente

como

un

conjunto

de

puntos

(vértices o nodos) unidos por líneas (aristas).

Elaboró: Mtra. Rosy

Sánchez

Multiple Choice

Un grafo se conforma de

• aristas y vértices

• De caminos

• de rutas para llegar a un camino

Componentes de un grafo

Aristas: son las líneas con las que se une un grafo y
con la que se construyen también caminos.

Elaboró: Mtra. Rosy

Sánchez

Componentes del grafo

• Aristas

adyacentes:

dos

aristas

son

adyacentes si tienen un vértice en común.

Elaboró: Mtra. Rosy

Sánchez

Componentes del grafo

• Aristas paralelas: dos o más aristas que son

incidentes (que se conectan) al menos dos
vértices iguales.

Elaboró: Mtra. Rosy

Sánchez

Componentes del grafo

• Lazos:

es una arista cuyos extremos inciden

sobre el mismo vértice.

Elaboró: Mtra. Rosy

Sánchez

Componentes del grafo

• Vértices: son los puntos o nodos con los que

está conformado un grafo.

Elaboró: Mtra. Rosy

Sánchez

Componentes del grafo

• Vértices

adyacentes:

los

vértices

son

adyacentes cuando comparten la misma arista.

Elaboró: Mtra. Rosy

Sánchez

Componentes del grafo

• Vértice aislado: es un vértice de grado cero.

Vértice aislado

Elaboró: Mtra. Rosy

Sánchez

Componentes del grafo

• Vértice

pendiente:

es

aquel

grafo

que

contiene sólo una arista, es decir que tiene grado
1.

Elaboró: Mtra. Rosy

Sánchez

Camino

• Secuencia de vértices dentro de un grafo tal que

exista una arista entre cada vértice y el siguiente.

• Dos vértices están conectados

si

existe un

camino que vaya de uno a otro.

• Conjunto de vértices que hay que recorrer para

llegar desde un nodo origen hasta un nodo
destino.

Elaboró: Mtra. Rosy

Sánchez

Bucle

• Un bucle es una arista que conecta a un vértice

consigo mismo. Es un ciclo de longitud 1.

Elaboró: Mtra. Rosy

Sánchez

Ciclo.

• Un ciclo es un camino donde el origen del

camino es igual a su destino.

Elaboró: Mtra. Rosy

Sánchez

En grafos Bucle y Ciclo son dos
conceptos diferentes

Bucle: arista que se conecta al mismo vértice dentro de un grafo.

• Ciclo: camino donde el origen y destino es

igual dentro de un grafo.

Elaboró: Mtra. Rosy

Sánchez

Open Ended

Se le conoce como vértice de grado cero

Multiple Choice

Secuencia de vértices dentro de un grafo tal que exista una arista entre cada vértice y el siguiente.

• Camino

• Bucle

• Ciclo

• Lazo

Tipos de Camino

• Camino simple:

todos los nodos que lo

forman son distintos.

• Camino abierto: diferente punto de partida al

de llegada.

• Camino cerrado: cuando el punto de llegada

es el mismo que el de partida.

Elaboró: Mtra. Rosy

Sánchez

Ejemplo de camino

• Camino desde a hasta d→<a, b, e, c, d>.

Elaboró: Mtra. Rosy

Sánchez

Longitud de camino

• Es el número de arcos del camino
• Ejemplos:
• Longitud

del

camino

desde

a

hasta

d

→

<a,b,e,c,d> es 4. (figura a)

Elaboró: Mtra. Rosy

Sánchez

Match

Identifica el concepto

• Camino Simple

• Camino Abierto

• Camino Cerrado

• Longitud de camino

• Bucle

Todos los nodos que lo forman son distintos

Es un camino donde el punto de partida es diferente al de llegada.

Cuando el punto de llegada es el mismo que él de partida

Número de arcos que tienes que recorres de un nodo a otro.

Es una arista que conecta a un vértice consigo mismo.

• Todos los nodos que lo forman son distintos

• Es un camino donde el punto de partida es diferente al de llegada.

• Cuando el punto de llegada es el mismo que él de partida

• Número de arcos que tienes que recorres de un nodo a otro.

• Es una arista que conecta a un vértice consigo mismo.

Longitud de camino

• Ejemplo:
• longitud

del

camino

desde

a

hasta

d

→

<a,b,e,f,b,e,c,d> es 7. (figura b)

Elaboró: Mtra. Rosy

Sánchez

Longitud de caminos

Camino entre 4 y 7

C={4,6,9,7}

Longitud: 3

Elaboró: Mtra. Rosy

Sánchez

Clasificación de Grafos

Grafo Simple
Multigrafo
Grafo Dirigido ó Dígrafo
Grafo No Dirigido
Grafo conexo
Grafo No conexo

Elaboró: Mtra. Rosy

Sánchez

Grafo simple

• Es aquel que acepta una sola arista uniendo dos

vértices cualesquiera.

• Es la definición estándar de un grafo.
• No

contiene aristas paralelas, lazos, ni aristas

dirigidos.

Elaboró: Mtra. Rosy

Sánchez

Multígrafo

• Grafo que cuenta con múltiples aristas entre dos

vértices se denomina multígrafo.

Elaboró: Mtra. Rosy

Sánchez

Grafo Dirigido o Dígrafo

• Un grafo dirigido o dígrafo, es un tipo de grafo

en el cual el conjunto de las aristas tiene una
dirección definida.

Elaboró: Mtra. Rosy

Sánchez

Grafo Dirigido o Dígrafo

• Un grafo dirigido es aquel en el que todas sus aristas

tienen sentido o dirección.

• La relación sobre V no es simétrica. Las aristas se

representan como un par ordenado. En este ejemplo:

• V={a, b, c, e}
• E={(a,b),(a,c),(a,e), (b,e), (c,e)}

Elaboró: Mtra. Rosy

Sánchez

Grafo No Dirigido

• Un grafo no dirigido es aquel en el que todas sus

aristas son bidireccionales. La relación sobre V
es simétrica. En este ejemplo:

• V={a, b, c, e}
• E={{a,b}, {a,c}, {a,e}, {b,e}, {c,e}}

Elaboró: Mtra. Rosy

Sánchez

Grafo No Dirigido

• Si las aristas no especifican un sentido en particular.

El grafo de la figura 1 se define por: V = [1..7],
A = { 〈1,2〉 , 〈1,3〉 , 〈2,1〉 , 〈2,3〉 , 〈2,4〉 , 〈3,1〉 , 〈3,2〉 ,
〈3,4〉 , 〈3,5〉 , 〈4,2〉 , 〈4,3〉 , 〈5,3〉 , 〈5,6〉 , 〈5,7〉 , 〈6,5〉 ,
〈7,5〉 }.
La longitud del camino 1, 3, 5, sería 2.

Elaboró: Mtra. Rosy

Sánchez

Elaboró: Mtra. Rosy

Sánchez

Match

Selecciona la imagen con la definición del grafo.

Es aquel que acepta una sola arista uniendo dos vértices cualesquiera.

Grafo que cuenta con múltiples aristas entre dos vértices

Es un tipo de grafo en el cual el conjunto de las aristas tiene una dirección definida.

Un grafo en el que todas sus aristas son bidireccionales.

• Es aquel que acepta una sola arista uniendo dos vértices cualesquiera.

• Grafo que cuenta con múltiples aristas entre dos vértices

• Es un tipo de grafo en el cual el conjunto de las aristas tiene una dirección definida.

• Un grafo en el que todas sus aristas son bidireccionales.

Grafo Conexo y No Conexo

• Un grafo se dice conexo si, para cualquier par de

vértices a y b en G, existe al menos una
trayectoria (una sucesión de vértices adyacentes
que no repita vértices) de a a b

Elaboró: Mtra. Rosy

Sánchez

Ejemplos Grafos Conexos

Elaboró: Mtra. Rosy

Sánchez

Ejemplos Grafos No Conexo

Elaboró: Mtra. Rosy

Sánchez

Ejemplos de grafos conexos y no
conexos

Elaboró: Mtra. Rosy

Sánchez

Grado o valencia de un vértice

Grado o valencia de un vértice
Grafos ponderados
Tipos de Grafos

Grafo Regular
Bipartito
Completo
Nulo
Isomorfo
Platónico

Elaboró: Mtra. Rosy

Sánchez

Grado o valencia de un vértice

• Es el número de aristas que inciden sobre un

vértice.

• El grado de un vértice de un grafo no dirigido es

el número de lados que inciden en él.

• La valencia o grado del vértice se denota por

δ(v).

• Llamaremos grado de un vértice al número de

aristas de las que es extremo. Se dice que un
vértice es `par' o `impar' según lo sea su grado.

Elaboró: Mtra. Rosy

Sánchez

Grado o valencia de un vértice

Elaboró: Mtra. Rosy

Sánchez

Ejemplos:

Elaboró: Mtra. Rosy

Sánchez

De forma mas comprensible:
GradoE (Grado de entrada): son las aristas que llegan al
nodo
GradoS (Grado de salida): son las aristas que salen del nodo.

Ejemplos

Elaboró: Mtra. Rosy

Sánchez

Grafos ponderados

Elaboró: Mtra. Rosy

Sánchez

Grafos ponderados

• Costo o peso

▫ Valor que se puede asociar con un arco
▫ Depende de lo que el grafo represente
▫ Si los arcos de un grafo tienen un costo

Elaboró: Mtra. Rosy

Sánchez

Costo o peso

del grafo

Webgrafía

• https://www.wuolah.com/Universidad/Facultad

-de-Matematicas-908/ejercicios-de-Primero-de-
Matematica-Discreta-477/Ejercicios-Resueltos-
de-Grafos-73860

• http://163.10.22.82/OAS/estructuras_de_grafo

s/definicin.html

Elaboró: Mtra. Rosy

Sánchez