Grafos

1

Semestre A2005

Teoría

Introducción a la Teoría de Grafos

1.

Grafos. Conceptos fundamentales

Un grafo G es un par G = (V, E ), donde V es un conjunto finito (vértices,
nodos) y E es un multiconjunto de pares no ordenados de vértices, denotados
por {x, y }, que se denominan lados, aristas, etc. En este caso decimos que x
y y son extremos de {x, y }. Denotamos V (G) por elconjunto de vértices del
grafo G y por E (G) el conjunto de lados del grafo G. Además ν (G) y ε(G)
denotan el número de vértices y el número de aristas de G respectivamente.
Puesto que E es un multiconjunto es posible que existen pares repetidos,
en este caso G tiene lados múltiples. También es posible que algún par no
ordenado de E tenga el mismo vértice repetido, en este caso decimos que
ellado es un lazo (loop) o bucle . Cuando existen lados múltiples y/o lazos
decimos que G es un multigrafo. Si no hay lados múltiples ni lazos decimos
que es un grafo simple. Un digrafo G es un par G = (V, E ) donde V es un
conjunto de vértices y E es un multiconjunto de pares ordenados. Los lados
se denotan por pares ordenados, (u, v ) denota el lado dirigido que tiene como
vértice inicial a u ycomo vértice terminal a v .
A continuación damos unas definiciones que provienen del libro de Matemáticas Discreta y sus aplicaciones de Rosen [2]. Se deja al lector comparar las
diferentes definiciones.
Definición 1 Un grafo simple G(V, E ) consta de V , un conjunto no vacío de vértices, y de E , un conjunto de pares no ordenados de elementos
distintos de V . A esos pares se les llama aristas olados.
Ejercicio 1 Muestre que si G es simple, entonces ε ≤

ν
2

.

En algunos casos lo grafos simples no bastan para modelar ciertas situaciones
en las cuales se requiere de la existencia de múltiples aristas entre par de
vértices. En este caso no es suficiente definir las aristas como par de vértices;
la definición de multigrafo es un poco más complicada.
Definición 2 Un multigrafoG(V, E ) consta de un conjunto V de vertices,
un conjunto E de aristas y una función f de E en {{u, v }|u, v ∈ V, u = v }. Se
dice que las aristas e1 , e2 son aristas múltiples o paralelas si f (e1 ) = f (e2 ).
Matemáticas Discreta

Prof. José Luis Chacón

Grafos

2

Semestre A2005

Teoría

Los multigrafos definidos no admiten bucles o lazos (aristas que conectan
un vértice consigomismo). Usamos en este caso, pseudografos que son más
generales que los multigrafos.
Definición 3 Un pseudografo G(V, E ) consta de un conjunto V de vertices, un conjunto E de aristas y una función f de E en {{u, v }|u, v ∈ V }. Se
dice que una arista e es un bucle o lazo si f (e) = {u, u} = {u} para algún
u∈V.
La diferencia entre grafo y digrafo es que el último tiene los lados dirigidos
y seentiende como un grafo dirigido.
Definición 4 Un grafo dirigido o digrafo G = (V, E ) consta de un conjunto V de vertices, un conjunto E de aristas, que son pares ordenados de
elementos de V .
Definimos los multigrafos dirigidos de la siguiente manera
Definición 5 Un multigrafo dirigido G(V, E ) consta de un conjunto V de
vertices, un conjunto E de aristas y una función f de E en {(u, v )|u, v ∈V }.
Se dice que las aristas e1 , e2 son aristas múltiples o paralelas si f (e1 ) =
f (e2 ).

Figura 1: Ejemplos de grafo y multigrafo dirigido.

1.1.

Adyacencia de Vértices, Incidencia de Aristas y
Grado de los Vértices

Dos vertices u, v de un grafo G = (V, E ) se dicen adyacentes si {u, v } ∈
E , asimismo dos aristas son adyacentes si tienen un mismo vértice como
extremo;análogamente si e = {u, v } decimos que el lado e es incidente a
los vértices u y v . El grado de un vértice es el número de lados incidentes a
él. El grado de un vértice u se denota gr(u). Denotamos con δ (G) y ∆(G) el
mínimo y el máximo grado de los vértices de G respectivamente.
Matemáticas Discreta

Prof. José Luis Chacón

Grafos

3

Semestre A2005

Teoría

Ejercicio 2 Si G es un...