MATEMÁTICA DISCRETA

Tema GRAFOS

Introducción

1
 ÍNDICE
1. INTRODUCCIÓN A LOS GRAFOS.
– Euler y los puentes de Könisberg.
– Definiciones y terminología.
• Grafo, multigrafo, pseudografo, grafo dirigido y con peso, etc.
• Familias particulares de grafos.
• Subgrafos. Grado de un vértice. Teorema de Euler.
– Isomorfismo de grafos.
2. CONECTIVIDAD.
– Recorridos y caminos. – Árboles.
– Grafos conexos. – Árboles recubridores.
– Grafos eulerianos.
– Grafos hamiltonianos.
2
3. GRAFOS PONDERADOS.
– Árboles recubridores mínimos. Algoritmo de Kruskal.
– Caminos mínimos. Centro y mediana.
– Algoritmo de Dijkstra.

4. DIGRAFOS ACÍCLICOS. (RELACIONES BINARIAS)

– Preorden. Cierres. Diagramas de Hasse.

– Orden topológico.

– Planificación de tareas.

3
 BIBLIOGRAFÍA
• [1] MATEMÁTICA DISCRETA, (2ª edición), "Notas de la
asignatura" editadas por el Servicio de Publicaciones de la E.U.
de Informática.

• [2] GRIMALDI, R.P.: “Matemática Discreta y Combinatoria”.

Addison Wesley, 1997.

• [4] ROSEN, K.H.: “Matemática Discreta y sus aplicaciones”.

McGraw-Hill, 2004.

• [1-Complementaria] BRADLEY, J.: “Introduction to Discrete

Mathematics”. Addison Wesley, 1988.
4
 Introducción a los grafos.
• Euler y los puentes de Könisberg.
– Formulación del problema.
– Modelización.
– Generalización.

• Utilidad de los grafos.

– Modelización y resolución de problemas.
– Representación de la información.
– Estructura de datos.

• Aplicación de los grafos.

– Matemáticas.
– Informática.
– Otras ciencias: geografía, biología, ecología, economía, etc.
– Otras artes: música, lingüística, literatura, etc.
5
 Relaciones del tema con otras asignaturas

• Con la mayoría de las de matemáticas

– Matemática Discreta.
• Árboles estructurales, tableaux, árboles de dependencia.
– Lógica.

• Con bastantes de informática

– Estructuras de Datos I y II.
– Algorítmica.
– Ingeniería del Software.
– Inteligencia Artificial.

6
 Euler (1707-1783) y los puentes de Könisberg

Könisberg

Río Pregel Río Pregel

Könisberg

Modelización:
Con una estructura discreta, finita: un grafo.

7
 Inicio de la teoría de grafos
• Generalización:
– GRAFO: Conjunto de vértices y aristas.
– Recorrido euleriano.
– TEOREMA (de Euler): Dado un grafo conexo
es euleriano si y solo si todos los vértices tienen grado par.
– El problema de los puentes de Könisberg no tenía solución.

• Inicio de la teoría de grafos (1736)

– En muchos problemas de apariencia dispar, subyace esta
misma estructura discreta.

• Objetivo:
– Aprender a modelizar con grafos.
– Resolver problemas con grafos.
8
 Definiciones y terminología.
• Definición Intuitiva de grafo:
Un grafo es un conjunto de puntos, vértices o nodos,
unidos por líneas, aristas.

No hay restricciones para formar un grafo:

– Puede haber varias aristas entre dos vértices.
– El vértice de partida y el de llegada puede ser el mismo.
– Las aristas pueden o no llevar flechas.

9
Definición: Grafo Simple o Grafo Simple No Dirigido.
Un grafo (o grafo simple o grafo simple no dirigido) es un par G = (V,A)
dondeV es un conjunto finito no vacío y A es un conjunto de pares
NO ordenados {u,v} de elementos distintos de V.

• Los elementos de V se denominan vértices.

• Los elementos de A se denominan aristas.

Notación: {u,v} se escribe uv o bien vu, o bien u ady v.

• Si uv es una arista, uv∈A, se dice que:
– Los vértices u y v son ADYACENTES, en la arista uv.
– u y v son INCIDENTES con la arista uv.
– u y v son los EXTREMOS de uv.
– La arista uv es INCIDENTE con los vértices u y v.

– Dos aristas son ADYACENTES si tienen un extremo común.

10
 Ejemplos de grafos
a b a b

g
c f c
f

e d
G H e d
Nota: en un grafo simple NO hay aristas orientadas, ni bucles,
ni dos o más aristas entre un mismo par de vértices.

• Si sí se permiten aristas múltiples. • Si además se permiten bucles.

Multigrafo Pseudografo 11
Definición: Grafo (Simple) Dirigido.
• Un grafo dirigido (o grafo simple dirigido) es un par
G = (V,A) donde V es un conjunto finito no vacío y A es un
conjunto de pares ordenados de vértices distintos de V,
tal que si el par (u,v) ∈A entonces (u,v) ∉A .

• Si (u,v) ∈A es una arista dirigida, diremos que

u y v son sus vértices inicial y final.

• Ejemplos:
c a
a b

d
a b
c d b c
12
• Multigrafos dirigidos:

a b a b e

d c d c

• Pseudografos dirigidos:

a b a b
a

c d d c
b c
13
Definición: Digrafo.
• Un digrafo es un pseudografo dirigido donde se
permite a lo sumo un bucle por vértice y dos aristas entre dos
vértices distintos con la condición de que tengan orientaciones
opuestas.
• Con esta definición cada digrafo G = (V, A) se corresponde
con una única relación binaria A en V y recíprocamente.

• Ejemplo: V={ a, b, c, d } y consideremos la relación binaria R en V:

R={ (a,a), (a,b), (a,c), (b,a), (b,b), (c,c), (c,d), (d,b), (d,c), (d,d) }

entonces el digrafo G asociado tiene a V

como conjunto de vértices y las aristas

dirigidas son los pares de R: G = (V, R)

14