Teoria de Grafos

Escuela de Ingeniería en Telemática
Curso de Teoría de Autómatas y Algoritmos
Prof: Ing. Alexander Vargas Céspedes, M.A.I.

TEORÍA DE GRAFOS
Definiciones y notaciones.
Los grafos son una estructura de datos no lineal y que tienen un gran número de aplicaciones. El
estudio de análisis de grafos ha interesado a los matemáticos durante siglos y representa una parte
importante de la teoríacombinatoria en matemáticas. Aunque la teoría de grafos es compleja y amplia
en este módulo se realizará una introducción a la teoría de grafos que permita la solución de algunos
problemas.

Un grafo G consiste en un conjunto V de vértices ( nodos ) y un conjunto E de aristas ( arcos o
lados ) tal que cada arista ‘e’ ∈ E se asocia con un par no ordenado de vértices. Si existe una arista
única‘e’ asociada con los vértices v y w se escribe e = ( v, w ) ó e = ( w, v ). El par ( v, w ) denota una
arista entre v y w en una gráfica no dirigida y no es un par ordenado.
Si una arista ‘e’ en una gráfica se asocia con el par de vértices v y w es incidente sobre v y w, y
se dice que v y w son incidentes sobre ‘e’ y son vértices adyacentes.

Si G es una gráfica con vértices V y aristas E, seescribe G = ( V, E ).

Ejemplo 1:
a
.

e1

e2 .
c
e5 .

e4

.
.
f

.

.

b

. e3
d

.
e6

G

.

e1 = ( a, b )

e5 = ( c, f )

Los vértices a y b así como los vértices c y f son adyacentes.
G consiste en el conjunto de vértices V = { a, b, c, d, f } y el conjunto de aristas E = { e1, e2, e3, e4, e5, e6 }.

Información tomada de: Johnsonbaugh, Richard.Matemáticas discretas. Sexta Edición. Pearson Prentice Hall. 2005

Página 1

Grado de un vértice.
El grado de un vértice está determinado por el número de aristas que tienen a ese vértice como
extremo.
Ejemplo 2:

.

.b

.

.

a

c.

.d

Los vértices a y b tienen grado 3 mientras que los vértices c y 2 grado 2.

.·e

Un vértice de grado = 0 es un vértice aislado, por ejemplo elvértice e.

.

.
.
Podemos comprobar que determinamos bien el grado de los vértices de una determinada gráfica
aplicando el teorema que indica: la suma de los grados de todos los vértices de una gráfica es igual al
doble del número de aristas de esa misma grafica.

Observe como la suma de los grados de todos los vértices de la gráfica del ejemplo 2 es igual a 10
( 3 + 3 + 2 + 2 + 0 ) yla cantidad de aristas de dicha gráfica es igual a 5.

Trayectorias y circuitos en una gráfica.
Ejemplo 3 :

.
.e
.4

3
e1

1.

.

e2

.

.
e5

.

5

.

3

2

e4

.

e6

e7

.

6
.

e8

.7
7
.

Trayectoria: es una sucesión de vértices adyacentes en donde ninguna arista se recorre más de una
vez, se inicia y finaliza en vértices distintos.
Enel ejemplo 3 podemos determinar como una trayectoria aquella que inicia en el vértice 1 y pasa por
los vértices 2, 3 y 4 para finalizar en el vértice 2. La denotamos así: ( 1, e 1, 2, e2, 3, e3, 4, e4, 2 ) o bien
solamente con sus vértices ( 1, 2, 3, 4, 2 ).
Circuito: es una trayectoria que inicia y termina en el mismo vértice. Para el ejemplo 3 podemos
denotar un circuito como ( 2, 3, 4, 2 ).Información tomada de: Johnsonbaugh, Richard. Matemáticas discretas. Sexta Edición. Pearson Prentice Hall. 2005

Página 2

Gráfica Conexa: una gráfica es conexa si existe una trayectoria de cualquier vértice a cualquier otro de
la gráfica.
a
b

.

.

.

.

.

.c
.

d

.

Gráfica Disconexa: una gráfica es disconexa cuando no existe trayectoria entre dos vértices de lamisma gráfica.

.

.b

a

.

.

.

d

.

.c
f.
.

.e

.

.

Observe que no existe trayectoria entre los vértices c y f.

Gráfica Discreta: una gráfica es discreta cuando no tiene aristas, también se le llama gráfica libre. Se
denota: Dn donde n es la cantidad de vértices y n ≥ 1. Esta es una gráfica disconexa y regular (todos los
vértices tienen el mismo...