Matemática discreta grafos

5.1 DEFINICIONES BÁSICAS Y SU REPRESENTACIÓN
Empezaremos con un
Ejemplo:Dado un mapa de las autopistas de un lugar, se podría determinar si existe una ruta por autopista entre dos ciudades en el mapa. Sea S = {a, b, c, ...} el conjunto de ciudades y  una relación binaria sobre S tal que (a, b)  si existe una autopista de la ciudad a a la ciudad b.

 = {(a, b), (a, c), (a, d), (a, e), (b,d), (c, d), (d, e)}
Definición:A la representación gráfica de los objetos y las relaciones binarias sobre ellos se conoce como grafo y consta de vértices (nodos) y lados (aristas).
Los vértices, que son los puntos del grafo, representan los elementos del conjunto. Los lados representan los elementos (x, y) que están relacionados.
5.2 GRAFOS DIRIGIDOS Y NO DIRIGIDOS
Definición:Un grafo (grafo nodirigido) G consta de un conjunto V de vértices o nodos y un conjunto E de lados, (ramas o aristas) tales que cada lado e  E esta asociado a un par no ordenado de vértices.
Si un lado e esta asociado a un único par de vértices v y w se escribe e = (v, w) o también se escribe e = (w, v).
NOTA:En este contexto (v, w) denota un lado de un grafo no dirigido y no un par ordenado de números.Definición: Un grafo dirigido (o dígrafo) G consta de un conjunto V de vértices y un conjunto E de lados, tal que e  E esta asociado a un par ordenado único de vértices v y w y se escribe e = (v, w).Definición: Se dice que un lado e = (v, w) de un grafo (dirigido o no dirigido) es incidente en v y w. Se dice que los vértices v y w son incidentes en e y también que los vértices son adyacentes.
Si G es ungrafo (dirigido o no dirigido) con un conjunto de vértices V y un conjunto de lados E, se escribe G = (V, E).Ejemplo: 
G
Este grafo G consta de un conjunto V de vértices
V = {S, T, U, V, W, X, Y, Z}
y el conjunto de lados
E = {e1, e2, e3, .... , e11 }.
El lado e1 esta asociado con el par no ordenado {T, U}, el lado e10 esta asociado al par no ordenado {S, X}. El lado e1 se denota por (U, T) obien (T, U). El lado e4 es incidente en los vértices Y y Z por lo que Y y Z son vértices adyacentes.
Ejemplo:
G
En este dígrafo los lados dirigidos están indicados por flechas. El lado e1 esta asociado al par ordenado de vértices (v2 , v1) por lo que se escribe e1 = (v2 , v1) y el lado e7 con el par ordenado (v6, v6), por lo que se escribe e7 = (v6, v6).Ejemplo:Consideremos ahora el siguientegrafo:
G
Cuando dos lados distintos están relacionados con el mismo par de vértices se llaman lados paralelos, como e1 y e2 que están asociados con el par no ordenado de vértices {v1 , v2}. Un lado de la forma (v, v) que inicia y termina en el mismo vértice se llama lazo, como ocurre en e3 = (v2, v2). En el grafo G ningún lado es incidente a v4, un grafo que no tiene lazos ni lados paralelosrecibe el nombre de grafo simple.
Ejemplo:
Grafo simple
 
Grafo no simple
Definición:Un grafo completo de n vértices, que se denota Kn, es el grafo simple con n vértices en el cual existe una arista entre cada par de vértices distintos.
Ejemplo:

Grafo completo K4
Ejemplo:Problema de los puentes de Köningsberg.Dos islas que se encuentran en el río Pregel en Köningsberg (antes PrusiaOriental, llamado ahora Kaliningrado) están conectadas entre si y con la margen del río por puentes como se indica en la siguiente figura: 

El problema consiste en partir desde cualquier lugar (A, B, C, o D), seguir caminando y pasar por cada uno de los puentes una sola vez y luego volver al punto de partida.
A un recorrido de este tipo se llama "circuito de Euler". Tal recorrido puede representarsemediante un grafo como sigue:

La solución puede obtenerse fácilmente utilizando el concepto de valencia de un vértice.
Definición:La valencia (o grado) de un vértice v se denota (v) y es numero de datos incidentes en v.
Ejemplo:Del grafo anterior tenemos que:
 (A) = 3 (B) = 5 (C) = 3 (D) = 3Más adelante se demostrará que el Problema de los puentes de Köningsberg no tiene solución.Un...