Teoria De Grafos

TEMA IV
TEORÍA DE GRAFOS
Poli Abascal Fuentes

TEMA IV Teor´a de grafos– p. 1/?
ı

TEMA IV
4. TEORÍA DE GRAFOS
4.1 GRAFOS
4.1.1 Introducción
4.1.2 Definiciones básicas
4.1.3 Caminos y recorridos
4.1.4 Subgrafos, complementos e isomorfismos de
grafos
4.1.5 Grafos conexos
4.1.6 Grado de un vértice
4.1.7 Recorridos y Circuitos Eulerianos
4.1.8 Caminos y Ciclos Hamiltoniano
4.1.9Grafos planos

TEMA IV Teor´a de grafos– p. 2/?
ı

TEMA IV
4.2 ÁRBOLES
4.2.1 Árboles no dirigidos
4.2.2 Grafos con coste: búsqueda de un árbol
generador minimal
4.2.3 Árboles dirigidos
4.3 REDES
4.3.1 Introducción
4.3.2 Modelos de redes
4.3.3 Un algoritmo de cálculo de flujo máximo
4.3.4 Teoría del emparejamiento

TEMA IV Teor´a de grafos– p. 3/?
ı

4. TEORÍA DE GRAFOSBibliograf´a
ı
Rosen K.H.,
Matemática discreta y aplicaciones,
Editorial McGraw-Hill
Johnsonbaugh, R.,
Matemáticas discretas,
Prentice Hall
Grassman, W.K. and Tremblay, J.P.,
Matemática discreta y Lógica,
Prentice Hall
Grimaldi, R.P.,
Matemáticas discretas y combinatoria,
Prentice Hall

TEMA IV Teor´a de grafos– p. 4/?
ı

4.1 Grafos
4.1.1 Introducci´ n
o
Salinas
e6

Grao

Praviae11

e2

Trubia

e1
e9

e12

e4

Oviedo
e13
e10
Posada

e8 Villaviciosa
Nava
e5

Luanco
e3

e7

Gijón

Figura 1: Grafo equivalente al Mapa de carreteras

TEMA IV Teor´a de grafos– p. 5/?
ı

4.1.2 Definiciones básicas
Definición 1 Sea V un conjunto finito no vacío a cuyos
elementos llamaremos vértices y sea E un conjunto de pares no
ordenados de V a cuyoselementos llamaremos aristas, al par
(V, E ) le llamaremos grafo no dirigido.
Si una arista e ∈ E está asociada a los vértices v y w
escribiremos e = {v, w}. Podría ocurrir que v = w.
Un vértice puede estar asociado a 0 aristas, pero toda arista une
uno o dos vértices.
Cuando dos vértices están asociados a una arista se dice que son
adyacentes, y a ellos se les llama extremos de la arista.TEMA IV Teor´a de grafos– p. 6/?
ı

4.1.2 Definiciones básicas
En el ejemplo anterior el conjunto de vértices sería
V = { Salinas, Luanco, Pravia, Gijón, Villaviciosa, Grado, Posada,
Nava, Trubia, Oviedo}
y el conjunto de aristas queda descrito a continuación:
e1 = {Salinas, Luanco}
e2 = {Salinas, P ravia}
e3 = {Gij on, Luanco}
´
´
e4 = {P ravia, Gij on}
e5 = {V illaviciosa, Gij on}´
e6 = {Grao, P ravia}

´
e7 = {P osada, Gij on}
e8 = {N ava, V illaviciosa}
e9 = {Grao, P osada}
e10 = {N ava, P osada}
e11 = {Grao, T rubia}
e12 = {T rubia, Oviedo}
e13 = {Oviedo, P osada}

TEMA IV Teor´a de grafos– p. 7/?
ı

4.1.2 Definiciones básicas
v1
e1
v2
e2

e3
v3

e4
v4

e5
e6

v5

La asignación de vértices a
aristas es la siguiente:
e1 = (v2 , v1 )
e2 =(v2 , v5 )

v6
e7

e3 = (v2 , v3 )

e4 = (v3 , v2 )
e5 = (v6 , v3 )
e6 = (v6 , v4 )
e7 = (v6 , v6 )

La arista e1 se asocia al par ordenado (v2 , v1 ) y se dice que v2 es el
origen y v1 el extremo.
La arista e7 se asocia al par ordenado (v6 , v6 ) y en este caso, el origen
y el extremo coinciden. Se llama lazo.
TEMA IV Teor´a de grafos– p. 8/?
ı

4.1.2 Definiciones básicasDefinición 2 Los grafos (dirigidos o no) que no tienen lazos ni más de
una arista adyacente al mismo par de vértices se llaman grafos simples
Definición 3 Un grafo completo, Kn , con n vértices es un grafo
simple no dirigido en el que existe una arista uniendo cada par de
vértices distintos.
Definición 4 Un grafo con n vértices y dirigido se dice grafo dirigido
completo cuando es simple y para cadapar de vértices u, v existe
exactamente una de las aristas (u, v ) ó (v, u). A dichos gráficos se les
∗
denota por Kn .

TEMA IV Teor´a de grafos– p. 9/?
ı

4.1.2 Definiciones básicas
Definición 5 Un grafo G = (V, E ) diremos que es un grafo bipartido
si se puede dividir el conjunto de vértices en dos subconjuntos
V = V1 ∪ V2 , tales que son disjuntos, V1 ∩ V2 = ∅, y cada arista de E...