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).
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 bi,j como bi,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 bi,j o bi,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).
No hay comentarios:
Publicar un comentario