Grafos

Grafos
Definición básica
Un grafo es la representación por medio de conjuntos de relaciones arbitrarias entre objetos. Existen dos tipos de grafos según la relación entre los objetos se univocao biunívoca. Los primeros forman los grafos dirigidos o biógrafos y los segundos los grafos no dirigidos o simplemente grafos .
Un grafo dirigido o diágrafo consiste en un conjunto de vértices V yun conjunto de arcos A. Los vértices se denominan nodos o puntos, los arcos también se conocen como aristas o líneas dirigidas que representan que entre un par de vértices existen una relación univocade modo que los arcos se representan por medio de pares ordenados (a,b) donde se dice que a es la cabeza y b la cola del arco y a menudo se representa por medio de una flecha tal como se muestra en lafigura.
Nodo
B

Nodo
B

Nodo
A

Nodo
A


Un vértice que tiene un arco salindo de el se denomina fuente y un vértice que solo tiene arcos Asia el se denomina sumidero dichanomenclatura es importane cuando los grafos se usan para resolver diagramas de flujo. Existen grafos en donde los arcos tienen asociado un valor en cuyo ablamos en grafos ponderados y haora se representancomo tripletas. Siguen existiendo información del peso dirijido de dicho arco. Asi pues el arco se representa a=(vi,vj,w) donde vi y vj son el origen del destino y w es el peso respectivamente.
2-.Metodos de representación en computadora.
Mostraremos las mas comunes y la forma de impleméntalo. La primera es adyacencia , por este medio se tiene n*n donde n es el numero de vértices o numero degrafos, una forma es que los renglones representen el origen y las columnas y destino de cada arista o arco en el grafo . Si el grafo es ponderado se acostumbra a poner 0 en el renglón i .

|1 | 2 | 3 | 4 | 5 |
1 | 0 | 1 | 0 | 0 | 1 |
2 | 1 | 0 | 1 | 1 | 1 |
3 | 0 | 1 | 0 | 1 | 0 |
4 | 0 | 1 | 1 | 0 | 1 |
5 | 1 | 1 | 0 | 1 | 0 |


2222...