Grafo

INTRODUCCIÓN
La Teoría de Grafos es parte de Matemáticas Discreta que es una asignatura del plan de estudios de Ingeniería en Informática, que tiene un marcado enfoque práctico, aplicado y computacional, además de un acentuado carácter formativo. El contenido referido a esta temática se plantea como respuesta a una variada serie de problemas de la «vida real» (diseño de bloques, flujo de redes,diseño de circuitos, transporte de viajeros, asignaciones horarias o de tareas, programación, etc.), lo que le confiere el enfoque aplicado que señalamos arriba, aprendiendo el alumno, además, a buscar modelos matemáticos adecuados para gran número de situaciones diferentes, lo que suele ser muy habitual en el desarrollo profesional. El tratamiento que se pretende dar a la asignatura es prácticopues, aparte de la resolución de ejemplos y ejercicios que tiene que desarrollar sobre el papel, se debe dedicar una buena parte de tiempo a realizar prácticas en el computador para resolver algún problema en lo posible concreto (extraído de un caso real)

Un grafo
Un grafo está formado de vértices y aristas (lados), por lo tanto G = {V, E} Los vértices del grafo G son: V_1, V_2, V_3, V_4entonces V = {V_1, V_2, V_3, V_4} Las aristas del grafo son: e_1, e_2, e_3, e_4 entonces E = {e_1, e_2, e_3, e_4} Entonces podemos decir que G = {{V_1, V_2, V_3, V_4}, {e_1, e_2, e_3, e_4}} Como el grafo G no tiene lazos ni lados paralelos entonces es un grafo simple. Otro ejemplo de grafo no dirigido es el siguiente:

GRADO DE UN VERTICE
GRADO DE UN VERTICE (δ) El grado de un vértice v, δ(v), es elnúmero de aristas que inciden en v.

Subgrafo
Un subgrafo de un grafo G es un grafo cuyos conjuntos de vértices y aristas son subconjuntos de los de G. Se dice que un grafo G contiene a otro grafo H si algún subgrafo de G es H o es isomorfo a H(dependiendo de las necesidades de la situación). El subgrafo inducido de G es un subgrafo G' de G tal que contiene todas las aristas adyacentes alsubconjunto de vértices de G.
Definición: Sea G=(V, A). G’=(V’,A’) se dice subgrafo de G si:
1- V’ V
2- A' A
3- (V’,A’) es un grafo

Aristas dirigidas y no dirigidas
En algunos casos es necesario asignar un sentido a las aristas, por ejemplo, si se quiere representar la red de las calles de una ciudad con sus direcciones únicas. El conjunto de aristas será ahora un subconjunto de todos losposibles pares ordenados de vértices, con (a, b) ≠ (b, a). Los grafos que contienen aristas dirigidas se denominan grafos orientado.

CAMINOS Y CICLOS
Camino o trayectoria es el recorrido desde un V0 (vértice inicial) a Vn (vértice destino) de longitud n, es una sucesión alternante de n + 1 vértices y n aristas que comienza en el vértice V0 y termina en el Vn . Formalmente significa: comience enel vértice v0; recorra la arista e1 hasta v1; siga por la arista e2 hasta v2, y así sucesivamente.
(v_0', e_1', v_1', e_2', v_2', …. v_{n - 1}, e_n, v_n)
Donde la arista e_i es incidente sobre los vértices v_{i - 1} y v_i para i = 1, … n

CICLO DE EULER Y DE HAMILTON
CICLO DE EULER
Si una grafica G tiene un ciclo de euler, entonces G es conexa y todo vértice tiene grado par (2, 4, 6 …).Observamos que la grafica es conexa, puesto que sus vértices tienen grado par así:
δ(v1) = δ (v2) = δ (v3)= δ (v5) = 4
δ (v4) = 6
δ (v6) = δ (v7) = 2

CICLO DE HAMILTON
En honor de Hamilton, decimos que un ciclo en una grafica G que contiene cada vértice en G exactamente una vez, excepto por el vértice inicial y final que aparece dos veces, recibe el nombre de ciclo hamiltoniano.El camino de Hamilton solicitado sería: (a, f, g, p, q, r, s, t, o, n, m, l, k, j, i, h, b, c, d, e, a). Como pueden observar no se repite vértice alguno, excepto el inicial y final que es el mismo
Caracterización de los grafos
Un problema interesante en la teoría de grafos, que no ha sido resuelto del todo, es el referente a la búsqueda de todos los grafos simples diferentes que existen con...