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
Grado de un nodo
Sea G = (V, E.ϕ) un grafo no dirigido. Sea v ∈ V , se de ne el grado de v ,
grad(v), como el número de aristas incidentes con v .
Un lazo incidente en un nodo v se considera como dos aristas incidentes con v .
M. en C. Perla Rebeca Sánchez Vargas Matemáticas discretas
Estructuras Discretas
Grafo Regular
Se dice que G = (V, E, ϕ) es un grafo regular si todos los nodos de G tienen el
mismo grado.
Si grad(v) = k, entonces a G se le llama k− regular.
M. en C. Perla Rebeca Sánchez Vargas Matemáticas discretas
Estructuras Discretas
Grafo Euleriano
Sea G = (V, E.ϕ) un grafo no dirigido sin nodos aislados.
Se dice que G tiene un circuito euleriano si existe un circuito en G que recorre
cada arista de G exactamente una vez.
Si existe un recorrido abierto de a a b en G que recorre cada arista de G
exactamente una vez, entonces se le llama recorrido euleriano.
Si G tiene un circuito euleriano, entonces se le llama grafo euleriano.
Teorema
Sea G = (V, E.ϕ) un grafo no dirigido sin nodos aislados. G tiene un circuito
euleriano si y sólo si G es conexo y todo nodo de G tiene grado par.
Corolario
Sea G = (V, E.ϕ) un grafo no dirigido sin nodos aislados. G tiene un recorrido
euleriano si y sólo si G es conexo y tiene exactamente 2 nodos de grado impar.
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
De nición
Sea G = (V, E.ϕ) un grafo dirigido. Para cualquier v ∈ V
a. El grado de entrada de v ge (v), es el número de aristas que llegan a v .
b. El grado de salida de v gs (v), es el número de aristas que parten a v .
Si se tiene un lazo incidente a un nodo v , entonces se contribuye con una
unidad a ge (v) y una unidad a gs (v).
Teorema
Sea G = (V, E.ϕ) un grafo dirigido sin nodos aislados. G tiene un circuito
euleriano si y sólo si G es conexo y para cada v ∈ V se tiene que ge (v) = gs (v).
M. en C. Perla Rebeca Sánchez Vargas Matemáticas discretas
Estructuras Discretas
M. en C. Perla Rebeca Sánchez Vargas Matemáticas discretas