grafos

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 el conjunto de vértices del
grafo G y por E(G) elconjunto 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
el lado es un lazo (loop) o bucle . Cuando existenlados 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 y como vértice terminal a v.
A continuacióndamos 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 o lados.
Ejercicio 1 Muestre que si G essimple, 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 multigrafo 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, u 6= 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 consigo mismo). Usamos en este caso, pseudografos que son más
generales quelos 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 se entiende como un grafo dirigido.
Definición 4 Un grafo dirigido odigrafo 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 oparalelas si f(e1) =
f(e2).
b
b
b b
b
b
b b
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
losvé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 grafo simple, muestre que ¢ ≤ º − 1 donde º es el
número de vértices de G.
En un...