Matemáticas Discretas y Lógica 2
Jose Soto
UTEC
Indice
1 Formulación histórica
2 Conceptos básicos de la Teoría de Grafos
3 Subgrafos
4 Complementos
5 Isomorfismo de Grafos
6 Grado de un vértice
Formulación histórica
Puentes de Königsberg
Encontrar un recorrido para cruzar a pie toda la ciudad, pasando
sólo una vez por cada uno de los puentes, y regresando al mismo
punto de inicio.
Figura: Puentes de Königsberg
Formulación histórica
Problema
Construir la figura sin levantar el lápiz y sin repetir ninguno de los
trazos
Formulación histórica
A menudo, cuando se utiliza un mapa de carreteras interesa
observar como ir de un pueblo a otro por las carreteras indicadas en
el mismo.
En consecuencia se tienen dos conjuntos distintos de objetos:
pueblos y carreteras. Como ya se ha visto, estos conjuntos de
objetos se pueden utilizar para definir una relación.
Formulación histórica
Conceptos básicos de la Teoría de Grafos
Ejemplo
Si V denota el conjunto de pueblos y E el conjunto de carreteras,
se puede definir una relación R en V por
aRb si existe una carretera que una a con b
y tal que (a, b) ∈ E si aRb.
Si son carreteras de doble sentido y existe aRb se tiene también
bRa.
Si todas las carreteras consideradas son de doble sentido se tiene
una relación simétrica.
Conceptos básicos de la Teoría de Grafos
Una forma de representar las relaciones es mediante la enumeración
de sus elementos, pero esta forma no es conveniente para
representar las relaciones entre 6 pueblos y las 8 carreteras que los
conectan, por ejemplo.
Conceptos básicos de la Teoría de Grafos
En la siguiente figura se representan las formas de viajar entre 6
pueblos, usando las 8 carreteras que existen entre ellos.
Figura: Representación de caminos entre ciudades
Conceptos básicos de la Teoría de Grafos
Definición.
Sea V un conjunto no vacío y E ⊂ V × V . Entonces el par (V , E )
se denomina grafo dirigido (en V ) o dígrafo (en V ) donde V se
llama conjunto de vértices o nodos y E conjunto de aristas.
Escribimos G = (V , E ).
Conceptos básicos de la Teoría de Grafos
b b d
c
b
b
b
e
b
a
Figura: Representación de un grafo
La dirección de la arista (a, b) se indica colocando una flecha en el
extremo b.
Conceptos básicos de la Teoría de Grafos
b b d
c
b
b
b
e
b
a
Figura: Representación de un grafo
Para cualquier arista, por ejemplo (b, d), se dice que la arista es
incidente con los vértices b, d; b es adyacente a d mientras que c
es adyacente desde a.
Conceptos básicos de la Teoría de Grafos
b b d
c
b
b
b
e
b
a
Figura: Representación de un grafo
Además b se denomina origen o fuente de la arista y d el término
o vértice final.
Conceptos básicos de la Teoría de Grafos
b b d
c
b
b
b
e
b
a
Figura: Representación de un grafo
Una arista (b, b) se denomina lazo. Un vértice que no tiene
ninguna arista incidente se denomina vértice aislado.
Conceptos básicos de la Teoría de Grafos
Cuando no importa la dirección de las aristas el grafo se denomina
no dirigido. En un grafo no dirigido hay aristas no dirigidas.
Se dibuja igual sin poner la flecha en la arista. En vez de denotar la
arista con
(a, b)
utilizamos conjuntos y denotamos la arista con
{a, b}.
Conceptos básicos de la Teoría de Grafos
En general cuando no se especifica si un grafo G es o no dirigido se
supone que es no dirigido. Si no contiene lazos se denomina grafo
sin lazos.
b
b
a b
b c
b
d
Figura: Adyacencias en un grafo
Decimos que b y d son adyacentes si hay arista {b, d}.
Conceptos básicos de la Teoría de Grafos
Definición.
Sea G = (V , E ) un grafo no dirigido.
Para x, y ∈ V se dice que hay un camino en G de x a y si
existe una sucesión no vacía finita de aristas distintas de E
como
{x, x1 }, {x1 , x2 }, ..., {xn−1 , xn }, {xn , y }.
Cuando x = y el camino se denomina ciclo.
El número de aristas de un camino (ciclo) se denomina
longitud del camino (ciclo).
Cuando un camino(ciclos) entre dos vértices solo pasa una vez
por cualquiera de ellos el camino se denomina simple.
Conceptos básicos de la Teoría de Grafos
b
b
c
b
a b
b
d b
e
b
Figura: Caminos y ciclos
Para un grafo dirigido se utilizan los términos caminos dirigidos y
ciclos dirigidos.
Conceptos básicos de la Teoría de Grafos
Definición.
Sea G = (V , E ) un grafo no dirigido. G se denomina conexo
si existe un camino entre cualesquiera dos vértices distintos de
G.
Sea G = (V , E ) un grafo dirigido. Su grafo no dirigido
asociado es el obtenido de G ignorando la dirección de las
aristas. G se considera conexo si lo es el grafo asociado.
Un grafo que no sea conexo se denomina no conexo.
Un grafo no conexo está compuesto de subpartes que son
conexas y que llamamos componentes conexas.
Conceptos básicos de la Teoría de Grafos
Proposición.
Un grafo es conexo si y solo si tiene una única componente conexa.
Conceptos básicos de la Teoría de Grafos
En la figura tenemos un grafo no conexo con dos componentes.
b b
e b
b g
a
b
b
b
c f
Figura: Conexidad
Conceptos básicos de la Teoría de Grafos
Teorema
Si G = (V , E ) es un grafo conexo, entonces existe un camino
simple entre dos vértices cualesquiera de G .
Conceptos básicos de la Teoría de Grafos
Demostración
Como G es conexo, para cualquier a, b ∈ V hay un camino de a a
b. Consideremos un camino: {a, x1 }, {x1 , x2 }, ..., {xn−1 , xn }, {xn , b}.
Si este camino no es simple se tiene el caso:
{a, x1 }, {x1 , x2 }, ..., {xk−1 , xk }, ..., {xm−1 , xm }, ..., {xn , b}
donde xk = xm , pero entonces
{a, x1 }, {x1 , x2 }, ..., {xk−1 , xk }, {xm , xm+1 }, ..., {xn , b}
es un camino más corto que repite un vértice menos, repitiendo
obtenemos un camino simple.
Conceptos básicos de la Teoría de Grafos
Definición.
Un grafo G = (V , E ) se denomina multigrafo si para a, b ∈ V ,
a ̸= b tiene dos o más aristas de la forma (a, b) (para un grafo
dirigido) o {a, b} (para un grafo no dirigido).
Conceptos básicos de la Teoría de Grafos
Definición.
Si hay k aristas de a a b se dice que la arista {a, b} tiene
multiplicidad k.
Para n ∈ Z+ un multigrafo se denomina n-grafo si ninguna
arista del grafo tiene multiplicidad mayor que n.
Conceptos básicos de la Teoría de Grafos
Definición.
Supongamos que G = (V , E ) es un grafo. La matriz de
adyacencias A del grafo G , se representa por aij donde
1 si (ai , aj ) ∈ E
aij =
0 otro caso
Conceptos básicos de la Teoría de Grafos
Definición.
Supongamos que G = (V , E ) es un grafo, v1 , · · · , vn representa los
vértices y e1 , · · · , em representan las aristas. La matriz de
incidencia M del grafo G , se representa por
1 si ej es incidente en vi
mij =
0 otro caso
Subgrafos
Definición.
Si G = (V ; E ) es un grafo (dirigido o no dirigido), G1 = (V1 , E1 ) se
denomina subgrafo de G si V1 ̸= ∅, V1 ⊂ V y E1 ⊂ E donde cada
arista de E1 es incidente con vértices de V1
Subgrafos
La figura 10 presenta un ejemplo de grafo formado por dos
subgrafos.
b
b e f
b b
a b
b b
c g
b
d
Figura: Grafo formado por dos subgrafos
Subgrafos
La idea de subgrafo ofrece una manera de desarrollar el
complemento de un grafo no dirigido. Antes de hacerlo, se define un
tipo de grafo de tamaño maximal para un número dado de vértices.
Subgrafos
Definición.
Sea V un conjunto de n vértices. El grafo completo en V
denotado por Kn es un grafo no dirigido, sin lazos, en el que para
cualquier a, b ∈ V , a ̸= b hay una arista {a, b}.
La figura 11 representa los grafos completos para n = 2, 3, 4, 5
Figura: Grafos completos K2 , K3 , K4 y K5
Complementos
Definición.
Sea G un grafo no dirigido sin lazos de n-vértices. El
complemento de G , denotado por G es el subgrafo de Kn
formado por los n vértices de G y las aristas que no están en G . (Si
G = Kn , G es un grafo formado por n vértices y sin aristas. Este
se denomina grafo nulo)
Complementos
a b a
b
b b
b b
b b b c
d
b
c d
Figura: Grafo y complemento
En la figura se muestra un grafo no dirigido de 4 vértices y su
complemento.
Isomorfismo de Grafos
Definición.
Sea G1 = (V1 , A1 ) y G2 = (V2 , A2 ) dos grafos no dirigidos.
Una función f : v1 → v2 se denomina isomorfismo de grafos si:
f es uno-a-uno y sobreyectiva, y
para todo a, b ∈ V1 , {a, b} ∈ A1 si y solo si {f (a), f (b)} ∈ A2
Cuando existe dicha función, G1 y G2 se denominan grafos
isomorfos.
La correspondencia de vértices de un isomorfismo de grafos
mantiene las adyacencias, de esta manera se mantiene la estructura
de los grafos.
Grado de un vértice
Definición.
Sea G un grafo o multigrafo no dirigido. Para cualquier vértice v de
G , el grado de v , escrito grad(v ) es el número de aristas de G
incidentes con v .
Grado de un vértice
Teorema.
Si G = (V , E ) es un grafo o multigrafo no dirigido, entonces
X
grad(v ) = 2|A|
v ∈V
Grado de un vértice
Demostración
Considerando una arista {a, b} del grafo G , se tiene que la arista
suma 1 a grad(a)
X y 1 a grad(b) y por lo tanto agrega
X 2 al
considerar grad(v ). Así, 2|A| es el total de grad(v ).
v ∈V v ∈V
Grado de un vértice
Proposición.
Para cualquier grafo o multigrafo no dirigido, el número de vértices
de grado impar debe ser par.
Grado de un vértice
Demostración
Supongo el número de vértices de grado impar es impar y
dividamos a V en dos conjuntos Vp y Vi , los vértices de grado par
e impar respectivamente.
X X X
grad(v ) = grad(v ) + grad(v )
v ∈V v ∈Vp v ∈Vi
X
El primer término grad(v ) tiene como resultado un número
v ∈Vp
par (la suma de dos pares es par).
Grado de un vértice
Demostración
X
El segundo término grad(v ), es una suma de números impares,
v ∈Vi
recordando que la suma de dos impares es par, pero por hipótesis
estamos suponiendo que hay un numero impar de vértices en Vi , la
suma resultante es un numero impar.
Luego se tiene que X
grad(v )
v ∈V
es un numero impar, lo cual es una contradicción, ya que este es
igual a 2|A|, que siempre es un numero par.
Grado de un vértice
Definición.
Un grafo o multigrafo no dirigido donde todos los vértices tienen el
mismo grado se denomina grafo regular.
