grafos

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}, quese 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 queG 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 paresordenados. 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 dellibro de Matemá-
ticas Discreta y sus aplicaciones de Rosen [2]. Se deja al lector comparar las
diferentes definiciones.

Adyacencia de Vértices, Incidencia de Aristas y Grado de los Vértices
Dosvertices 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 esincidente a
los vértices u y 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 losvértices de G respectivamente

Representaciones de los grafos
Sea G = (V, E) un grafo con ν vértices y ε aristas, entonces le corresponde
una matrizν × ε denominada la matriz de incidencia de...