TEMA 2. TEORÍA DE GRAFOS.

1. INTRODUCCIÓN

La teoría de grafos nació como una rama de la Topología, siendo hoy en día una herramienta
matemática indispensable en campos muy diversos.

Si consideramos las siguientes figuras que representan una red eléctrica y un plan de carreteras,
ambas pueden ser representadas esquemáticamente por unos puntos P,Q, R. S T llamados vértices y
por unas líneas llamadas ejes. AL conjunto total lo llamamos GRAFO

Observar que el cruce de PS con TQ no es un vértice. También podemos crear otro grado
eliminando el cruce, dibujando la recta PS fuera del rectángulo PQST. Así el nuevo grafo nos
informa de cómo están conectados los cables de la red eléctrica o de si existe una carretera directa
desde un cruce a otro. La única información que hemos perdido es la relativa a las propiedades
métricas, (longitud de la carretera, rectitud del alambre, etc.

De forma general puede decirse que los grafos se utilizan para representar las relaciones entre los
elementos de un conjunto.

2. EL LENGUAJE DE LOS GRAFOS

2.1 GRAFO SIMPLE. TIPOS DE GRAFOS. ISOMORFISMO

Un grafo simple es un par (V,E), donde V es un conjunto de elementos, y E es grupo de pares de

elementos de V, donde no se permite la repetición de ninguno y no importa la ordenación del par de
elementos.

Ejemplo:V={1,2,3} E={{1,2},{2,3}} Puede representar las conexiones aéreas entre 3 ciudades,

ordenadores conectados por red, o los números del 1 al 3 cuyas diferencias tengan modulo

Partes de un grafo simple:

• Un vértice o nodo son cada uno de los elementos de V

• Ejes o aristas son cada una de las uniones entre dos pares de elementos de V(vértices); son las
parejas de V que forman E.

• Vértices adyacentes: Dos vértices i, j ∈V son adyacentes si están conectados por algún eje !
{i,j} ó {j,i} ∈E

• Bucle: Cuando en un eje los extremos coinciden, {i,i}

Tipos de grafos:

• Grafo simple: cuando no contiene ningún bucle.

• Grafo nulo: cuando no contiene ejes, E=∅
• Grafo completoTEMA
cuando tiene todos los
2. Fundamentos ejes posibles,
y aplicaciones de laincluyendo los bucles.
teoria de grafos. Diagramas en árbol
• Grafo simplemente completo cuando todos los vértices son adyacentes, el grafo tiene
todos los ejes excepto los bucles 

TEMA 2. Fundamentos yGrafo
aplicaciones de la completo
simplemente teoria de grafos. Diagramas en árbo
Aplicación Adyacente: Para tener completamente determinado un grafo basta con conocer V y a la
aplicación adyacente:
Para tener completamente determinado un grafo basta con conocer V y a la aplicación
adyacente:
Grafo simplemente completo
Γ :V V Γ(ei ) = {e j : (ei , e j ) o (e j , ei ) ∈ E}
Para tener completamente determinado un grafo basta con conocer V y a la aplic
ei ej
adyacente:
Isomorfismo de grafos: dos grafos (V,E) y (V’,E’) son isomorfos si existe una aplicación que
Γ :V V Γ(ei ) = {e j : (ei , e j ) o (e j , ei ) ∈ E}
Isomorfismonos de relaciona
grafos: dos los vértices: φ: V !
grafos (V,E) V’ tal son
y (V’,E’) que si (ei, ej )∈E si
isomorfos entonces
existe (φ(e
unai),φ(e j ))∈E’ y que
aplicación de igual
nos
forma si (e ’,e ’)∈E’ e i
entonces (φ -1
(e ’
), φ -1
(e e
’ j
))∈E. Son grafos con diferente numeración de lossi
relaciona los vértices: φ: i Vj ! V’ tal que si (e , i e )∈Ej entonces (φ(e ),φ(e ))∈E’ y de igual forma
i j i j
vértices pero misma
TEMA forma. y aplicaciones de la teoria de grafos. Diagramas en árbol
2. Fundamentos
(ei’,ej’)∈E’ entonces (φ (ei ), φ-1(ej’))∈E.
-1 ’
Isomorfismo de grafos:Sondos grafos
grafos con(V,E) y (V’,E’) numeración
diferente son isomorfos desi los
existe una aplicació
vértices
2.2. Multigrafo de orden
nos relaciona p.
los vértices: φ: V ! V’ tal que si (ei, ej )∈E entonces (φ(ei),φ(ej ))∈E’ y de
pero misma forma.
Definición:forma Unsip-grafo
(ei’,ej’)∈E’
es unentonces
Grafo
par (V,E)(φdonde (ei ), φV-1es
-1 ’ completo
simplemente (ej’))∈E. Son grafos
un conjunto con diferente
de elementos numeración
y E es un d
2.2 MULTIGRAFO ParaDE
conjunto de vértices
tener ORDEN pero
completamente
pares de misma
V,Pdonde elforma.
determinado un grafo basta con conocer V y a la aplicación
orden de los parejas no importa, y donde una pareja puede
adyacente:
aparecer un máximo de p veces en E.
Un p-grafo es un par 2.2. Multigrafo
Γ : V (V,E) donde VVes un de eorden
i ) = {e j : (p.
Γ(conjunto ede o (e j , ei ) ∈ E}y E es un conjunto de pares de V,
i , e j )elementos

donde el orden de losE={e j={eDefinición:

j1,eno
eiparejas j2}, importa, ∈E p-grafo
ej1, eej2j Un y: I(e
donde j)=∑es una
vecesj1≤p
un pareja ∀j} (V,E)
par puede dondeaparecer
V es un un conjunto
máximo de
de elementos
p veces y E
en E. Isomorfismo
Con esta de grafos:
conjunto
definición dedos grafos
pares
un grafode(V,E)V,y (V’,E’)
simple esson
donde unisomorfos
el1-grafo.
orden si existe
de los una parejas
aplicación que
no importa, y donde una pareja p
nos relaciona los vértices: φ: V ! V’ tal que si (ei, ej )∈E entonces (φ(ei),φ(ej ))∈E’ y de igual
forma aparecer
si (ei’,e un máximo
j’)∈E’clásico
entonces -1 ’ de
φ-1(e ’ p veces en E.
Un ejemplo es(φ el
(ei ),multigrafo
j ))∈E. Son
degrafos con diferente
orden 2 que numeración
pretendedeestudiar
los los 7 puentes de
vértices pero misma forma.
Königsberg(Prusia) que
E={eune las
j={ej1,ej2orillas ej2∈E
}, ej1, A,C y dos islas
: I(e j)=∑ vecesj1≤p ∀j}
B,D:
2.2. Multigrafo de orden p.
e6
Definición: UnCon esta
B es definición
p-grafo un grafo
un par (V,E) donde V es unsimple
conjuntoesdeun 1-grafo.
elementos y E es un
conjunto de pares de V, donde eel orden de los parejas no importa, y donde una pareja puede
Con esta definición un egrafo
3
aparecer un máximoUnsimple
deejemplo
es2 un 1-grafo.
clásico
p veces en E. es el multigrafo de orden 2 que pretende estudiar los 7 puent
A e 1 C
Königsberg(Prusia)
ej1, ej2∈E : I(ej)=∑que1≤pune las orillas A,C y dos islas B,D:
∀j}V={A,B,C,D}
Un ejemplo clásico E={e esj={ej1el,ej2},multigrafo de orden
vecesj
2 que pretende estudiar los 7 puentes de
E={(A,B),(A,B),(A,D),(A,D),(A,C),(B,C),(D,C)}
e4 e6un grafo simple
Con esta definición es un 1-grafo.
Königsberg(Prusia) que une las orillaseA,C 5
By dos islas B,D:
eUn
7 ejemplo clásico es el multigrafo de orden 2 que pretende estudiar los 7 puentes de
Königsberg(Prusia) que une e2 B,D:
De3las orillas A,C y dos islas
e6
A B e1 C V={A,B,C,D}
e3 e2
La mayoría de autorese4Ccoinciden een considerarE={(A,B),(A,B),(A,D),(A,D),(A,C),(B,C),(D,C)}
el nacimiento del nacimiento del grafo
A e 1
V={A,B,C,D} 5
cuando Euler(S XVIII) estudiabaE={(A,B),(A,B),(A,D),(A,D),(A,C),(B,C),(D,C)}
este 2-grafo como pasatiempo, viendo la forma de cruzar
e4 e 7 e5
todos los
e7 puentes sin pasar dos veces
D por el mismo.
D
2.3.Grafo dirigido u orientado.
La mayoría deLaautores
mayoría de enautores
coinciden considerarcoinciden
el nacimientoendel considerar
nacimiento del el nacimiento del nacimiento
grafo del
A veces
cuando las
Euler(S relaciones
XVIII)
cuando estudiabaentre los
este 2-grafo
Euler(S XVIII) vértices no son
como pasatiempo, simétricas y
viendo la forma no es equivalente
de cruzar
estudiaba este 2-grafo como pasatiempo, viendo {ei,ej} ala{ejforma
,ei} de c
La mayoría de autores
todos coinciden
los puentes sin pasar dosen considerar
veces por el mismo. el nacimiento del nacimiento del grafo cuando
como era en el caso
todos de los p-grafos.
los puentes sin pasarPor dosejemplo
veces por la relación
el mismo. de “hijos de”, “divisores de” no
Euler(S XVIII) 2.3.Grafo
estudiaba este 2-grafo como pasatiempo,
dirigido u orientado.Surgen así los grafos orientados.
viendo la forma de cruzar todos los
tienen esa bidireccionalidad.
puentes sin pasar dos veces por elentre
mismo.
A veces
2.3.Grafo
las relaciones
dirigido
Definición: Grafo orientado esuunorientado.
los vértices no son simétricas y no es equivalente {ei,ej} a {ej,ei}
par (V,A) donde V es un conjunto de elementos y A es un
como era en el caso de los p-grafos. Por ejemplo la relación de “hijos de”, “divisores de” no
conjunto formado
tienen esa A veces las
por parejas
bidireccionalidad. relaciones
Surgen asíde grafosentre
los elementos los
de vértices
orientados. V, dondeno si son simétricas
importa y no
el orden dees
losequivalente
elementos {ei,ej} a
del par, siendo
como
Definición: distinto
Grafoera en{eiel
orientado ,e
esj}caso
unapar
{ej(V,A)
,e
dei} con
los eVj es
p-grafos.
donde y euni pertenecientes
Por de
conjunto ejemplo ala
elementos yV.
Arelación
es un de “hijos de”, “divisores d
 La mayoría de autores coinciden en considerar el nacimiento del nacimiento del g
cuando Euler(S XVIII) estudiaba este 2-grafo como pasatiempo, viendo la forma de cr
todos los puentes sin pasar dos veces por el mismo.
2.3 GRAFO DIRIGIDO U ORIENTADO
2.3.Grafo
A veces las relaciones entre dirigido
los vérticesu no
orientado.
son simétricas y no es equivalente {ei,ej} a {ej,ei} como
era en el caso de losA p-grafos.
veces las relaciones
Por ejemplo entre los vértices
la relación no sonde”,
de “hijos simétricas y node”
“divisores es equivalente
no tienen esa{ei,ej} a {e
bidireccionalidad.como era en el caso de los p-grafos. Por ejemplo la relación de “hijos de”, “divisores de
tienen esa bidireccionalidad. Surgen así los grafos orientados.
Grafo orientado es un par (V,A) donde V es un conjunto de elementos y A es un conjunto formado
Definición:
por parejas de elementos de Grafo orientado
V, donde es un par
si importa (V,A) donde
el orden de losV elementos
es un conjuntodel de
par,elementos
siendo y A e
distinto{ei,ej} a conjunto
{ej,ei} conformado
ej y ei por parejas de aelementos
pertenecientes de V, donde
V. En los grafos si importa
orientados el orden
el eje se de los eleme
llama arco
del par, siendo distinto {ei,ej} a {ej,ei} con ej y ei pertenecientes a V.
Ejemplo: V={a,b,c,d} A={(a,b),(b,a),(d,b),(c,b)}.
En los grafos orientados el eje se llama arco. Arco es cada par de elementos que fo
partei será
Dado un arco {i,j}, de A.elLos demás
vértice elementos
inicial y j el son los mismos
vértice final. Seque
diceenque
grafos
i esno orientados.
predecesor de j y j
sucesor de i. i ==> j.
Jose Luis Lorente (preparador oposiciones secundaria www.joseluislorente.es)
La aplicación sucesor se define Γs (i) = { j : (i, j) ∈ A} siendo la aplicación predecesor Γp ( j) =
{i : (i, j) ∈ A} . Para conocer un grafo orientado basta con conocer V y una de las anteriores
aplicaciones.

2.4 REDES

Una red (dirigida) es una terna (V, E, l) donde (V, E) es un grafo(dirigido) y la aplicación l : E ==>
Rk que asocia a cada eje(arco) un valor numérico, pudiendo ser multivaluado.

Ejemplo: (V,E,l), V={León, Salamanca, Valladolid};

E={(León, Salamanca),(Salamanca,Valladolid), (León,Valladolid)}

l=aplicación que nos da la distancia y el tiempo medio de un autobús: l(León,Valladolid)=170km,

1,8h; l(León,Valladolid)=200km,2,2h; l(Valladolid, Salamanca)=140km,1,1h.

3. ORDEN, TAMAÑO Y GRADO DE INCIDENCIA

Orden de un grafo(dirigido) O(G) es el número de vértices

Tamaño de un grafo(dirigido) T(G). es el número de ejes (arcos) que tiene.

Propiedades de O(G) y T(G):

 denota como T(G).
Relación en algunos casos de O(G) y T(G):

0n-
• Un grafo completamente simple tiene .. ++ de tamaño, siendo n el orden del grafo.
2 / ,
0n-
• Un grafo completo tiene .. ++ +n donde estos n a mayores respecto al grafo
/ 2,
completamente simple son debidos a los bucles que hay por cada uno de los n
vértices.

0n-
• Un grafo completamente simple dirigido tiene 2 .. ++ =n(n-1) de tamaño, siendo n el
/ 2,
orden del grafo.

0n-
• Un grafo completo dirigido tiene 2 .. ++ +n=n2 donde estos n a mayores respecto al
/ 2,
anterior son debidos a los bucles que hay por cada uno de los n vértices.

Grado
TEMA 2. Fundamentos y aplicaciones de la teoria de grafos. Diagramas en árbol
JosedeLuis
incidencia de un vértice
Lorente (preparador i de unsecundaria
oposiciones grafo (dirigido) es el no de ejes (arcos) en los que
www.joseluislorente.es) 3 interviene el
vértice i, considerando que el bucle {i,i} cuenta doble. Se denota como g(i).
Grado de incidencia de un vértice i de un grafo (dirigido) es el nº de ejes (arcos) en los que
En Grafos
interviene dirigidos:
el vértice i, considerando que el bucle {i,i} cuenta doble. Se denota como g(i).

• Grado
En Grafos de salida g+(i) es el número de arcos donde i extremo inicial.
dirigidos:

• •Grado dede
Grado entrada
salida g-+(i) es el
(i) es el número
número de arcos donde
donde ii es extremo
extremo final. 

inicial.
• Grado de entrada g-(i) es el número de arcos donde i es extremo final.
Propiedades: (demostración Lorente)
Propiedades:
1. El tamaño de un grafo es igual a la semisuma de todos los grados de incidencia:
1
t (G ) = ∑ g (i) . Es consecuencia de que cada eje (arco) contribuye 2 veces en
2 i∈V
el grado de incidencia (uno por cada vértice). Los bucles también.
2. En todo grafo dirigido y para todo vértice i, g(i)=g+(i)+g-(i), ya que tanto g+(i) como
g-(i) contribuyen una vez en el grado de incidencia.
3. En todo grafo hay un nº par de vértices con grado impar:
Demostración:
4. GRAFOS CONEXOS
∑ g (i) = 2t (G ) separamos grados par e impar
4.1i∈VGRAFOS CONEXOS
´` ´´ ´´ ´´

∑
(V’,E’)
i∈V
∑
) =un subgrafo
g (ies
i∈V
∑
g (i ) + deg ((V,E)
i ) = 2sit (se
i∈V
→ gque
G )cumple ∑
(i ) V’
i∈V
suma
⊆ Vgy(iE’
) par
⊆E ∑ g (i) suma g (i)impar
i∈V
´´
Ejemplo: G1=(V1, E1´), V1=(1,2,3); E1={(1,2),(2,3)}, G2=(V2,E2), V2=(1,2); E2={(1,2)}
∑ g (i) = 2t (G ) − ∑ g (i) ≡ par
i∈V i∈V
G2 subgrafo de G1 123
par
´´
g(i)
(V́,Ees impar,
́) es luego
el grafo para
complementario ∑
g (i ) que
de sea
i∈V
parsidebe
(V,E) haberque
se cumple un numero par cde
V=V́y É=E g(i).
(complementario de E).

4. Grafos Conexos.
 Ejemplo: G={V=(1,2,3);E={(1,2),(2,3),(1,1)}}

G´={V´=(1,2,3); E´={(1,3},(2,2),(3,3)}
Ejemplo: G={V=(1,2,3);E={(1,2),(2,3),(1,1)}}

Ǵ={V́=(1,2,3); É={(1,3},(2,2),(3,3)}

Jose Luis Lorente (preparador oposiciones secundaria www.joseluislorente.es)

Grafo unión de dos grafos (V,E), (V́,E ́) es el grafo resultante de unir V y V́ (V∪V́) y E y E ́
(E∪É) TEMA 2. Fundamentos y aplicaciones de la teoria de grafos. Diagramas en árbol

Ejemplo: Definición:
G 1 Grafo
={Vde1 =(1,2,3); E 1 (V´,E´)
unión de dos grafos (V,E), ={(1,2)}, G 2 =(V
es el grafo resultante de unir2V=(2,3,4);
y V´ E 2 ={(2,4)}
G=G1∪G2={V=(1,2,3,4),E={(1,2},(2,4)}
(V∪V´) y E y E´ (E∪E´)

Ejemplo: G1={V1=(1,2,3); E1={(1,2)}, G2=(V2=(2,3,4); E2={(2,4)}

Grafo G=(V,E) es conexo si no se puede poner como unión de 2 grafos disjuntos (no vértices en
G=G1∪G2={V=(1,2,3,4),E={(1,2},(2,4)}
común), esto ocurre si en el grafo todos los vértices unidos formando un bloque.
Definición: Grafo G=(V,E) es conexo si no se puede poner como unión de 2 grafos disjuntos
(no vértices en común), esto ocurre si en el grafo todos los vértices unidos formando un
Grafo inconexo
bloque. es aquel que no es conexo.
Definición: grafo inconexo es aquel que no es conexo.
Ejemplo:
1 2 3 Conexo

Inconexo(2 componentes conexas)

1 2 3 4

4.2. Cadenas y ciclos

4.2 CADENAS Y CAMINOS
Definición: Dado un grafo (E,V) llamamos cadena a una secuencia elemental de vértices y
ejes que comienza y acaba en un vértice(no necesariamente el mismo)
llamamos cadena
Ejemplo: v1Dado
,(v1,v2),vun grafo
2,(v2,v (E,V)que
4),v4, decimos a una secuencia
la cadena une v1 conelemental
v4. de vértices y ejes que comienza y
acaba en unTipos
vértice(no
de cadenas:necesariamente el mismo)
• Cadena simple : no se repite ningún eje
Ejemplo: v1,(v1,v2),v2,(v2,v4),v4, decimos que la cadena une v1 con v4.
• Cadena elemental: No se repite ningún vértice.
Definición: un ciclo es una cadena donde el primer y el último vértice es el mismo
Cadena simple : no se repite ningún eje Cadena elemental: No se repite ningún vértice.
Ejemplo: v1,(v1,v2),v2,(v2,v4),v4,(v4,v1),v1.

un ciclo es una cadenasidonde

Ciclo elemental el primer
solo coinciden y yelúltimo
el primer último vértice es el mismo 

vértice.

Ejemplo: v1Nota: 2),v2,(v2,v4),v4,(v4,v1),v1. 


,(v1Si,vtrabajamos con ,multigrafos no debemos denotar los ejes como (vi,vj), pues puede
ocurrir que con esta notación se encuentren varios ejes. Tendremos que representarlo como el
Ciclo elemental
nombre del sieje.solo coinciden el primer y último vértice.

4.3. Caminos y circuitos

4.3 CAMINOS Y CIRCUÍTOS
Definición: Sea un grafo dirigido (V,A), llamamos camino a una secuencia de arcos
a1,a2...donde el vértice final de cada arco coincide con el inicial del siguiente:
Llamamos camino
final(a i)=origen(a(Sea
i+1) ∀i. un grafo dirigido (V,A)), a una secuencia de arcos a1,a2...donde el vértice
arco coincide con el inicial del siguiente: final(ai)=origen(ai+1) ∀i. 

final de cadaTipos:
• Camino simple. No se repite ningún arco.
Tipos: 
 • Camino elemental: No se repite ningún vértice.
* Camino simple. No se repite ningún arco. Camino elemental: No se repite ningún vértice. 

Definición: Circuito es un camino donde el primer vértice coincide con el final
Circuito es un camino donde el primer vértice coincide con el final

Jose Luis Lorente (preparador oposiciones secundaria www.joseluislorente.es) 5
 1) Si tenemos que Portodos
sólo paraloscualquier
siejemplo vértices
en un unidos
árbol
pareja porhomogéneo
de una cadena,
vértices existe entonces
(mismas
una cadena claramente
ramas estesiendo
que loscada
une vértice),
esta como
simple es
y e
TEMA 2. Fundamentos
grafo es conexo.anterior
Si el grafodelnonº y aplicaciones
es de
conexo de la teoria
por definiciónde grafos.
hay Diagramas en árbol
elemental. Demostración:
0 a 100, en donde a dos
cadavértices
vérticequele nos se 10
salen pueden
ramas (tantos como cifr
unir al haber 2 o más componentes de grafo disjuntas, por tanto no habrá cadena que los una.

 posibilidades disminuyen
1) Si tenemos de forma
que todos logarítmica
los vértices unidos enporbase10:
una cadena, entonces claramente este
2) Elemental: si en la cadena
grafo se repite
es conexo. Si el un vértice
grafo no eseliminamos
conexo porel definición
ciclo que empieza
hay dos yvértices
acaba que nos se pueden
1.
en este vértice. Así conseguimos Inicialmente tenemos 1000 posibilidades (del 0 al 999)
unir al haberla2 cadena elemental.
o más componentes• Simple: de egrafo
er2,e4disjuntas, por tanto no habrá cadena que los una.
1,e
2. Después del primer paso(1 nivel), al elegir la centena tenemos 100 posibilid
• Elemental: e ,e ,
1 2

 3) Simple: de igual forma siDespués
no es simple
2)3.Elemental: dellaessegundo
si en porquese
cadena hay un (2º
repite
paso
• Circuito:
bucle
e1,e2un
que podemos
;vértice
,e5nivel),
eliminar
eliminamos
e2,e4; al eelegir
3,e4.
y laque
el ciclo
la decena empieza10y acaba
tenemos posibilid
cadena que nos queda es simple.
en este
4. vértice. Así conseguimos
Después del 4º paso(3 er
la cadena elemental.
nivel),al elegir la unidad tenemos el numero buscado
Ejemplo: 3) Simple:un de igual forma si
Mediante diagrama denoárbol
es simple es porque
hemos hayal
llegado unnúmero
bucle queentre
podemos
0 yeliminar
999 eny latres
4.3. Caracterización grafos
cadena queconexos. Grafos
nos queda orientados fuertemente conexos.
es simple.
disminuyendo
Podemos caracterizar 2 logarítmicamente
1 los grafos las posibilidades:
3 mediante las cadenas:
conexos 1-2!e paso=log
1 grafo es conexo
Un si y 10(posibilidades).
e1 DE Ejemplo:
e2 existe unaCONEXOS 1-3!e
sólo si para cualquier pareja
4.4 CARACTERIZACIÓN de vértices
GRAFOS
Si codificáramos
cadena que
la información en Y1,eFUERTEMENTE
los une siendo esta simple y
código binario, el CONEXOS
2
proceso será semejante só
elemental. Demostración: e3 1-4!e1,e4
ahora el número deunidos 1
posibilidades2 3
desciende 1-2!e1
logarímicamente pero en base 2.
Un grafo es1) conexo
Si tenemos que todos
si y sólolossivértices
para cualquier 2-3!e
por una cadena,
pareja entonces
de
2 claramente
vértices este
existe una cadena que los une
e 1
grafo es conexo. Si el grafo no es4conexo por definición e
hay dos 1-3!e
2 vértices que nos se pueden 1 2 ,e
2-4!e 3
siendo esta2simple
unir al haber y elemental.
o más componentes Demostración:
de grafo e3 3-4!e
disjuntas, por tanto ,ecadena que los1-4!e
no habrá una. 1,e4
2 3
En grafos 2)dirigidos
Elemental: sila 1000definición
en nueva
la cadena 1000
se repite no eliminamos
un vértice válida pues
el ciclopueden sery2-3!e
que empieza conexos
acaba 2 3 3camino
y no haber
posibilidades

Eneste
grafos dirigidos la nueva 4 pues pueden ser conexos 2-4!e3y no haber
en
entre vértice.
dos Así conseguimos
vértices (debido aldefinición
la cadena no válida
elemental.
sentido)

log(pos)
camino3)entre
Simple:dos vértices
de igual forma(debido al sentido)
si no es simple
3-4!e ,e
es porque hay un bucle que podemos eliminar y la 2 3 2 2
500
cadena que nos queda es simple.
Ejemplo: En grafos dirigidos la es conexo
nueva y 3 no senopuede
definición válidaunir conpueden
pues 1, ni conser
2. conexos y no haber
Ejemplo:
1 2 3 1
camino entre dos vértices (debido al sentido)
Definición: un grafo1dirigido2 es 3fuertemente 100 conexo
1-2!e1 si hay algún camino que une todos sus
e 0
Ejemplo:
e 1-3!e
10 1
es conexo y 3 no se puede unir0 con 1, Este
ni con 2.
un grafo dirigido
vértices. es fuertemente
Este concepto interés
1 para
2 conexo
saber si ensiuna
hay 1,e2 todos
algún
ciudad camino que une
sus rincones estántodos susyavértices.
unidos,
e 0 11 1-4!e 2 1,e4 2 3 3 4 0
que hay
concepto callespara
interés con sentido si en3 una
único.
saberDefinición: ciudad todos
un grafo dirigido
sus rincones están unidos, ya que hay calles
es2 fuertemente conexo si hay algún camino que une todos sus
2-3!e
con 1
sentido único. 4 2-4!e
Pasos
Ejemplo: vértices. Este concepto interés para
3 saber si en una ciudad todos sus rincones están unidos, ya
3-4!e2,e3
que hay calles con sentido único.
En grafos dirigidos la nueva definición no válida pues pueden ser conexos y no haber
camino entre dos vértices Ejemplo:
En (debido
árboles no homogéneos, donde cada vértice
al sentido) no tiene el mismo nº de
5. Diagrama de árbol.
Ejemplo:descendientes, la gráfica no es
es conexo y 3 tan
no sesimple
puede unirpues
con 1, el nº2.de posibilidades desciende de dif
ni con
Un caso especial en1 los 2grafos 3son las estructuras denominados diagramas de árbol,
forma según el camino elegido. Pero en todo caso el decrecimiento Posibilidades vs pa
Definición: un grafovez
introducir por primera 5. dirigido
grande.
es fuertemente
Diagrama
en los de de
trabajos conexo
árbol. si hay
Kirchoff algún camino
(1847) queeléctricas.
de redes une todos sus
vértices. Este concepto interés para saber si en una ciudad todos sus rincones están unidos, ya
Definición:
5. MATRICES Un
conárbol
ASOCIADAS
que hay calles esúnico.
sentidoUn un grafo
A UN
caso conexo
GRAFO
especial sin los
en ciclos.
grafos son las estructuras denominados diagramas de árbol,
6. introducir
Ejemplo:
Definición: BosqueMatrices
es un grafo asociadas
por no
primera vezsin
conexo a trabajos
enciclo
los un grafo.
(unión de Kirchoff
varios (1847) de redes eléctricas.
árboles).
Dado un grafo (V,E) llamamos matriz de adyacentes a la matriz M∈Mnxn(N) donde n son los
Definición:Dado
Definición: Un árbol
un es un grafo
grafo (V,E) conexo sin ciclos.
llamamos matriz de adyacentes6 a la matriz M∈Mnxn
vértices
Josede VLorente
Luis y definida como: oposiciones
(preparador secundaria www.joseluislorente.es)
5. Diagrama de árbol.
donde n son los vértices
Definición: Bosque esdeunVgrafo
y definida como:
no conexo sin ciclo (unión varios árboles).
Un caso especial en los grafos son las estructuras denominados diagramas de árbol,
Jose
introducir por primera vezLuis : 1(preparador
Lorente
en los trabajos si arco
de Kirchoff (1847) ∈ Eeléctricas.
(oposiciones
i, dej )redes (secundaria
unidos ) www.joseluislorente.es) 6
mij = 9
Definición: Un árbol es un grafo 8
conexo ciclos. (i , j ) ∉ E ( no unidos )
0 sisinarco
Definición: Bosque es un grafo no conexo sin ciclo (unión varios árboles).
La matriz en grafos no orientados es simétrica, pues todo par de vértices (i,j) unidos
Jose Luis Lorente (preparador oposiciones secundaria www.joseluislorente.es)
6
dos sentidos.
Propiedades: En grafos no orientados la matriz es simétrica, pues todo par de vértices (i,j) unidos
en los dos sentidos. EnEn grafos orientadosla la
grafos orientados definición
definición dematriz
de la la matriz es la misma,
de adyacente pero nopero
es la misma, es ahora
simétrica. En el caso de p-grafos hay vértices que pueden estar unidos por p arcos, luego los
simétrica.
valores de mij van de 0 a p.

Jose Luis
Teorema: Si en la matriz M Lorente
del grafo(preparador
la elevamosoposiciones
al cuadradosecundaria www.joseluislorente.es)
tenemos una matriz, que nos indica
el número de cadenas con 2 ejes que unen dos vértices. Si lo elevamos al cubo la matriz resultado
nos indica el número de cadenas con 3 ejes que unen cada par de vértices. Así Mk nos informa del
número de cadenas con k ejes que unen cada par de vértices. Demostración
6. GRAFOS EULERIANOS Y PUENTES DE KÖNIGSBERG

6.1 PUENTE DE KÖNIGSBERG, TEOREMA DE EULER

En el siglo XVIII Euler demostró la imposibilidad de recorrer los 7 puentes de su ciudad sin pasar
dos veces por el mismo puente. A partir de aquí se crea un tipo de grafos, los Eulerianos. Euler
demostró el siguiente teorema

Teorema: todo grafo es recorrible sin repetición de ninguno de sus arcos, si el numero de vértices
impares (llegan un no impar de ejes) no es mayor que 2, es decir que no sean 4, 6,8...(ya que como
vimos en un teorema anterior, hay un numero par de vértices impares) (Demostración)

6.2 GRAFOS EULERIANOS Y SEMIEULERIANOS

Cola es una secuencia de aristas V0, V1,....,Vn-1, Vn, en la que todas las aristas son
diferentes. Si los vértices final e inicial coinciden, se dice que es una cola cerrada.

grafo euleriano a un grafo conexo G que tiene una cola cerrada que incluye todas las
aristas de G

grafo semieuleriano si la cola no es cerrada.



Teorema de Euler: (Demostración)

1) Un grafo es euleriano si y solo si cada vértice es de grado par.

2) Un grafo es semieuleriano si y solo si tiene dos vértices impares

7. GRAFO HAMILTONIANO

En el año 1859 el matemático Hamilton puso en circulación un rompecabezas basado en dodecaedro regular
(sólido formado por 12 pentágonos iguales). El juego consistía en ver si se era capaz de recorrer los 20
vértices sin repetir ninguno, salvo el inicial y el final que eran los mismos, moviéndose por las aristas. El
juego tenia solución, y había varios ciclos que pasaban por todos los vértices una sola vez salvo el primero y
el ultimo. Otro juego similar propuesto por Hamilton era el de recorrer todas las casillas del ajedrez con un
caballo sin repetir ninguna. En este caso los vértices serian las casillas del ajedrez y las aristas todos los
posibles movimientos del caballo. Los dos problemas se pueden plantear a partir de la definición de grafo
hamiltoniano.

Se denomina grafo hamiltoniano a todo aquel en el que existe un camino cerrado que contiene
todos los vértices una sola vez (no tiene por quÉ contener todas las aristas ).

semihalmintoniano. Un grafo que posea una trayectoria que pase a través de cada vértice.

Propiedades:

1) Los grafos hamiltonianos deben ser conexos.

 semihalmintoniano.
Es evidente que al igual que ocurre con los Eulerianos, los grafos hamiltonianos deben ser
2) Sin embargo no se Sin
conexos. ha embargo
conseguido una
no se hapropiedad
conseguidosencilla para caracterizar
una propiedad los
sencilla para grafos los grafos
caracterizar
hamiltonianos como ocurría
hamiltonianos comoen lo eulerianos.
ocurría en lo eulerianos.

3) Sin embargo
Puede comprobarse puede
que hay comprobarse
grafos eulerianosque
quehay
nografos eulerianos queynoviceversa.
son hamiltonianos son hamiltonianos y
viceversa.

9. Conclusiones
8. DIAGRAMAS DE ÁRBOL
Los grafos no se estudian como tal en secundaria ni bachillerato, si bien los diagramas de
árbol
Un caso especial en se
losutilizan
grafosen sonellas
estudio de la probabilidad.
estructuras denominados Losdiagramas
diagramasdepueden
árbol,ser una herramienta
introducir por
útil para utilizar con alumnos de altas capacidades
primera vez en los trabajos de Kirchoff (1847) de redes eléctricas. como actividades complementarias.

Un árbol es un grafo conexo sin ciclos.


Un Bosque es un grafo no conexo sin ciclo (unión varios árboles).

Otra forma: Un Bosque es un grafo que no posee ningún circuito y Árbol es un bosque conexo

Jose Luis Lorente (preparador oposiciones secundaria www.joseluislorente.es) 11

Teorema: (Demost)
9. APLICACIONES DE LOS GRAFOS

Los grafos pueden ser vistos como un modelo matemático, un material de base para
resolver problemas, obtención de regularidades, etc. Son utilizados en divisibilidad,
técnicas de recuento y combinatoria, probabilidad compuesta, etc.
A nivel interdisciplinar encontramos estructuras de grafos en diversas áreas tanto
científicas como las humanísticas. Por ejemplo en química en la representación de
hidrocarburos, etc. En física en las redes eléctricas. LAs estructuras lógicas de los
programas de ordenadores, en lógica informática, etc. Todo lo que sean esquemas,
pueden interpretarse como grafos.

Una de las aplicaciones más conocidas de los grafos es la del coloreo, es muy usada
cuando hablamos de pintar mapas.
El objetivo es colorear los vértices de un grafo de tal manera que no existan
dos vértices adyacentes del mismo color, ademas de que tenemos que usar el menor
numero de colores posibles. El algoritmo de coloración dice que basta solo de 4 colores
para pintar cualquier mapa; este algoritmo es llamado el "Teorema de los 4 Colores".
Para aplicar este algoritmo necesitamos saber el grado de cada vértice, es decir, conocer
el numero de vértices adyacentes.

El teorema dice que se deben de disponer de 4 colores, se empieza por el vértice que
tenga el mayor grado y se van pintando en orden descendente.