Grafos

G1

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 el conjuntode 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 el lado 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 y como vérticeterminal 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 o lados. Ejercicio 1 Muestreque 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 multigrafo G(V, E) consta de un conjunto V devertices, 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 consigo mismo). Usamos en este caso, pseudografos que sonmá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 se entiende como un grafo dirigido. Definición 4 Un grafodirigido 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 oparalelas 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 uy 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...