*********GRAFOS********

¿Qué es un grafo?

Un grafo es una estructura de datos que almacena datos de dos tipos:

     Vértices o puntos, con un valor almacenado.

     Aristas o arcos: cada una conecta a un vértice con otro, y puede tener un valor almacenado.

·        Una arista es un par de vértices (v,w)

·        Si el par está ordenado, se dice que el grafo es dirigido o que es un dígrafo.

Los grafos tienen gran cantidad de aplicaciones por ejemplo:

·        Representación de circuitos electrónicos analógicos y digitales.

·        Representación de caminos o rutas de transporte entre localidades.

·        Representacion de redes de computadoras

¿De que consta?

Un grafo consta de dos cosas:

a)     Un conjunto N cuyos elementos se llaman nodos, vértices o puntos.

b)    Un conjunto S de parejas no ordenadas de nodos diferentes, llamadas segmentos o aristas.

ü Denotamos un grafo por G(N, S) cuando queremos destacar las dos partes de G.

ü Representamos de una manera natural los grafos por diagramas en el plano. O sea, cada nodo v de N se representa por un punto (o pequeño círculo) y en cada segmento s={v_1, v₂} se representa por una curva que conecta sus terminales v_{1 y} v_2.

Los nodos A y B son adyacentes si hay un segmento {a,b}

·        Segmento es la curva que une dos nodos.