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) 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értice terminal 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 Muestre que si G es simple, entonces " ≤

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).