Los grafos

Los grafos pueden ser considerados diagramas o dibujos, o formalmente como un par de

conjuntos.

Un grafo G se define como un conjunto E de pares no ordenados de elementos distintos

y otro conjunto de elementos V.

El conjunto V es el conjunto de vértices del grafo, se denota por V(G).

El conjunto E es el conjunto de aristas del grafo, se denota por E(G).

G=(V, E)

V={v1, v2,..., vn}

E={vivj, vn,vm,...}

Dos vértices vi, vj son adyacentes si son los extremos de una arista, es decir, si el par de

vértices V es un elemento de E.

#V es el número de vértices.

#E es el número de aristas.

Un grafo es finito si #V es finito.

Dibujar un grafo para resolver un problema es un reflejo muy común, que no precisa conocimientos matemáticos. Un grafo se parece a la figura siguiente, y consta de vértices y de aristas que reúnen algunos de ellos.

En la teoría de los grafos, sólo se queda lo esencial del dibujo: la forma de las aristas no son relevantes, sólo importan sus extremidades (o cabos); la posición de los vertices tampoco, y se puede variar para obtener un grafo más claro, y hasta sus nombres se pueden cambiar. Estos cambios se llaman isomorfismos de grafos. Generalmente, se considera que colocar los vértices en forma de polígono regular da grafos muy leíbles.

En la figura, V = { a, b, c, d, e, f }, y A = { ab, ac, ae, bc, bd, df, ef }.

Formalmente: Un grafo es una pareja G = (V, A), donde V es un conjunto de puntos, llamados vértices, y A es un conjunto de pares de vértices, llamadas aristas. Para simplificar, la arista {a,b} se denota ab.

En algunos casos es necesario imponer un sentido a las aristas, por ejemplo si se quiere representar la red de las calles de una ciudad con sus inevitables direcciones únicas. Las aristas son entonces pares ordenados de vértices, con (a,b) ≠ (b,a), y se define así grafos orientados (figura a la izquierda).

En este grafo se ha autorizado una arista que tiene sus dos cabos idénticos: es un rizo (o bucle), y aparece también una arista sin flecha: significa que la arista se puede recorrer en cualquier sentido: es bidirreccional, y corresponde o dos aristas orientadas.

En algunos casos es necesario imponer un sentido a las aristas, por ejemplo si se quiere representar la red de las calles de una ciudad con sus inevitables direcciones únicas. Las aristas son entonces pares ordenados de vértices, con (a,b) ≠ (b,a), y se define así grafos orientados (figura a la izquierda).

En este grafo se ha autorizado una arista que tiene sus dos cabos idénticos: es un rizo (o bucle), y aparece también una arista sin flecha: significa que la arista se puede recorrer en cualquier sentido: es bidirreccional, y corresponde o dos aristas orientadas.

Los grafos se pueden clasificar en dos grupos: dirigidos y no dirigidos. En un grafo no dirigido el par de vértices que representa

...