Grafos.

Algoritmo de Dijkstra

b)

a)

b)

a)

Es una matriz boleana, de orden n, donde n indica el numero de vértices de G

Matriz de adyacencia

Grafica dirigida

Es un grafo cuyos conjuntos de vértices y aristas son subconjuntos de los de un grafo G

Subgrafo

Multigrafo

Es completa si cada vértice es adyacente a todos los demas vértices

Grafica completa

Camino simple

Es cerrado si el primer y ultimo vértice son iguales

Camino cerrado

Camino

Definición

a)Digráfica o gráfica dirigida, b)Lista de adyacencia de la gráfica

Lista de adyacencia

Una lista de adyacencia para un vértice a es una lista ordenada de todos de todos los vértices adyacentes de a

Grafica etiquetada

Está etiquetada si sus aristas tienen asignado un valor

Grafica árbol

Es del tipo árbol o árbol libre si es una gráfica conexa sin ciclos

Grafica conexa

Es conexa si existe un camino simple entre cualesquiera dos de sus nodos

Ciclo

Camino simple cerrado de longitud 3 o mayor

Lazo o bucle

Arista que conecta un vértice consigo mismo

El algoritmo de Dijkstra encuentra el camino mas corto de un vértice elegido a cualquier otro vértice de la gráfica, donde la longitud de un camino es la suma de los pesos de las aristas que lo forman

a)Gráfica dirigida, b)Matriz de adyacencia de la matriz dirigida

Se caracteriza porque cada arista tiene una dirección asignada

Se denomina asi si al menos dos de sus vértices están conectados entre si por medio de dos aristas

Es simple si todos sus nodos son distintos, con excepción del primero y el ultimo que pueden ser iguales

Secuencia de n vértices que se debe seguir para llegar del vértice origen al vértice destino

Grado de un vertice

Número de aristas que contiene un nodo

Consta de nodos/vértices y de arcos/aristas

GRAFOS/GRÁFICAS