Fundamentos y aplicaciones de la teoría de grafos, diagrama en árbol

OPOSICIONES SECUNDARIA MATEMÁTICAS

TEMA 2

C
C
TEMA 2
FUNDAMENTOS Y APLICACIONES DE LA TEORÍA DE
GRAFOS. DIAGRAMA EN ÁRBOL.
C
C
Página 1 de 15TEMA 2
OPOSICIONES SECUNDARIA MATEMÁTICAS

1. INTRODUCCIÓN

1.1. JUSTIFICACIÓN DE LA ELECCIÓN DEL TEMA

1.2. RESEÑA HISTÓRICA

2. CONCEPTOS FUNDAMENTALES DE LA TEORÍA DE GRAFOS

2.1. TIPOS DE GRAFOS

2.2. REPRESENTACIÓN DE GRAFOS

2.3. ISOMORFISMO DE GRAFOS

2.4. SUBGRAFOS

3. CAMINOS Y CICLOS. CONEXIÓN

3.1. GRAFOS EULERIANOS

3.2. GRAFOS HAMILTONIANOS

4. GRAFOS COMPLETOS. GRAFOS BIPARTITOS COMPLETOS. GRAFOS PLANOS

5. ÁRBOLES. DIAGRAMAS EN ÁRBOL

5.1. ÁRBOLES ABARCADORES

5.2. ÁRBOLES CON RAÍZ

6. APLICACIONES DE LA TEORÍA DE GRAFOS

6.1. INGENIERÍAS

6.2. TEORÍA DE JUEGOS

6.3. VARIOS

7. CONCLUSIÓN

8. BIBLIOGRAFÍA

Página 2 de 15OPOSICIONES SECUNDARIA MATEMÁTICAS
TEMA 2

1. INTRODUCCIÓN

1.1. JUSTIFICACIÓN DE LA ELECCIÓN DEL TEMA

Los grafos son modelos matemáticos de numerosas situaciones reales. De forma general, puede
decirse que los grafos se utilizan para representar las relaciones existentes entre los elementos de un
conjunto. Por lo tanto, podemos decir que los grafos son un artificio matemático que puede simplificar
y resolver numerosas situaciones o problemas reales, desde los problemas relacionados con tráfico
(aéreo, por carretera, de mercancías, etc.) o diseño de redes (de transporte, en sistemas eléctricos,
etc.) hasta aplicaciones en ciencias tan dispares como la química, la genética, la informática, la
bibliotecomanía o la arqueología.
Por tanto, es evidente que los grafos constituyen hoy en día una herramienta matemática
indispensable en diversos campos a parte de la ciencia y por ello, es imprescindible conocer las ideas
básicas que sustentan la denominada teoría de grafos, las cuales introduciremos a lo largo del tema.

1.2. RESEÑA HISTÓRICA

Leonhard Euler (s. XVIII) fue un matemático de gran talento que enriqueció las matemáticas, tal y
como hace referencia en el libro de Carl B. Boyer: Historia de la matemática, en cada una de sus
ramas. Uno de sus resultados más famosos fue su solución al problema de los "puentes de
Königsberg".
La ciudad de Königsberg estaba dividida en cuatro partes por el río Pregel, con siete puentes. Muchos
habitantes de la época se plantearon el reto de encontrar una ruta por la ciudad que recorriera los
siete puentes, cruzando cada uno de ellos una única vez y volviendo al punto de partida.
Euler dio una demostración matemática de la imposibilidad de realizar dicho trayecto en las
condiciones que se pretendían, y hoy en día, esa solución se considera como el origen de la teoría de
grafos. A partir de entonces, muchos matemáticos han realizado contribuciones, entre los siglos XVIII
y XIX se pueden citar a Cauchy, Vandermonde, Hamilton, Cayley y Kruskal.
4
1
6
5
2
3
7

2. CONCEPTOS FUNDAMENTALES DE LA TEORÍA DE GRAFOS

De forma informal, podríamos comenzar definiendo un grafo del siguiente modo:
Un grafo es una colección de vértices y aristas que unen dichos vértices.
De un modo más formal, definimos grafo del siguiente modo:
Página 3 de 15OPOSICIONES SECUNDARIA MATEMÁTICAS
TEMA 2

Definición de Grafo

Un grafo es un par ordenado G = (V,A), donde V es un conjunto no vacío y a cuyos elementos se les
llama vértices, y A es un conjunto de pares de elementos de V a cuyos elementos se les llama aristas.

Definición de Elementos del Grafo

Sea G = (V,A) un grafo. Entonces:
1) Si a = (u, v) es una arista del grafo G, entonces los vértices u y v se llaman los extremos de
la arista a.
2) Si el vértice v E V es un extremo de la arista a E A, entonces se dice que v y a son incidentes.
3) Los vértices u, v E V se dicen adyacentes si existe una arista en el grafo G que une u y v.
4) Dos aristas se dicen incidentes si tiene un vértice en común.
5) Un punto del grafo que es extremo de alguna arista se llama nodo. En caso contrario, se llama
vértice aislado.
6) Cuando en una arista coinciden los vértices, u = v, la arista se denomina lazo.
Ejemplo:
a1
v1
v2
v4
a2
v3
a3
v1 y v2 son vértices adyacentes
a1 y a2 son aristas incidentes
a3 es un lazo
v4 es un vértice aislado
Nota: Dado el grafo G = (V,A), se denota por V (G) al conjunto de vértices y por A(G) al conjunto de
aristas de dicho grafo.

Definición de Grado de un Vértice

Sea G = (V,A) un grafo y v E V un vértice:
a) Llamamos grado de v (grad (v)) al número de aristas que inciden en v.
b) Un nodo se llama par si hay un número par de aristas que lo tiene como extremo. De forma
análoga se llamaría impar. En este cómputo, si la arista fuese un lazo entonces se cuenta dos
veces.
c) Se dice que v E V es terminal si gr(v) = 1. Además, un vértice aislado cumple que su grado
es nulo.

Teorema de la Suma de Grados

Si G = (V,A) es un grafo, entonces EvEv grad(v) = 2|A|.
Demostración
Según se considera cada arista a = (u, v) del grafo G, la arista suma 1 a grad(u) y a grad (v), luego
suma 2 a la suma de todos los grados. Así, 2|A| es el total de grad(v), Vv E V.

Teorema (Lema del apretón de manos)

El número de vértices de grado impar de un grafo es par o cero.
Página 4 de 15OPOSICIONES SECUNDARIA MATEMÁTICAS
TEMA 2

2.1. TIPOS DE GRAFOS

Definición de Grafo Simple

Un grafo simple es un grafo que verifica que para todo par de vértices existe a lo sumo una arista
que los une.
u
v
w

Definición de Multigrafo

Un multigrafo o grafo general es un grafo con varias aristas entre dos vértices.
u
v
w

Definición de Pseudografo

Un pseudografo es un grafo en el cual aparecen lazos.
u
w
v

Definición de Grafo Orientado

Un grafo orientado, dirigido o dígrafo es un grafo donde a cada arista se le asigna un orden de sus
extremos. El orden se indica en el dibujo con una flecha. Se llama origen al primer vértice de una
arista y final al segundo.
v1
v2
v3
VI = {v2, V2, 13}
A1 = {v1V2, 1203, 13V1}

Definición de Grafo Nulo

Se llama grafo nulo a un grafo donde el conjunto de aristas es vacío. El grafo nulo de n vértices se
designa por Nn·
u
N3
v
w

Definición de Grafo Regular

Un grafo es regular si todos sus vértices tienen el mismo grado. Si dicho grado es k, entonces el
grafo se llama k-regular.
v1
v2
v2
v1
Ejemplo:
v8
v7
v5
v6
NO REGULAR
v4
v4
v3
v3
3-REGULAR
grad(v1) # grad(v2)
Página 5 de 15OPOSICIONES SECUNDARIA MATEMÁTICAS
TEMA 2

Definición de Ciclo

Se denomina ciclo a todo grafo 2-regular. Los ciclos se representan por Cn, siendo n el número de
vértices.
Ejemplo:
C4
C5

2.2. REPRESENTACIÓN DE GRAFOS

Un grafo se puede representar de diferentes formas:

1. Definiendo por enumeración los conjuntos V y A de vértices y aristas del grafo
   respectivamente. Esta forma es muy poco operativa.
   Ejemplo:
   § V(G) = {a, b, c, d, e, f}
   (A(G) = {ab, ae, bd, cd, ed}
2. Gráficamente, mediante un diagrama en el que aparezca un punto por cada vértice y una
   línea entre dos vértices adyacentes. Esta es la forma usual de representar un grafo.
   Ejemplo:
   e
   f
   a
   C
   b
   d
3. Por su matriz de incidencia: es una matriz que tiene tantas filas como vértices y tantas
   columnas como aristas, cuyos elementos ajj vienen dados por:
   [1 si el vértice i y la arista j son incidentes
   0 en caso contrario
   Ejemplo:
   d
   C
   e
   f
   a
   b
   1
   0
   0
   1
   0
   0
   ae
   0
   1
   0
   1
   0
   1
   1
   0
   0
   0
   0 0
   0
   0/
   0
   0
   1
   1
   bd cd de
   0
4. Por su matriz de adyacencia: es una matriz cuadrada que tiene tantas filas y columnas como
   vértices, cuyos elementos dij vienen dados por:
   §1 si los vértices i y j son adyacentes
   0 en caso contrario
   aij = 1
   0 1
   0
   a
   b
   1
   Ejemplo:
   d
   0
   C
   0
   0
   1
   e
   0
   0
   1
   0
   b
   1
   0
   0
   1
   0
   0
   C
   0
   0
   d
   1
   1
   f
   0
   0
   0
   1
   0
   0
   1
   0
   0
   0.
   a
   0
   e
   0
   0
   0
   f
   Página 6 de 15
   0
   ab
   0

2.3. ISOMORFISMO DE GRAFOS

Definición de Isomorfismo

Diremos que dos grafos G = (V,A) y G' = (V',A') son isomorfos si existe una aplicación biyectiva
q: V -> V'. Es decir, la relación que relaciona biyectivamente pares de vértices de A con pares de
vértices de A', de modo que los vértices conectados por aristas siguen estándolo. A la aplicación o
se le denomina isomorfismo.
Ejemplo:
a
b
1
2
4
C
d
G
3
Gʹ

Teorema de Isomorfismo

Sean G = (V,A) y G' = (V',A') dos grafos y « un isomorfismo entre G y G'. Si u E V, entonces:
grad(u) = grad((u)).
Observación
Dos grafos con distinto número de vértices no pueden ser isomorfos. Y el recíproco no es cierto, es
decir, grafos con igual número de vértices no tienen por qué ser isomorfos.

2.4. SUBGRAFOS

Definición de Subgrafo

Sea G = (V,A) un grafo. Un grafo G' = (V',A') se dice subgrafo de G si Ø # V'(G') ≤V(G) y
A'(G') ≤ A(G).
Observación
Los subgrafos se obtienen eliminando algunas aristas y vértices del grafo original, de modo que, si
eliminamos un vértice, hemos de eliminar todas las aristas que tienen tal vértice como extremo.
Ejemplo:
1
2
3
4
G
V(G) = {1,2,3,4}
(1,2), (2,3),
A(G) = (3,4), (4,1),
(1,3), (2,4)
1
2
V(G) = {1,2,3}
A(G) =
[(1,2), (2,3),Į
(3,1)

Definición de Grafo Complementario

Sea G = (V,A) un grafo. Se denomina grafo complementario de G y se representa por G, al grafo que
tiene el mismo conjunto de vértices y verifica que entre cada dos vértices existe una arista sí y sólo
sí dicha arista no existe en G.
Ejemplo:
1
2
3
4
G
1
2
3
4
G
3
G' (subgrafo de G)
Página 7 de 15OPOSICIONES SECUNDARIA MATEMÁTICAS
TEMA 2

3. CAMINOS Y CICLOS. CONEXIÓN.

Los grafos se usan con frecuencia para representar redes de transporte o de comunicación. En un
grafo que representa una de estas redes es importante conocer la existencia de caminos que recorran
todas las aristas o todos los vértices y que, en cierto modo, sean los más económicos.

Definición de Caminos y Ciclos

Sea G = (V,A) un grafo. Entonces:
a) Un camino en el grafo G es una sucesión en la que aparecen de forma alternada elementos
de V y elementos de A de la forma vo, ao, V1, a1, 12, a2, ... , Un, an Con vi E V(i = 0, ... , n) y aj €
A(j = 1, ... ,n).
A los vértices vo y Vn se les llaman extremos del camino, o vértices inicial y final
respectivamente. También se dice que el camino conecta vo con Un.
La longitud del camino es el número de aristas que contiene dicho camino.
El camino también puede expresarse mediante sus vértices de la siguiente manera: v0 -> v1 ->
12 > ... >> Vn-1 -> Un.
b) Un camino se dice cerrado si sus extremos coinciden: v0 = Vn (pero sí pueden repetirse algún
vértice).
c) Un camino se dice simple si en la sucesión de vértices no hay ninguno repetido, por lo tanto,
todas las aristas son distintas.
d) Un ciclo es un camino cerrado donde los únicos vértices que se repiten son el primer y el
último.
e) Un circuito es un camino cerrado que no repite aristas (pero sí puede repetir vértices).

Definición de Grafo Conexo

Un grafo G = (V,A) se dice conexo si para cada par de vértices u, v E V existe un camino cuyos
extremos son u y v. Si un grafo no es conexo, se dice disconexo.
Grafo conexo
Grafo disconexo

3.1. GRAFOS EULERIANOS

El nombre de este tipo de grafos proviene del matemático Leonhard Euler (s. XVIII) quién abordó
por primera vez el asunto de cómo debían caracterizarse los grafos para poder recorrerse de la
manera deseada tras desestimar el problema de los puentes de Königsberg.

Definición de Caminos y Circuitos Eulerianos

Sea G un grafo. Entonces:
a) Un camino euleriano es un camino que contiene todas las aristas del grafo G, apareciendo
cada una de ellas exactamente una vez (puede repetir vértices, pero no aristas).
b) Un circuito euleriano es un circuito que contiene todas las aristas de G.
c) Un grafo que admite un circuito euleriano se llama grafo euleriano.
Página 8 de 15