Grafos

Grafos

Un grafo es un diagrama que consiste de puntos (llamados nodos ) unidos por líneas (llamadas arcos ). Cada arco en un grafo se especifica por medio de un par de nodos.

Definición de grafos

Un grafo es un objeto matemático que se utiliza para representar circuitos, redes, etc. Los grafos son muy utilizados en computación, ya que permiten resolver problemas muy complejos.
Imaginemos que disponemos de una serie de ciudades y de carreteras que las unen. De cada ciudad saldrán varias carreteras, por lo que para ir de una ciudad a otra se podrán tomar diversos caminos. Cada carretera tendrá un coste asociado (por ejemplo, la longitud de la misma). Gracias a la representación por grafos podremos elegir el camino más corto que conecta dos ciudades, determinar si es posible llegar de una ciudad a otra, si desde cualquier ciudad existe un camino que llegue a cualquier otra, etc.
El estudio de grafos es una rama de la algoritmia muy importante. Estudia remos primero sus rasgos generales y sus recorridos fundamentales, para tener una buena base que permita comprender los algoritmos que se pueden aplicar.

Tipos de grafos

LAZO
Es cuando un arco sale de un nodo y regresa al mismo nodo sin tocar otro nodo diferente.
LADOS PARALELOS
Es cuando dos arcos salen de un mismo nodo y ambos llegan a otro nodo.
GRAFO SIMPLE
Es aquel grafo que no tiene ni lazos, ni lados paralelos.

Representación de grafos en memoria

Un camino de longitud n de V a W es una sucesión de lados que va de V a W y la cual tiene n lados distintos entre sí.
Un camino simple de longitud n de V a W es una de la forma (V0,V1,V2...Vn) en donde V0=V y Vn =W,y VV0,V1,Vn son distintos entre sí.
Un circuito o ciclo es un camino de V aV.
Un circuito simple es un circuito de la forma (V0,V1,V2...Vn) en donde V0=Vn y V0,V1...Vn-1 son distintos entre sí.es la ciencia de la computaciones una estructura de datos y concretos tipos abstrato de datos lineales lista enlazada ,vertice forma de representacion generadores constructores,selectores, grafo simples ,dirigido y no dirigido,.origen de la palabra grafo es griego ,su significado etimologico es trazar con frecuencia de respuesta de la vida cotidiana algunos ejemplos podina ser lo siguientes ,e podría deducir que un grafo es básicamente un objeto geométrico aunque en realidad sea un objeto combinatorio,es decir,un conjunto de puntos y un conjunto de líneas tomado de entre el conjunto de líneas que une cada par de vértices.Por otro lado,y debido a su generalidad y a la gran diversidad de formas que pueden usarse,resulta complejo tratar con todas las ideas relacionadas con un grafo.
Para facilitar el estudio de este tipo de dato,a continuación se realizará un estudio de la teoría de grafos desde el punto de vista de las ciencias de la computación. Considerando que dicha teoría es compleja y amplia,aquí sólo se realizará una introducción a la misma,describiéndose el grafo como un tipo de dato y mostrándose los problemas típicos y los algoritmos que permiten solucionarlos usando un ordenador.
Los grafos son estructuras de datos no lineales que tienen una naturaleza generalmente dinámica. Su estudio podría dividirse en dos grandes bloques:

• Grafos Dirigidos.
• Grafos no Dirigidos(pueden ser considerados un caso particular de los anteriores).

Un ejemplo de grafo dirigido lo constituye la red de aguas de una ciudad ya que cada tubería sólo admite que el agua la recorra en un único sentido.Por el contrario,la red de carreteras de un país representa en general un grafo no dirigido,puesto que una misma carretera puede ser recorrida en ambos sentidos.No obstante,podemos dar unas definiciones generales para ambos tipos.
A continuación daremos definiciones de los dos tipos de grafos y de los conceptos que llevan asociados grafos de salida y subdual matriz adyacencia rafo es etiquetado,entonces tanto b_i,j como b_i,j representan al coste o valor asociado al arco (i,j) y se suelen denominar matrices de coste. Si el arco (i,j) no pertenece a A entonces se asigna b_i,j o b_i,j un valor que no puede ser utilizado como una etiqueta valida.
La principal ventaja de la matriz de adyacencia es que el orden de eficiencia de las operaciones de obtencion de etiqueta de un arco o ver si dos vertices estan conectados son independientes del número de vértices y de arcos. Por el contrario, existen dos grandes inconvenientes:

• Es una representación orientada hacia grafos que no modifica el número de sus vertices ya que una matriz no permite que se le o supriman filas o columnas.
• Se puede producir un gran derroche de memoria en grafos poco densos (con gran número de vértices y escaso número de arcos).

Para evitar estos inconvenientes se introduce otra representación: las listas de adyacencia. ta estructura de datos la idea es asociar a cada vertice i del grafo una lista que contenga todos aquellos vértices j que sean adyacentes a él. De esta forma sóllo reservará memoria para los arcos adyacentes a i y no para todos los posibles arcos que pudieran tener como origen i. El grafo, por tanto, se representa por medio de un vector de n componentes (si |V|=n) donde cada componente va a ser una lista de adyacencia correspondiente a cada uno de los vertices del grafo. Cada elemento de la lista consta de un campo indicando el vértice adyacente. En caso de que el grafo sea etiquetado, habrá que añadir un segundo campo para mostrar el valor de la etiqueta.