grafos

Matem´
atica Discreta
TEORIA DE GRAFOS

` Claverol
Merce
´
Ester Simo
´
Marisa Zaragoza

Departamento Matem´atica Aplicada IV
EPSEVG - UPC

´Indice general
1. Grafos: Definiciones B´
asicas
1.1. Introducci´on . . . . . . . . . .
1.2. Definiciones b´asicas . . . . . .
1.2.1. Grafos Simples . . . .
1.2.2. Grafos no tan Simples
1.3. Clases Especiales de Grafos .
1.3.1.Aplicaci´on . . . . . . .
1.4. Representando Grafos . . . .
1.5. Subgrafos . . . . . . . . . . .
1.6. Propiedades . . . . . . . . . .
1.6.1. Grado de un v´ertice . .
1.6.2. Isomorfismo de grafos .

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
..
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

3
3
4
4
5
8
11
12
14
17
17
19

2. Grafos: Caminos y Conexi´
on
2.1. Caminos . . . . . . . . . . . . . . . . . .
2.2. Grafos Conexos. . . . . . . . . . . . . .
2.3. Conectividad . . . . . . . . . . . . . . .
2.3.1. Aristo-Conectividad . . . . . . .
2.3.2. V´ertice-Conectividad . . . . . . .
2.4. Circuitos Eulerianos . . . . . . . . . . .
2.4.1. Circuitos y Cadenas de Euler . .
2.5. Ciclos Hamiltonianos . . . . . . . . . . .
2.5.1. Ciclos y Caminos Hamiltonianos .

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
..

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

23
23
26
28
29
30
33
33
38
39

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
..

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

´
3. Grafos: Arboles
43
´
3.1. Arboles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
´
3.2. Arboles
Generadores . . . . . . . . . . . . . . . . . . . . . . . 46
3.3. B´
usqueda en ´arboles . . . . . . . . . . . . . . . . . . . . . . . 49
i

1
3.3.1. B´usqueda en Profundidad . . . . .
3.3.2. B´
usqueda en Anchura . . . . . . .
´
3.4. El Problema del Arbol
Generador M´ınimo
´
3.5. Arboles
con ra´ız . . . . . . . . . . . . . . .
´
3.5.1. Arboles
de decisi´on . . . . . . . . .

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
..

.
.
.
.
.

49
52
54
61
63

2

Cap´ıtulo 1
Grafos: Definiciones B´
asicas
1.1.

Introducci´
on

En este cap´ıtulo introducimos el concepto de grafo. Un grafo es una estructura matem´atica que consta de v´ertices y aristas que conectan estos v´ertices.
Estas estructuras se utilizan para resolver problemas en muchos campos.
Por ejemplo, se pueden utilizar paradeterminar si un circuito se puede implementar de forma plana, para distinguir entre dos componentes qu´ımicos
con la misma f´ormula molecular pero diferente estructura, etc. Veamos otras
posibles aplicaciones de los grafos.
Planificaci´
on de proyectos
Una de las primeras aplicaciones por ordenador de los grafos estaba relacionada con la planificaci´on de proyectos. Un grafo con aristas dirigidases
una forma natural de describir, representar y analizar proyectos complejos
que consten de muchas actividades relacionadas entre s´ı.
Sistemas de tr´
afico
Una herramienta de uso frecuente por parte de quienes hacen dise˜
nos
urban´ısticos y de transportes es la simulaci´on por ordenador de sistemas de
tr´afico. Los sistemas que se modelan van desde las redes de tr´afico nacionales,
a...