Grafos

CAPÍTULO

1

Grafos

E

ste capítulo es una introducción a la teoría de grafos. Los grafos son estructuras discretas compuestas por puntos (llamados vértices) y líneas (llamadas aristas) que conectan algunos pares de esos puntos. Son una abstracción útil para modelar diversas situaciones reales como por ejemplo: redes de computadoras, redes telefónicas o eléctricas, circuitos eléctricos,sistemas de carreteras, sistemas de transporte y distribución de mercancías y sistemas organizacionales. Hay muchos libros dedicados por entero a esta disciplina, que el lector interesado puede consultar. Entre ellos cabe destacar los clásicos [H2, B2], y entre los más modernos [B2, D1]. En español es muy recomendable el de José Rodríguez [R6].

1.1. Deniciones y conceptos básicos
1.1.1.Grafos simples
conjunto nito no vacío de elementos llamados vértices y E es un conjunto de pares no ordenados de elementos distintos de V llamados aristas. Por razones técnicas se supondrá que V ∩ E = ∅. Si e = {u, v} es una arista entonces se dice que los vértices u y v son los

Denición 1.1.1. Un grafo simple es un par G = (V, E) donde V es un

2

Capítulo 1. Grafos

extremos de e. Unvértice y una arista son incidentes si el vértice es uno de los extremos de la arista. Dos vértices u y v son adyacentes si {u, v} es una arista. El orden de un grafo G = (V, E) es el número de vértices |V |.
Lamentablemente en teoría de grafos no hay una terminología uniforme y aceptada por todos. Casi puede decirse que cada autor tiene su propia terminología, y por eso la mayoría de las obras sobregrafos comienzan deniendo los conceptos que se van a utilizar. En particular, los vértices de un grafo también son llamados nodos o puntos y las aristas líneas, arcos o ejes. Un grafo se representa por medio de puntos o pequeños círculos, que designan vértices, y líneas que los unen, que representan las aristas. Para simplicar la notación frecuentemente designaremos una arista {u, v}simplemente como uv .

Ejemplo 1.1.2. Sea V = {a, b, c, d, e} y E = {ab, bd, be, de}. Entonces (V, E) es un grafo con cinco vértices (a, b, c, d y e) y cuatro aristas (ab, bd, be y de). La gura 1.1 es su representación gráca:
a b

d c e

Figura 1.1: Grafo simple.

Denición 1.1.3. El grado de un vértice v de un grafo es el número g(v)
de aristas incidentes con él. Si g(v) = 0 se dice que v es unvértice aislado. En el grafo del ejemplo anterior se tiene g(a) = 1, g(b) = 3, g(d) = g(e) = 2 y g(c) = 0 (c es un vértice aislado). La sucesión de grados de un grafo se obtiene ordenando en forma no decreciente los grados de todos los vértices. En el ejemplo anterior la sucesión de grados es 0, 1, 2, 2, 3.

Teorema 1.1.4 (Euler). En todo grafo G = (V, E) se cumple
g(v) = 2|E|.
v∈V

1.1.Deniciones y conceptos básicos

3

Demostración. Las aristas se pueden contar viendo cuántas son incidentes con cada vértice y sumando todos los números obtenidos. Pero así cada arista resulta contada dos veces, una por cada uno de sus extremos.

Corolario 1.1.5. En todo grafo G = (V, E) el número de vértices de grado
impar es par.

Denición 1.1.6. Dos grafos G = (V, E) y G = (V , E )son isomorfos si

existe una biyección f : V → V que preserva la relación de adyacencia, es decir tal que

{u, v} ∈ E

si y sólo si {f (u), f (v)} ∈ E .

Para indicar que G y G son isomorfos se escribe G ≈ G .

Ejemplo 1.1.7. Los dos grafos representados en la gura 1.2 son isomorfos, ya que la función f que lleva a en a , b en b , c en c y d en d es una biyección y preserva la adyacencia.a b b’

c

d

a’

c’

d’

Figura 1.2: Grafos isomorfos. Dos grafos isomorfos deben tener el mismo número de vértices. Más aún todas las propiedades que se deriven de la relación de adyacencia deben ser idénticas en ambos, en particular deben tener el mismo número de aristas, el mismo número de vértices aislados y la misma sucesión de grados. Para los nes de la teoría de grafos,...