GRAFOS

Cómo se conforma un grafo?
Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de pares de vértices, llamados aristas que pueden ser orientados o no. Típicamente, un grafo se representa mediante una serie de puntos (los vértices) conectados por líneas (las aristas).

 Qué es un vértice o nodo?

Ø Punto de intersección o unión de varios elementos que confluyen en el mismo lugar

En estructura de datos:

Un nodo es uno de los elementos de una lista enlazada, de un árbolo de un grafo . Cada nodo será una estructura o registro que dispondrá de varios campos , y al menos uno de esos campos será un puntero o referencia a otro nodo, de forma que, conocido un nodo, a partir de esa referencia, será posible en teoría tener acceso a otros nodos de la estructura. Los nodos son herramientas esenciales para la construcción de estructuras de datos dinámicas.

Un Arco o también llamado Arista corresponde a una relación entre dos vértices de un grafo .

Tipos de grafos dígrafo y no dirigido.
Un dígrafo o grafo dirigido es un grafo en el cual las aristas están dirigidas (y se acostumbra llamarles arcos). Es decir, la relación entre dos vértices adyacentes no necesariamente es simétrica ejemplo: si hay un arco que va de A a B (relación que se denota a veces como A→B ) entonces se dice que A domina a B .

Grafo no dirigido es un conjunto de pares no ordenados de elementos.
Un par no ordenado es un conjunto de la forma {a,b} , de manera que {a,b} = {b,a} .

En que consiste el camino en un grafo
Un camino en un grafo es una sucesión finita en la que aparecen alternadamente vértices y aristas de dicho grafo
Tipos de caminos
Camino euleriano: es un camino o circuito que contiene todas las aristas apareciendo cada una de ellas exactamente una vez. Un grafo que admite dicho circuito se denomina grafo euleriano, y sus vértices o tienen grado par o dos de los vértices tienen grado impar.
Camino hamiltoniano: es un camino simple que contiene todos los vértices apareciendo cada uno de ellos exactamente una vez. Un ciclo que a su vez es un camino hamiltoniano se denomina ciclo hamiltoniano, y un grafo que contiene un ciclo hamiltoniano se denomina grafo hamiltoniano.