NOTA

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 depares 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) el conjunto de lados del grafo G. Además º(G) y "(G)
denotan el número devé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 tienelados 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 ungrafo 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 denotanpor 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ón damos unasdefiniciones que provienen del libro de Matemá-
ticas Discreta y sus aplicaciones de Rosen [2]. Se deja al lector comparar las
diferentesdefiniciones.
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