Facultad de Ingeniería

Matemática Discreta

Licenciatura en Sistemas
Ingeniería Informática

GRAFOS

Abril 2023

Ing. A. García
 MATEMATICA DISCRETA.2023
GRAFOS

Un grafo es un Sistema Matemático Abstracto, creado por Leonard Euler en el siglo XVIII
Los grafos son modelos matemáticos de numerosas situaciones reales, como ser: un mapa de carreteras, un
plano de la red de metro de una ciudad, un plano de un circuito eléctrico, un plano de la red telefónica de una
compañía, etc., son grafos que representan esquemáticamente situaciones reales.
Las aplicaciones de grafos son múltiples como ser:
a) La síntesis de circuitos secuenciales, contadores o sistemas de apertura. Se utiliza para diferentes áreas
por ejemplo, Dibujo computacional, en todas las áreas de Ingeniería.

b) Modelar trayectos como el de una línea de autobús a través de las calles de una ciudad, en el que
podemos obtener caminos óptimos para el trayecto.

c) Para la administración de proyectos, utilizamos técnicas como técnica de revisión y evaluación de

programas (PERT) en las que se modelan los mismos utilizando grafos y optimizando los tiempos para
concretar los mismos.

d) Desarrollar un concepto no metafórico de red social que sustituye los nodos por los actores sociales y
verifica la posición, centralidad e importancia de cada actor dentro de la red.

e) Se emplea en problemas de control de producción, para proyectar redes de ordenadores, para diseñar
módulos electrónicos modernos y proyectar sistemas físicos con parámetros localizados (mecánicos,
acústicos y eléctricos).

f) Se usa para la solución de problemas de genética y problemas de automatización de la proyección

(SAPR). Apoyo matemático de los sistemas modernos para el procesamiento de la información.

Circuito eléctrico Sociograma de una red social

Topología de red de computadoras organigrama

Asimismo, un algoritmo puede representarse mediante un grafo al que se le llama diagrama de flujo del algo-
ritmo.

2
 MATEMATICA DISCRETA.2023
Sea V un conjunto de vértices y A un conjunto de aristas (líneas entre dos vértices)
En el dibujo:

V = {v1, v2, v3, v4, v5}

A = {a, b, c, d, e, f, g}
*

Grafo 1
Definición:
Se llama Grafo a la terna G = (V, A,  ), dónde V es un conjunto finito no vacío de vértices(o nodos), A
es un conjunto finito de aristas, dónde cada arista está asociada a un conjunto compuesto por dos vértices
extremos. La función de incidencia  le hace corresponder a cada arista sus vértices extremos de V.
 x  A :  ( x ) = { vi , vj }

De acuerdo a nuestro ejemplo, podemos construir una tabla para 

x a b c d e f g
 ( x ) { v2 , v3 } { v1 , v3 } { v4 , v1} { v4 , v3 } { v1 , v5 } { v1 , v2 } { v4 , v4 }

Definiciones

Sea G = (V, A,  ) un grafo.

Definición 1: Un vértice y una arista son incidentes si y sólo si el vértice es extremo de la arista.

En nuestro ejemplo c y v4 son incidentes.

También podemos decir que c incide en v4.

Definición 2: Dos aristas son paralelas (o múltiples) si y solamente si los vértices asociados a cada una de
ellas coinciden.
En grafo 1, no hay aristas paralelas.
En el grafo 2 b y c son aristas paralelas.
 (b)   v 2 , v3  y  (c)   v 2 , v3    (b)   (c)

También podemos decir que dado un grafo ( V , A ,  )

 x1  A   x 2  A , x1 y x 2 son aristas paralelas   (x1 )   (x 2 ) Grafo 2

Definición 3:
Una arista es un lazo (o bucle) si y solamente si, sus extremos coinciden.
En el grafo 1 g es un lazo.  (g)   v 4 , v4 

 x  A : x es un lazo   ( x ) = { vi , vi } vi  V

Definición 4:
3
 MATEMATICA DISCRETA.2023
El grado o valencia de un vértice es el número de aristas que inciden en él.
En este grafo:
g ( v1 ) = 4 . En v1 inciden e, c, b, f
g ( v2 ) = 2 g ( v4 ) = 4
g ( v3 ) = 3 g ( v5 ) = 1

Nota: en v4 inciden las aristas c, d y g . Pero esta es un lazo, por

lo tanto incide dos veces en v4, por eso se cuenta doble.

Pendiente
Definición 5:
Un vértice v se dice aislado si g (v) = 0 .
Es decir no incide ninguna arista en él. Aislado

En este grafo 3, v1 y v4 son vértices aislados. Aislado Lazo

Grafo 3
Definición 6:
Un vértice v es un vértice pendiente si g ( v ) = 1 .
En el grafo 1 v5 es un vértice pendiente, ya que g(v5) =1
En el grafo 3 v3 es un vértice pendiente

Definición 7:
Dos vértices son adyacentes si son extremos de una misma arista.
En nuestro ejemplo v1 es adyacente a v2, v3, v4 y v5.
v2 es adyacente a v1 y v3.
v3 es adyacente a v1, v4 y v2.
v4 es adyacente a v1, v3 y v4. Vertices adyacentes
v5 es adyacente a v1

Definición 8:
Aristas
Dos aristas son adyacentes si tienen un vértice en común. Adyacentes
En nuestro ejemplo a es adyacente a b, f , d.
b es adyacente a a , c, e , f , d.
c es adyacente a b, d, e, f, g .
d es adyacente a a , b, c , g.
e es adyacente a b, c , f.
g es adyacente a c, d, g. 3-Regular

Definición 9:
Si todos los vértices de un grafo tienen el mismo grado, el grafo se dice
regular.
Si todos los vértices tienen grado k el grafo es k-regular.
El grafo 4 es 3-regular.

Grafo 4 Simple

Definición 10:
Un grafo se llama simple (o sencillo) si no tiene lazos ni aristas paralelas.
El grafo 1 no es simple porque tiene un lazo.
El grafo 2 no es simple porque tiene una arista paralela.

4
 MATEMATICA DISCRETA.2023
El grafo 3 no es simple tiene un lazo
El grafo 4 es un grafo simple.

Definición 11:
Matriz de incidencia de grafos
Sea (V, A,  ) un grafo de n vértices y k aristas.

Entonces | V | = n el número de elementos de V es n

y |A|=k el número de elementos de A es k.

Se llama matriz de incidencia de un grafo (V, A,  ) (que no tenga lazos) a una matriz
MI = || mij || de n filas y k columnas, tal que.

1 𝑠𝑖𝑖 𝑣𝑖 𝑦 𝑎𝑗 𝑠𝑜𝑛 𝑖𝑛𝑐𝑖𝑑𝑒𝑛𝑡𝑒𝑠

mij = {
0 𝑠𝑖𝑛𝑜 𝑙𝑜 𝑠𝑜𝑛

Ejemplo
La matriz de incidencia obtenida del grafo dado, se la construye colo-
cando en las filas de la matriz los vértices del grafo que están numera-
dos de v1,v2,v3,v4, y en las columnas de la matriz se colocan las aris-
tas a, b,c,d, del grafo.
Nos colocamos en el vértice v1 y observamos que aristas inciden en él ,
en nuestro caso inciden las aristas a, b y c por lo cual colocamos un 1 en
sus casilleros, como la arista d no incide le corresponde un 0, de esta
manera se construye la matriz de incidencia del grafo.
También se obtiene la matriz de incidencia, analizando cada arista entre
que vértices se encuentra. Por ejemplo la arista a esta definida por los
vértices v1 y v2. El resultado final será el mismo
a b c d
Con la función de incidencia se puede armar la matriz de incidencia
v1  1 1 1 0  g(v1 )  3
  Para cada arista se coloca los vértices en los que incide, colocandolos
v2  1 1 0 1  g(v 2 )  3 de manera vertical para cada arista
M=  
v3 0 0 1 1 g(v 3 )  2 También se puede completar en horizontal, colocando las aristas que
 
v4  0 0 0 0  g(v 4 )  0
inciden en cada vertice

Nota:
Cada columna de una matriz de incidencia tiene dos unos. La suma de los elementos de cada fila da el grado
del vértice correspondiente.
De igual manera observamos que en las columnas hay dos unos, la arista sale de un vértice y llega a otro vér-
tice, cuando estamos en presencia de lazos en las columnas tendríamos un solo uno. Algunos autores hacen
uso de esta matriz aun en presencia de lazos, teniendo esta salvedad.

Ejemplo 2.
Dado el siguiente grafo, que contiene un lazo, la matriz de incidencia nos quedaría de la siguiente manera

a b c d e f g
V1 0 1 1 0 1 1 0
V2 1 0 0 0 0 1 0
M= V3 1 1 0 1 0 0 0
V4 0 0 1 1 0 0 1
V5 0 0 0 0 1 0 0
Tiene un único 1 en su
5 columna, es un lazo
 MATEMATICA DISCRETA.2023
Observamos que en la columna de la arista g sólo hay un 1, esto se debe a la presencia de un lazo sobre el
vértice v4 . En esta situación también podemos emplear la matriz de incidencia. Teniendo en cuenta al
computar el grado del vértice 4 , ya que la arista g incide doblemente sobre el vértice 4, su grado seria 4.
incide doble por ser lazo
Definición 12:
Matriz de adyacencia de vértices de un grafo
Es una buena representación para grafos sin aristas paralelas.
Sea G = (V, A, ) un grafo de n vértices.
Se llama matriz de adyacencia de vértices de un grafo a una matriz
1 si vi y v j son adyacentes
 Comparten la misma arista
Mv = mij de orden n x n tal que mij = 

0 en todo otro caso

En el caso de los grafos la matriz es simétrica, no importa si lo

completamos en horizontal o vertical
Ejemplo:
v1 v2 v3 v4
v1  1 1 1 0
 
v2  1 0 1 0
Mv = 
v3 1 1 0 1
 
v4  0 0 1 0 
En la diagonal principal, los 1, revelan los lazos existentes

Observamos que nos da una matriz simétrica suele suceder que dada una matriz de adyacencia de vértices se
pida el grafo correspondiente, para realizar el grafo se debe utilizar la matriz diagonal superior o inferior
para su representación si se usa toda la matriz obtendrán grafos con aristas paralelas caso que excluye la
definición.
Esta matriz también se puede utilizar aún en presencia de aristas paralelas o múltiples haciendo la siguiente
salvedad. Se coloca el número de aristas paralelas entre los vértices involucrados. Solo que la matriz ya no
sería booleana.
En el ejemplo dado anteriormente si se le agrega una arista paralela tendremos:

v1 v2 v3 v4
v1  1 1 1 0 El vértice v2 comparte 2 aristas con el vértice v3
 
v2  1 0 2 0
Mv = 
v3 1 2 0 1
 
v 4  0 0 1 0 

Teorema del saludo de manos (o de los apretones de mano)

Sea G = (V, A,  ) un grafo , la suma de los grados de todos los vértices del grafo es igual al doble del nú-
mero de aristas.
V = {vi } |V| =n |A|=k

n
 g( v i )  2 A Es decir el grado total de G es igual al duplo del número de aristas de G
i 1

Demostración

6
 MATEMATICA DISCRETA.2023
Sea G un grafo que se elige arbitrariamente y supongamos que G tiene n vértices v1,v2,v3,…,vn y m aristas,
donde n es un entero positivo y m es un entero no negativo. Cada arista de G contribuye en 2 al grado total
de G. Se supone que e es una arista arbitrariamente elegida con vértices extremos vi y vj. Esta arista contri-
buye con 1 al grado de vi y con 1 al grado vj. Esto es verdadero aún si vi = vj, ya que se cuenta dos veces,
una arista que es un lazo en el cálculo del grado del vértice en el que incide.

Por tanto e contribuye con 2 al grado total de G. Ya que e se escoge arbitrariamente, está demostrado que
cada arista de G contribuye con 2 al grado total de G. Por tanto el grado total de G es igual a 2 por el número
de aristas de G.

En el grafo 1 sería

V = { v1 , v2 , v3 , v4 , v5 } |A|=7  2 | A | = 14
5
 g( v i )  g ( v1 ) + g ( v2 ) + g ( v3 ) + g ( v4 ) + g ( v5 ) =
i 1
4 + 2 + 3 + 4 + 1 = 14

Corolario: El grado total de un grafo es par.

Teorema:
En todo grafo hay un número par de vértice de grado impar.
Sea V el conjunto de vértices de un grafo.
Demostración:
Sea Vp el conjunto de los vértices de grado par. V p = { vp }
Sea Vi el conjunto de los vértices de grado impar V i = { vi }  V = Vp  Vi
n
 g(vj )2 A
j1
La suma de los grados de todos los vértices es igual a la suma de los grados de los vértices de grado par más
la suma de los grados de los vértices de grado impar.
 g(v p )   g(v i )  2 A

 g(v p ) es un número par porque es la suma de números pares

2 | A | es un número par porque es múltiplo de dos.
En consecuencia  g( v i ) debe ser par.
Pero  g( v i ) es una suma cuyos términos son todos impares. Si el resultado de esta suma es par, entonces
el número de términos de esa sumatoria debe ser par.
Por lo tanto, el número de vértices de grado impar es par, que es lo que queríamos demostrar.

Verificamos para el ejemplo dado

g ( v1 ) = 4 g ( v4 ) = 4
g ( v2 ) = 2 g ( v5 ) = 1
7
 MATEMATICA DISCRETA.2023
g ( v3 ) = 3
Observamos que tenemos dos vértices de grado impar

SUBGRAFOS
Definición:
Una terna S = ( V´, A´, ´ ) es un subgrafo del grafo G = ( V, A,  ) si se cumple:
I ) V´ V
II) A´ A
III ) ´ es una restricción de  en A´
Por ejemplo si G = ( V, A,  ) es Un subgrafo será por ejemplo

Subgrafo restante respecto de un vértice.

Definición:
Se llama subgrafo restante respecto del vértice vi al grafo obtenido a partir del grafo original omitiendo el
vértice vi y todas la aristas que inciden en él.
~
Se simboliza Gv
i
Si tomamos el grafo del ejemplo anterior podemos representar el diagrama del subgrafo restante respecto de
cada uno de sus vértices.

Subgrafo restante respecto de una arista

Definición:
Se llama subgrafo restante respecto de una arista ai al grafo que se obtiene suprimiendo la arista a del
~
grafo original y que se simboliza: G
a
Para nuestro ejemplo, obtendremos los siguientes subgrafos restantes respecto de cada arista.

8
 MATEMATICA DISCRETA.2023

Subgrafo generado por un subconjunto de vértices W

Definición:
Sea W un subconjunto de vértices de V.
Se llama subgrafo generado por un subconjunto de vértices W al grafo que tiene a W como subconjunto
de vértices y cuyo conjunto de aristas está formado por todas las aristas del grafos original que tienen ambos
extremos en W.
En nuestro ejemplo
Si W = { v1 , v3 } el subgrafo generado por W es

Conexión de Grafos

Camino
Definición:
Sea G un grafo G = ( V , A ,  ) y sean vi y vj dos vértices de G.
Un camino de vi a vj es una sucesión finita alternada de vértices adyacentes y aristas de G. Por tanto un ca-
mino tiene la forma de v1e1 v 2 e 2 v 3 e 3 ...e n -1 v n -1e n v n
Un camino trivial de v1 a v1 consiste del único vértice v1
Un camino puede iniciar y terminar en el mismo vértice, puede repetir aristas y vértices.

Ejemplo:
{v6 g v1 a v2 b v4 h v1 g v6 f v5 }

Cadena (sendero o recorrido)

Definición:
Dado un grafo G = ( V , A ,  ) se llama cadena(sendero o recorrido) a
una sucesión alternada de vértices adyacentes y aristas de la forma v1
a1 v2 a2 v3 a3 ... a n v n que comienza y termina en vértices y que
cumple las siguientes condiciones:
i) Las aristas son todas distintas. Los vértices se pueden repetir
ii) Cada arista incide en el vértice precedente y en el siguiente.

En el grafo un ejemplo sería

{ v1 g v6 d v4 e v5 f v6 } es una cadena de v1 a v6.

Cadena simple
Definición:
Una cadena simple(o trayectoria) es una cadena en la cual todos los vértices son distintos.
Las aristas pueden repetirse
Ejemplo:
{v1 a v2 b v4 } es una cadena de v1 a v4.

9
 MATEMATICA DISCRETA.2023
Ciclo
Definición:
Un ciclo es una cadena cuyo vértice inicial coincide con el final.
Los vértices se pueden repetir
Ejemplo:
{v1 h v4 e v5 f v6 d v4 bv2 a v1 } ciclo

Ciclo simple
Definición:
Un ciclo simple es un ciclo en el que no se repite ningún vértice, salvo el primero (y el último)
Aristas distintas
Ejemplo:
{v1 g v6 d v4 b v2 a v1} es un ciclo simple.

Longitud de un camino
Definición:
Se llama longitud de un camino ( o cadena o ciclo) al número de aristas que la componen.
En nuestros ejemplos anteriores las longitudes de las cadenas son 2 y 4 respectivamente.
Las longitudes de los ciclos son 4 y 6 respectivamente.
Un par de aristas paralelas constituyen un ciclo de longitud 2.
Un lazo es un ciclo de longitud 1.

Ejemplo:
a) v1e1v2e3v3e4v3e5v4 cadena
b) v1e1 v2 e3 v3e5 v4e5 v3e6v5 camino
c) v2e3v3e5v4e10v5e6v3e7v6e8v2 ciclo
d) v2 e3v3 e5v4 e10v5 e9v6 e8v2 ciclo simple
e) v1e1v2e1v1 camino cerrado
f) v1 camino cerrado

Número de caminos entre dos vértices

El número de caminos que hay entre dos vértices de un grafo se puede determinar usando su matriz de adya-
cencia de vértices.
Teorema: Sea G un grafo y sea MG su matriz de adyacencia con respecto a la ordenación v1,v2,v3,…,vn (se
admiten aristas múltiples o lazos). El número de caminos distintos de longitud r de vi a vj, siendo r un entero
positivo, es igual al elemento en la posición (i,j) de la matriz MGR.

Ejemplo: Dado el grafo G cuántos caminos de longitud 4 hay entre el vértice a y d?

a  0 1 1 0 a 8 0 0 8
   
b 1 0 0 1 b  0 8 8 0
MG   MG  
4

c 1 0 0 1 c 0 8 8 0
   
d  0 1 1 0  d  8 0 0 8 
Multiplicar por sí misma la matriz, tantas veces como la longitud
que queremos encontrar
Si analizamos la posición 14 que corresponde a los caminos que comienzan en a y terminan en d , el número
que aparece es el 8 , es decir hay 8 caminos de longitud 4 de a a d.

10
 MATEMATICA DISCRETA.2023
Ejemplo:
ababd abacd abdbd abdcd acabd acacd acdbd acdcd

Conectividad
Un grafo está conectado si es posible viajar desde cualquier vértice a cualquier otro vértice a lo largo de una
sucesión de aristas adyacentes del grafo.

Grafo Conexo
Definición: Sea G un grafo.
El grafo G es conexo si y solo si, dados dos vértices cualesquiera vi y vj de G hay una cadena simple de vi a
vj.
𝐺 𝑒𝑠 𝑐𝑜𝑛𝑒𝑥𝑜 ⟺ ∀ 𝑣é𝑟𝑡𝑖𝑐𝑒 𝑣𝑖 , 𝑣𝑗 𝜖 𝑉(𝐺) ∃ 𝑢𝑛𝑎 𝑐𝑎𝑑𝑒𝑛𝑎 𝑠𝑖𝑚𝑝𝑙𝑒 𝑑𝑒 𝑣𝑖 𝑎 𝑣𝑗
Un grafo es conexo si tiene una única componente conexa.

Lema: Sea G un grafo

a) Si G es conexo, entonces dos vértices distintos cualesquiera de G pueden conectarse con una cadena
simple.
b) Si los vértices v y w forman parte de un ciclo en G y se quita una arista del ciclo, entonces aún existe
una cadena de v a w en G.
c) Si G es conexo y contiene un ciclo, entonces se puede eliminar una arista del ciclo sin desconectar a
G.

Grafo no conexo
Teorema: Un grafo G = ( V, A ,  ) que no es conexo , es la unión de dos o más subgrafos conexos que dos
a dos, no tienen ningún vértice en común. A estos subgrafos conexos disjuntos se les llama componentes co-
nexas del grafo.
Ejemplos

En el grafo adjunto, el vértice v2 no es alcanzable desde v5 porque no hay una cadena que los une, por lo
tanto es un grafo no conexo

I
II

Grafo conexo Grafo no conexo

Las componentes conexas del grafo no conexo son { v1 , v2 , v3 , v4 } ; { v5 , v6 , v7 , v8 } ; { v9 , v10 , v11
En el ejemplo I hay una sola clase de equivalencia formada por todos los vértices de V.
11
 MATEMATICA DISCRETA.2023

Desconexión de Grafos
Punto de corte
Definición:
Un vértice v de un grafo conexo G es un istmo o punto de corte si y solamente si el subgrafo restante res-
pecto de v es no conexo.
v es punto de corte  G~ es no conexo
v
~
En el siguiente ejemplo observamos en v4 es un punto de corte porque Gv es no conexa
4

También son puntos de corte v2, v5, v6.

Puente
Definición:
Una arista a de un grafo conexo G es un puente si el subgrafo restante respecto de esa arista es no co-
nexo.
a es puente  G ~ es no conexo
a
~
En el ejemplo anterior e es un puente porque G es no conexo.
e

También son puentes a, f, g

Ciclo de Euler
Definición:
Un ciclo en un grafo G = ( V , A ,  ) es un ciclo de Euler si recorre todas las aristas del grafo en estudio.

En el ejemplo siguiente tenemos un grafo donde todos sus vértices tienen grado par por lo tanto hay ciclo de
Euler una de los tantos ciclos que se puede armar seria
{ 5 , a1 , 4 , a2 , 6 , a3 , 3 , a4 , 2 , a5 , 1 , a6 , 3 , a7 , 5 , a8 , 6 , a9 , 2 , a10 , 4 ,a11,5}

12
 MATEMATICA DISCRETA.2023

Teorema:
Un grafo conexo G admite un ciclo de Euler si y solamente si todos sus vértices tienen grado par.
Hipótesis : G es conexo y admite un ciclo euleriano.
Tesis:  v  V : g ( v ) es par.

D) Si v es un vértice distinto del vértice inicial, cada vez que se llega a él también se debe salir de él por un
arista diferente, por lo tanto el número de aristas que inciden en él debe ser par, entonces: G ( v ) es par.
Lo mismo sucede con el vértice inicial, porque como es un ciclo se debe llegar también a él por una arista
diferente, entonces su grado debe ser par.
Sólo 2 Impar y el resto Par
Teorema
Un grafo conexo G contiene una cadena de Euler si y sólo si tiene exactamente dos vértices de grado im-
par, siendo todos los demás vértices de grado par. Empieza y termina en los vértices impares

Ejemplo:
En el grafo dado solo se puede encontrar una cadena de Euler que se inicia en el vértice 5 y termina en el
vértice 4 ambos tienen grado impar.
{ 5 , a1 , 4 , a2 , 6 , a3 , 3 , a4 , 2 , a5 , 1 , a6 , 3 , a7 , 5 , a8 , 6 , a9 , 2 , a10 , 4 }

Claramente se ve que no hay un ciclo euleriano porque los vértices 4 y 5 tienen grado impar.

Ciclo de Hamilton Ciclo o Cadena Simple que contenga a todos los vértices del grafo
Definición:
Sea un grafo conexo G = (V, A, ) tiene un ciclo de Hamilton si existe un ciclo simple de G que contenga
todos los vértices de V.
Una “cadena de Hamilton” es una cadena simple de G que contiene todos los vértices.
Ejemplo:

{ v2 , b , v3 , f , v5 , g , v4 , d , v1 , a , v2 }
Es un ciclo hamiltoniano.

13
 MATEMATICA DISCRETA.2023
Los ciclos de Hamilton son llamados así en honor de Sir William Hamilton quien patentó un juego con la
forma de un dodecaedro a mediados del siglo XIX.
Cada esquina del dodecaedro tenía el nombre de una ciudad y el problema era comenzar en cualquier ciudad,
viajar a lo largo de las aristas, visitar cada población exactamente una vez y volver al punto de partida.
La condición necesaria y suficiente para la existencia de un ciclo hamiltoniano en un grafo no se conoce aún.
Sugerencias para intentar hallar un ciclo de Hamilton según Grimaldi.
En un grafo G = (V, A,  ) :
1) Si G tiene un ciclo de Hamilton, entonces para v  V, grad (v)  2.
2) Si v  V y grad (v) = 2, entonces las dos aristas incidentes en el vértice v deben aparecer en cualquier
ciclo de Hamilton de G.
3) Si v  V y grad (v) > 2, entonces cuando se intenta construir un ciclo de Hamilton, una vez que se
pase por v, las aristas no utilizadas incidentes en v se dejan de tener en cuenta.

Las condiciones suficientes más importantes son

Teorema de Dirac
Sea G un grafo simple con n vértices para n ≥ 3 tal que todos los vértices de G tienen grado mayor o igual a
n/2. Entonces, G contiene un ciclo hamiltoniano.

Teorema de Ore
Sea G un grafo simple con n vértices para n ≥ 3 tal que  (u )   (v)  n para cada par de vértices no adya-
centes u y v de G. Entonces, G contiene un ciclo hamiltoniano.
Estos teoremas no dan condiciones necesarias para la existencia de un ciclo hamiltoniano.

GRAFOS ISOMORFOS

La definición de Grafo no hace referencia ni al largo ni a la forma de las aristas que unen cada par de vérti-
ces o nodos. Tampoco prescribe algún tipo de orden para los vértices. Por lo tanto, para un mismo grafo
puede haber más de un diagrama que lo represente.

Por ejemplo:

Los dos diagramas precedentes representan el mismo grafo. Son grafos isomorfos.

Definición
Dados dos grafos G = (V, A, ) y G  (V, A, ) se dice que G y G son isomorfos si existe una función bi-
yectiva f : V  V y una función biyectiva g : A  A que conserven las relaciones de incidencia y adya-
cencia.
Sean los grafos: G G

14
 MATEMATICA DISCRETA.2023

Son G y G isomorfos?
V = {v1, v2, v3, v4, v5} │V│=5 V = {w1, w2, w3, w4, w5} │ V │=5

A = { a ,b , c , d , e } │A│=5 A={ f , g, h , i , j } │ A │=5

f: V  V g:A A

Los grados de los vértices de G y G

Para G g(v1)=2 g(v2)=2 g(v3)=2 g(v4)=2 g(v5)=2

Para G g(w1)=2 g(w2)=2 g(w3)=2 g(w4)=2 g(w5)=2

para que sean isomorfos las biyecciones f y g deben ser tales que si una arista de A incide en los vértices vi y
vj de V , entonces la imagen de x , g ( x ) debe incidir en las imágenes de vi y vj o sea f (vi ) y f (vj ).
Construyamos las matrices de incidencia de G y G .

a b c d e f g h i j
v1  1 0 0 0 1 w1  0 0 0 1 1
   
v2  1 1 0 0 0 w2  1 0 0 0 1
M G  v3  0 1 1 0 0 M  w3  1 1 0 0 0
  G  
v4  0 0 1 1 0 w4  0 1 1 0 0
v5  0 0 0 1 1  w5  0 0 1 1 0 

Si en la matriz de G hacemos cambios en las filas de la matriz de manera tal que la 2da fila pasa a 1er fila y
la 3er fila pasa a 2da fila y la 1er fila pasa a 5ta fila obtenemos la matriz siguiente

f g h i j
w2 1 0 0 0 1
 
w3 1 1 0 0 0
M  w 4  0 1 1 0 0 Esta matriz es coincidente con la de G.
G  
w5  0 0 1 1 0
w 1  0 0 0 1 1 
En nuestro ejemplo: las funciones de biyección serían tanto para vértices como para aristas.

f (v1 ) = w2 f (v2 ) = w3 f (v3 ) = w4 f (v4 ) = w5 f (v5 ) = w1

15
 MATEMATICA DISCRETA.2023
g (a ) = f g (b ) = g g (c ) = h g (d ) = i g (e ) = j

La arista b incide en v2 y v3  la imagen de b debe incidir en f ( v2 ) y f ( v3 )

En efecto la arista g de G incide en w3 y w4 y como esto se cumple para todas las aristas, los grafos G y G
son isomorfos.
Φ(b)={v2,v3} g(b)={f(v2),f(v3)} Φ(g)={w3,w4}

Si observamos también podemos obtener la matriz G si cambiamos las columnas.

Reordenamos las columnas y también obtenemos una matriz similar a la 𝑀𝐺

j f g h i
𝑤1 1 0 0 0 1
𝑤2 1 1 0 0 0
𝑀𝐺⃐ = 𝑤3 0 1 1 0 0
𝑤4 0 0 1 1 0
𝑤5 (0 0 0 1 1)

Y las funciones de biyección serían para los vértices y las aristas las siguientes
f (v1 ) = w1 f (v2 ) = w2 f (v3 ) = w3 f (v4 ) = w4 f (v5 ) = w5
g (a ) = j g (b ) = f g (c ) = g g (d ) = h g (e ) = i

Si previo reordenamiento de filas y columnas de sus matrices de incidencia, éstas coinciden, los grafos son
isomorfos.
Lamentablemente, no hay método conocido más eficiente para comprobar si dos grafos son isomorfos. Sin
embargo, hay pruebas sencillas que se pueden utilizar para mostrar que ciertos pares de grafos no son iso-
morfos.

Invariante del isomorfismo

Definición: Una propiedad P se llama invariante del isomorfismo del grafo, si y sólo si, dados dos grafos
cualesquiera G y G , si G tiene la propiedad P y G es isomorfo a G, entonces G tiene la propiedad P.

Teorema:
Cada una de las siguientes propiedades es un invariante del isomorfismo del grafo, dónde, n, m y k son todos
enteros no negativos.
1) Tiene n vértices
2) Tiene m aristas
3) Tiene un vértice de grado k
4) Tiene m vértices de grado k
5) Tiene un ciclo de longitud k
6) Tiene un ciclo simple de longitud k
7) Tiene m ciclos simples de longitud k
8) Es conexo
9) Tiene un ciclo de euler Todos su vértices son de grado par
10) Tiene un ciclo de Hamilton. Ciclo simple que contiene a todos los vértices

Sin embargo que dos grafos tengan los mismos invariantes es una condición necesaria para que dos grafos
sean isomorfos, pero no es una condición suficiente.
En el ejemplo dado previo a encontrar las biyecciones entre vértices y aristas los grafos G y G deben con-
servar las invariantes de cada grafo, es decir deben tener:
16
 MATEMATICA DISCRETA.2023
a) el mismo número de vértices
b) el mismo número de aristas
c) los vértices correspondientes deben tener el mismo grado.

Si cualesquiera de estas condiciones no se cumplen en los dos grafos, estos no son isomorfos.

Tipos especiales de grafos

Grafos k-regulares
El grafo regular de grado k o grafo k-regular es aquél en el cual todos los vértices tienen grado k.
Los grafos k regulares pueden ser simples o no.
Ejemplos:

Grafos simple 3- regular Grafos 3 -regular no simple

Grafo Completo de p vértices

Definición:
El grafo completo de p vértices que simbolizaremos Kp es un grafo simple cuyo conjunto de vértices tiene p
elementos, tal que todo par de vértices distintos determina una arista.
O lo que es lo mismo: un grafo simple es completo si todo vértice está conectado con todo otro vértice

Propiedades del Grafo Completo KP

1) Todo vértice tiene grado p – 1.

2) El subgrafo restante de Kp respecto de cualquiera de sus vértices es isomorfo con Kp – 1
3) Dados 3 vértices distintos de Kp ( p  3 ) existe un ciclo de longitud 3 que los contiene sólo a ellos.
4) Para p  3 , Kp es un bloque es decir que carece de itsmos y puentes
5) Si A es el conjunto de aristas de Kp entonces
p ( p 1)  p 
|A|      C p , 2
2  2
Un grafo completo Kp siempre tendrá un ciclo hamiltoniano, cuando p ≥ 3,

Grafo Complementario

Definición:

17
 MATEMATICA DISCRETA.2023
Dado un grafo simple G = ( V , A ,  ) se llama grafo complementario de G al grafo  G  V , A' ,  ' que
tiene el mismo conjunto de vértices que G y cuyas aristas son justamente las que le faltan a G para ser com-
pleto.

Grafos bipartitos Si los vértices del grafo simple se pueden colorear de sólo 2 colores es bipartito

Definición:
Un grafo simple G se dice bipartito si su conjunto de vértices se puede particionar en dos subconjuntos V1 y
V2 tales que toda arista del grafo conecta un vértice de V1 con un vértice de V2.
Recordemos que V1 y V2 forman una partición de V sii V1  V2 =V y V1  V2 = 
El grafo de la figura es bipartito porque si hacemos V1 = { v1 , v4 } V2 = { v2 , v3 , v5 } estos dos conjuntos
forman una partición de V y además cada arista del grafo tiene un extremo en un elemento de V1 y el otro
extremo en un elemento de V2.
Para mayor claridad, el grafo bipartito suele representarse como sigue, colocando encolumnados a la iz-
quierda los elementos de V1 y encolumnados a la derecha los elementos de V2.

En la práctica los grafos bipartitos se presentan naturalmente cuando los vértices representan 2 subconjuntos
distintos de entes u objetos.

Grafo Bipartito Completo

Definición:
Un grafo simple es bipartito completo cuando es bipartito y además cada vértice de V1 está conectado con
cada vértice de V2

Un grafo bipartito completo se denota Kp,q (o también Kn1;n2) donde el primer subíndice es el número de
elementos de V1 y el segundo subíndice es el número de elementos de V2.

18
 MATEMATICA DISCRETA.2023
En general se acepta que siempre sea p  q .

Ejemplos:

GRAFO PLANAR (GRAFO PLANO)

Definición de Grafo Plano:

Un grafo es plano si puede dibujarse en el plano de manera que ningún par de sus aristas se corte(por corte
de aristas se entiende la intersección de las líneas que representan a las aristas) en un punto distinto de sus
vértices.
Un grafo se dice plano si y sólo si existe una representación plana del mismo, de modo que sus aristas se
corten sólo en los vértices de G.
Un grafo G es un grafo aplanable, si es posible dibujar a G en un plano de tal manera que cada par de sus
aristas solo se corten en los vértices.
Por ejemplo:
El grafo K4 puede representarse de esta manera

Pero puede ser aplanado de las siguientes dos

maneras.

En cambio no es posible unir los cinco vértices de un pentágono con cada uno de los otros, sin cortar las
aristas. Por lo tanto no es un grafo planar.

19
 MATEMATICA DISCRETA.2023

El siguiente grafo completo K3, 3 no se puede aplanar

Si rebatimos el vértice v3 nos quedaría

pero es imposible aplanarlo

Por lo tanto K3, 3 no es plano

Mapa

Se llama mapa a una representación plana particular de un grafo plano finito. El mapa es conexo si el corres-
pondiente grafo es conexo. Un mapa dado divide el plano en varias regiones y también se presenta una re-
gión sin frontera, es decir no acotada. Así no hay pérdida de generalidad al contar las regiones si suponemos
que nuestro mapa está contenido en algún rectángulo mayor en lugar de en el plano completo.

Frontera de una región

Sea un grafo plano G, al conjunto de vértices y aristas que inciden en
una región r de G se le llama la frontera de r.
En este grafo la frontera de la región R3 es
{v3, v3v4, v4, v4v6 ,v6 ,v3v6}
La región R6 es la región sin frontera y su frontera es
{v1,v1v3,v3,v2v3,v2,v2v6,v6,v6v7,v7,v5v7,v5,v4v5,v4,v4v1}

Euler dio una fórmula que conecta el número de vértices, el número de aristas y el número de regiones r
para cualquier mapa conexo (grafo plano conexo)

Teorema de Euler para grafo plano conexo

Si G es un grafo plano conexo con | V |= nº de vértices,

| A |= nº de aristas y que descompone al plano en r regiones entonces se cumple que

|V|–|A|+r=2
Demostración:
Por inducción sobre | A |
Si | A |= 0 , entonces
| V |=1, r =1 y se cumple que | V | – | A | + r = 2
Supongamos que el resultado es cierto para todos los grafos planos y conexos con | A | -1 aristas, dónde

20
 MATEMATICA DISCRETA.2023
| A | ≥ 1.
Sea G un grafo plano conexo y con | A | aristas r regiones y | V | vértices
Si G es un árbol → r = 1 , | V |=| A | +1 → | V | + r =| A | +1+ 1 = | A | + 2

Si G no es un árbol → existe alguna arista a de un ciclo de G , G-{a} es plano, conexo con | V | vértices,
| A | -1 aristas y r-1 regiones.
La hipótesis de inducción asegura entonces que |V | -(| A| -1) +(r-1) = 2 es decir | V | – | A | + r = 2
Ejemplo
|V|=5 , |A|=7 r=4 5–7+4=2

Teorema de Euler para Grafo plano no Conexo

Si G es un grafo plano no conexo se cumple |V|–|A|+r= +1
dónde  es el número de componentes conexas. número de componentes
conexas

En el ejemplo:

|V|=9 , |A|=8 r=3

 =3  9–8+3=3+1
4 =4

Grafos no planares
El teorema de Kuratowski proporciona una prueba sencilla para determinar si un grafo dado es o no planar.

Teorema de Kuratowski:
Un grafo es plano si, y solo si, no contiene ningún subgrafo isomorfo a K5 ni a K3,3 ni a subdivisiones de
ellos.
Ejemplo: grafo de Petersen

El grafo de Petersen no es plano, ya que contiene una subdivisión de K3,3

21
 MATEMATICA DISCRETA.2023
Otro ejemplo
Este grafo es isomorfo a K5 , por lo tanto no es plano

Grafos coloreados

El coloreado de un grafo G=(V,A,φ) es una asignación de colores a los vértices de G de tal forma que vértices
adyacentes tengan colores distintos. Se dice que G es n-coloreable si existe un coloreado de G que usa n
colores.

Número cromático
El número cromático de un grafo G, es el número mínimo de colores necesario para colorear G. Y se utiliza
la letra griega chi para representarlo χ(G),
No es fácil determinar el número cromático de un grafo
Ejemplos
Si coloreamos el grafo completo K4 observamos que utilizamos cuatro colores. a b c d
Es decir su número cromático seria 4
χ(K4) = 4.
Y si seguimos analizando grafos de este tipo es decir completos,
concluimos que si el grafo es Kn → χ(Kn) = n es decir su nú-
mero cromático es n

Grafos bipartitos y coloración

Un grafo bipartito es un grafo cuyos vértices se pueden dividir en dos subconjuntos dónde los vértices de cada
subconjunto están conectados con todos los vértices del otro subconjunto y no están conectados con ningún
vértice de su propio subconjunto. Por tanto necesitamos dos colores para colorear un grafo bipartito
Ejemplos:

Teorema:
Los siguientes enunciados son equivalentes para un grafo G
i) G es 2-coloreable
ii) G es bipartito
iii) Cada ciclo de G tiene longitud par

Ejemplo:

22
 MATEMATICA DISCRETA.2023
Coloreamos el siguiente grafo utilizando el Algoritmo secuencial de Welch-Powell, lo cuál nos da como re-
sultado la siguiente coloración de los vértices.
V1 V2 V3 V4 V5 V6 V7 V8
a b b a a b a b
Por tanto podemos dividir sus vértices en dos subconjuntos
V1 ={v1,v4,v5,v7} y V2={v2,v3,v6,v8}
Por tanto el grafo es bipartito K4,4 que se puede dibujar de la siguiente manera
y que es coloreable con solo dos colores.

Grafos planares y coloreado

Teorema: Cualquier grafo planar G es cinco-coloreable.

Este teorema está demostrado por inducción completa, nosotros solo lo enunciaremos.

Ejemplo:
Para colorear un grafo podemos utilizar el Algoritmo secuencial de Welch-
Powell que dice:
Primero se ordena los vértices de G según sus grados decrecientes.
Usar un color para colorear el primer vértice y para colorear en orden secuen-
cial, cada vértice de la lista que no es adyacente a un vértice pintado previa-
mente con este color. Luego se repite el proceso
Los grados de los vértices del grafo son gr (v1)= 4; gr (v2)= 2; gr(v3)= 3;
gr(v4)= 3; gr(v5)= 2.
Ordenamos los vértices según sus grados decrecientes y coloreamos de acuerdo al Algoritmo.
V1 V3 V4 V2 V5
a c b b d
Colores y mapas
Por colorear un mapa M se entiende asignar colores a las regiones de M tal que las regiones adyacentes tengan
colores distintos. Un mapa es n-coloreable si existe una coloración de M que usa n colores

Los mapas se colorean de modo tal que regiones con un segmento de frontera común tengan colores diferentes.
Aunque algunos mapas se pueden colorear con menos de 4 colores.
Un mapa plano es un grafo plano en el que podemos interpretar a las regiones como países, las aristas se
interpretan como las fronteras entre los países y los vértices representan la intersección de las fronteras.
El problema de colorear un mapa plano G, de manera que los países fronterizos no tengan el mismo color,
puede reducirse al problema de colorear un grafo, construyendo el grafo dual G’ de G de la manera siguiente.
Los vértices del grafo dual G’ provienen de reemplazar cada región, incluyendo las regiones sin frontera, por
un vértice.

23
 MATEMATICA DISCRETA.2023
Una arista en G’ une dos vértices si las correspondientes regiones de G están separadas por una frontera. Una
coloración del mapa G es equivalente a colorear los vértices del grafo dual G’.
Ejemplos

Teorema de los cuatro colores:

Si las regiones de un mapa M se colorean de forma que las regiones adyacentes tengan colores distintos, en-
tonces no se necesitan más de cuatro colores.
Cada grafo planar es 4-coloreable
Ejemplo

Grafos rotulados o ponderados

Un grafo G se llama un grafo rotulado o ponderado si sus aristas y/o vértices se le asignan datos de alguna
clase. En particular, si a cada arista a de G se le asigna un número no negativo entonces a l(s) se le llama el
peso o longitud l(s) de a.
Frecuentemente es importante encontrar una trayectoria de peso mínimo entre dos vértices dados de un grafo
rotulado

Algoritmo del Camino más corto o de Dijkstra

El algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es un algoritmo para la determina-
ción del camino más corto dado un vértice origen al resto de vértices en un grafo con pesos en cada arista. Su
nombre se refiere a Edsger Dijkstra, quien lo describió por primera vez en 1959.
La idea subyacente en este algoritmo consiste en ir explorando todos los caminos más cortos que parten del
vértice origen y que llevan a todos los demás vértices; cuando se obtiene el camino más corto desde el vértice
origen, al resto de vértices que componen el grafo, el algoritmo se detiene.
Considérese un grafo etiquetado conexo con dos vértices (o nodos) especiales llamados Origen y Destino. A
cada una de las aristas se le asocia una Distancia no negativa. El objetivo es encontrar la ruta más corta (la
cadena con la mínima longitud total) que va del origen al destino.

Descripción del método

Objetivo de la iteración n-ésima: encontrar el n-ésimo vértice más cercano al origen. (Este paso se repetirá
para n = 1,2,..., hasta que el n-ésimo vértice más cercano sea el vértice destino.)

24
 MATEMATICA DISCRETA.2023
Datos para la n-ésima iteración:(n - 1) vértices más cercanos al origen (encontrados en las iteraciones pre-
vias), y también su ruta más corta y la distancia desde el origen.(Estos vértices y el origen se llamarán vértices
resueltos; el resto son vértices no resueltos.)
Candidatos para el n-ésimo vértice más cercano: cada vértice resuelto que está conectado directamente por
una arista con uno o más vértices no resueltos proporciona un candidato, y éste es el vértice no resuelto que
tiene la arista más corta. (Los empates proporcionan candidatos adicionales.)
Cálculo del n-ésimo vértice más cercano: para cada vértice resuelto y sus candidatos, se suma la distancia
entre ellos y la distancia de la ruta más corta desde el origen a este vértice resuelto. El candidato con la distancia
total más pequeña es el n-ésimo vértice más cercano (los empates proporcionan vértices resueltos adicionales),
y su ruta más corta es la que genera esta distancia.

n-esima Vértice Resuelto Vértice no resuelto Distancia total n-esimo Distancia Ultima
iteración Conectado directa- más cercano involucrada vértice mas mínima conexión
mente a vértice no conectado cercano
resuelto
1 a c 1 c 1 ac
2 a b 3 b 3 ab
c b 1+2=3 b
cb
c d 1+2=3 d
c e 1+2=3 e cd
ce
3 d f 3+4=7 f 5 ef
e f 3+2=5
4 e g 3+3=6 g 6 eg
f g 5+1=6
fg
5 f z 5+2=7 z 7 fz
g z 6+1=7
gz

Ejemplo
Encontrar el camino más corto entre el punto de origen a y el punto final z

Para encontrar los caminos conectamos los puntos obtenidos en la iteración, de acuerdo a esto tenemos
dos caminos que son a, c, e, g , z y también a, c, e, f , z de longitud 7.
Nota
Cuando salimos del vértice origen es nuestro primer vértice resuelto analizamos a partir de él, el vértice o los
vértices más cercanos, puede ser que haya más de uno si las distancias más cercanas son iguales, lo que nos
sucede en la iteración dos, del ejemplo precedente.
25
 MATEMATICA DISCRETA.2023

Tener cuidado cuando un vértice es elegido por ser el más cercano pasa a la categoría de vértice resuelto y
no puede ser usado de nuevo como opción.
Cada vértice resuelto pasa a ser parte de la siguiente iteración en búsqueda del más cercano a cada uno de
los vértices resueltos.
La iteración finaliza cuando llegamos al vértice destino.
El camino más corto se encuentra uniendo los segmentos obtenidos en la iteración y su longitud es la distan-
cia final obtenida.

Bibliografía
MATEMATICAS DISCRETAS. Kenneth A Ross y Charles R. B. Wright. Prentice Hall. 1990.
MATEMATICA DISCRETA Y COMBINATORIA. Ralph Grimaldi. Addison- Wesley Iberoamericana.
1998.
ALGEBRA I y II. Armando Rojo. Editorial El Ateneo. 1998.
MATEMATICA DISCRETA Y SUS APLIACIONES. Kenneth H. Rosen. Mc Graw Hill. España. 2004
MATEMATICA DISCRETAS CON TEORIA DE GRAFICAS Y COMBINATORIA. Veerarajan T. Mé-
xico McGraw-Hill 2008
PROBLEMAS RESUELTOS DE MATEMATICA DISCRETA. Feliz García Merayo, G.Peñalver,A.Luna
Editorial Thomson 2007
MATEMATICAS PARA LA COMPUTACION, José A. Jiménez Murillo. Alfaomega Grupo Edi-tor.Mé-
xico.2009
MATEMATICAS DISCRETAS,Ramón E.Armenta,Alfaomega Grupo Editor. México.2010
MATEMATICAS DISCRETAS CON APLICACIONES. Susanna S.Epp.Mexico Cengage Learning.2011
ALGEBRA LINEAL Y SUS APLICACIOES. David C. Lay .Pearson Educación. Mexico.2012

26