Grafos.

GRAFOS/GRÁFICAS

Definición

Multigrafo

Lista de adyacencia

Grafica conexa

Camino

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

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

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

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

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

Subgrafo

Grafica árbol

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

Camino cerrado

a)

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

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

Grado de un vertice

Número de aristas que contiene un nodo

Grafica dirigida

Camino simple

Grafica completa

b)

Lazo o bucle

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

Se caracteriza porque cada arista tiene una dirección asignada

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

Arista que conecta un vértice consigo mismo

Grafica etiquetada

Matriz de adyacencia

Ciclo

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

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

Está etiquetada si sus aristas tienen asignado un valor

Camino simple cerrado de longitud 3 o mayor

Algoritmo de Dijkstra

b)

a)

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

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