¿Que es un grafo?
Un GRAFO es un conjunto de nodos o vértices (V) y un conjunto de aristas (E), donde cada arista relaciona a un par de nodos pertenecientes a V.
La estructura algebraica para los grafos es G=(V,E).
Existen dos tipos de Grafos:
- GRAFO DIRIGIDO
- GRAFO NO DIRIGIDO
Grafos Dirigidos
-
- Un GRAFO DIRIGIDO G consiste de un conjunto V de vértices y un conjunto E al conjunto de aristas del grafo.
Un GRAFO DIRIGIDO G consiste de un conjunto V de vértices y un conjunto E al conjunto de aristas del grafo.
Grafos no dirigidos
Un Grafo no Dirigido se diferencia de un Grafo Dirigido debido a que cada arista en E es un par no ordenado de vértices.
Los grafos se pueden representar de la siguiente manera:
- Matriz de Adyacencia
- Lista de Adyacencia
- Arreglos para la Lista de Adyacencia.
La matriz de adyacencia es una matriz cuadrada que se utiliza como una forma de representar relaciones binarias.
Una lista de adyacencia es una representación de todas las aristas o arcos de un grafo mediante una lista.
Tambien deben tener en cuenta lo siguiente:
VENTAJAS Y DESVENTAJAS
DE LA MATRIZ DE ADYACENCIA
DE LA MATRIZ DE ADYACENCIA
VENTAJAS:
- Se puede determinar en un tiempo fijo y constante si un enlace(arco) pertenece o no al grafo.
- Es fácil determinar si existe o no un arco o enlace, solo se debe posicionar en la matriz.
- Es fácil determinar si existe un ciclo en el grafo, basta multiplicar la matriz por ella misma n veces hasta obtener la matriz nula(no hay ciclos) o bien una sucesión periódica de matrices(hay ciclo)
DESVENTAJAS:
- Se requiere un almacenamiento |v|*|v|. Es decir O(n2).
- Solo al leer o examinar la matriz puede llevar un tiempo de O(n2).
VENTAJAS Y DESVENTAJAS
DE LAS LISTAS DE ADYACENCIA
DE LAS LISTAS DE ADYACENCIA
VENTAJAS:
- La lista de adyacencia requiere un espacio proporcional a la suma del número de vértices más el número de enlaces(arcos). Hace buen uso de la memoria.
- Se utiliza bastante cuando el número de enlaces es mucho menor que O(n2)
•DESVENTAJAS:
- La representación con lista de adyacencia es que puede llevar un tiempo O(n) determinar si existe un arco del vértice i al vértice j, ya que pueden haber O(n) vértices en la lista de adyacencia. Para el vértice i.
Recorrido de Grafos.
Los grafos se pueden recorrer de 2 formas:
Por amplitud o anchura.
Por profundidad.
danielandres25
Estamos trabajando para Usted :D 