Estructuras Discretas
Curso de Matemáticas Discretas
Unidad IV: ESTRUCTURAS DISCRETAS
M. en C. Perla Rebeca Sánchez Vargas
IPN-ESCOM
Semestre 2021-2
M. en C. Perla Rebeca Sánchez Vargas Matemáticas discretas
Estructuras Discretas
De nición de un Grafo
Un grafo G consiste de un conjunto V 6= ∅ nito de nodos o vértices, un
conjunto E ⊆ V × V de aristas y una función ϕ que relaciona cada arista con
un par de nodos. Una grá ca se denota como G = (V, E, ϕ).
Observaciones
Para denotar a los nodos se ocupan las letras del alfabeto.
Un grafo se dice dirigido si las aristas tienen una echa indicando
dirección, de lo contrario es un grafo no dirigido.
Para denotar a las aristas se tienen varias formas: (a, b) cuando la grá ca
es dirigida, {a, b}, cuando la grá ca es no dirigida, y también es posible
ocupar la notación ab en ambos casos.
Para cada arista (a, b) o {a, b}, se dice que la arista es incidente con los
nodos a y b, mientras que los nodos a y b son adyacentes.
M. en C. Perla Rebeca Sánchez Vargas Matemáticas discretas
Estructuras Discretas
M. en C. Perla Rebeca Sánchez Vargas Matemáticas discretas
Estructuras Discretas
A la arista que une un nodo a consigo mismo (a, a) o {a, a} se le llama lazo.
Al nodo a que no es adyacente a ningún otro nodo se le llama nodo aislado.
A un grafo G = (V, E, ϕ) se le llama multigrafo si existen a, b nodos de G con
dos o más aristas incidentes con ellos.
M. en C. Perla Rebeca Sánchez Vargas Matemáticas discretas
Estructuras Discretas
Se dice que una grá ca G = (V, E, ϕ) se dice simple si no tiene lazos y no hay
mas de una arista incidente por cada par de nodos.
Sea V un conjunto de n nodos, el grafo completo sobre V , que se denota por
Kn , es un grafo no dirigido sin lazos, tal que para todos a, b ∈ V , con a 6= b,
existe una arista {a, b}.
M. en C. Perla Rebeca Sánchez Vargas Matemáticas discretas
Estructuras Discretas
De nición de camino para un grafo G
Sean x y y nodos de un grafo G = (V, E, ϕ).
Un camino x − y en G es una sucesión alternada nita (sin lazos) de nodos y
aristas de G
x = x0 , {x0 , x1 }, x1 , {x1 , x2 }, x2 , . . . , {xk−1 , xk }, xk = y
que comienza en el nodo x y termina en el nodo y .
La longitud de un camino x − y está dada por la cantidad de aristas que
hay en el camino.
Si la longitud de un camino x − y es n < 1 y x = y , se dice que el
camino x − y es cerrado, de lo contarrio el camino es abierto.
M. en C. Perla Rebeca Sánchez Vargas Matemáticas discretas
Estructuras Discretas
Recorrido, circuito, camino simple y ciclo
Sea un camino x − y en un grafo G = (V, E, ϕ).
Si no se repite ningún arista en el camino x − y , entonces el camino es un
recorido x − y .
Un recorrido cerrado x − x es un circuito.
Cuando ningún nodo se repite mas de una vez en el camino x − y ,
entonces se tiene un camino simple x − y , y si además x = y entonces se
le llama ciclo. ( Por convención, para tener un ciclo se requieren al menos
tres aristas distintas).
M. en C. Perla Rebeca Sánchez Vargas Matemáticas discretas
Estructuras Discretas
Dado el grafo de esta página, determine lo siguiente.
Un camino que no sea recorrido de b a d.
Un recorrido que no sea un camino simple de b a d.
Un camino simple de b a d.
Un camino cerrado que no sea un circuito b a b.
Un circuito que no sea un ciclo de b a b.
Un ciclo de b a b.
M. en C. Perla Rebeca Sánchez Vargas Matemáticas discretas
Estructuras Discretas
Grafo Conexo
Se dice que un grafo G = (V, E, ϕ) es conexo, si para cada par de nodos x, y de G,
existe un camino simple x − y , de lo contrario se dice que G = (V, E, ϕ) es disconexo.
M. en C. Perla Rebeca Sánchez Vargas Matemáticas discretas
