Grafos




CUADERNO ELECTRÓNICO
Qué es un grafo?
En matemáticas y ciencias de la computación un grafo (dibujo o imagen). Es conjunto de objetos llamados vértices o nodos unidos por aristas que permiten representar relaciones binarias entre elementos de un conjunto. Son objeto de estudio de la teoría de grafos, un grafo representa gráficamente como un conjunto de vértices o nodos unidos por líneas.En la práctica, los grafos permiten estudiar las interrelaciones entre unidades que interactúan unas con otras. Por ejemplo, una red de computadoras puede representarse y estudiarse mediante un grafo en el cual los vértices representan terminales y las aristas representan conexiones las cuales a su vez pueden ser cables o conexiones inalámbricas.
Un grafo G es par ordenado
G=( v,E)
Dónde:
V=conjunto de vértices o nodos-
E=Conjunto de aristas o arcos que relacionan estos vértices. Normalmente V suele ser finito. Muchos resultados importantes sobre grafos no son aplicables para grafos infinitos.
Se llama orden de grafo G a su número de V vértices.

GRAFO (unidad 1)
Es un diagrama que consta de vértices, nodos y lados. Los vértices en la siguiente figura representan a las ciudadesy los lados a las carreteras un grafo no dirigido consiste en un conjunto de V vértices o nodos y un conjunto de E lados o ramas. Tales que cada uno de E pertenece a E y se asocia a un par no ordenado de vértices V y W se escribe como:
E= (v,w) e= (w,v)
Un grafo dirigido G consiste en un conjunto de vértices y un conjunto de E lados. Tales que cada lado de e pertenece E, (e ϵ E) si un lado“e” está asociado a un par ordenado único de vértices se escribe como: e= (v, w).
Se dice que un grafo no dirigido y dirigido es incidente a V Y W por lo tanto se escribe como un conjunto de lados G= (V,E).
Grafo no dirigidoe1=v, t e2=t , s



V= {v, t, s, z, y, x, v, w}
E= {e1, e2………e11}











Los lados que inciden con un par de vértices se les llama lados paralelos cuando un lado se dirige al mismo vértice de (v, v) se le llama lazo. Cuando un grafo no tiene ni lados paralelos se le llama grafo simple.
Ejercicio 1: existe una ruta de v a y que pase directamente una vez para cadacuidad? .Si no existe. ¿Cuál es el número máximo de ciudades que se pueda visitar 1 sola vez en el trayecto de v a y?
Respuesta 3 veces {v, w, x, y} {v, u, t, s, z, y} {v, w, x, s, y}


Ejercicio 2: es posible el grafo comenzando y terminando en el mismo punto sin levantar, el lápiz del papel y sin pasar 2 veces por el mismo lado.






No se puede porque pasa por el mismo vértice v6, v4.Camino hamiltoniano
Un camino hamiltoniano, en el campo matemático de la teoría de grafos, es un camino de un grafo, una sucesión de aristas adyacentes, que visita todos los vértices del grafo una sola vez. Si además el último vértice visitado es adyacente al primero, el camino es un ciclo hamiltoniano.
El problema de encontrar un ciclo (o camino) hamiltoniano en un grafo arbitrario se sabeque es NP-completo.
Los caminos y ciclos hamiltonianos se llaman así en honor de William Rowan Hamilton, inventor de un juego que consistía en encontrar un ciclo hamiltoniano en las aristas de un grafo de un dodecaedro. Hamilton resolvió este problema usando cuaterniones, aunque su solución no era generalizable a todos los grafos.
Definición
Un camino hamiltoniano es un camino que pasa por cadavértice exactamente una vez. Un grafo que contiene un camino hamiltoniano se denomina un ciclo hamiltoniano si es un ciclo que pasa por cada vértice exactamente una vez (excepto el vértice del que parte y al cual llega). Un grafo que contiene un ciclo hamiltoniano se dice grafo hamiltoniano. Estos conceptos se pueden extender para los grafos dirigidos los cuales son igual a un carro....