trabajo

GRAFOS

DEFINICIONES FUNDAMENTALES

Bucle: Toda arista de la forma (v, v)

Vértices adyacentes: se dice que 2 vértices son adyacentes si están unidos por una arista.

Aristas adyacentes :se dice que 2 aristas son adyacentes cuando tiene un vértice en común

Se dice que un vértice es aislado si no es adyacente a ningún otro vértice.

Se dice que un grafo es simple si no tiene bucles ó aristas múltiples.

Tipos de Grafos

a)        Grafo Regular: Si G=(V,A), de grado “n”, si todos sus vértices tiene grado “n”.

b) Grafo dirigido o dígrafo: Es un par G=(V,A), consistente en un conjunto finito no vacío V, cuyos miembros se llaman vértices y una familia finita A de pares ordenados de vértices a cuyos extremos llamaremos arista ó arcos.

Las aristas de los dígrafos tienen sentido

Representación de Grafos

1. Matriz de adyacencia
2. Matriz de incidencia
3. Listas

“Sea un grafo G=(V,A), con n- vértices {v1, v2, v3, ……,vn}, su matriz de adyacencia es la matriz de orden nxn, M(G)=(a_ij), donde a_ij es el número de aristas que unen los vértices v_i y v_j”

Matriz de incidencia

“Es determinable cuando no existen vértices con aristas del tipo (v,v)”

Las matrices de incidencia   sólo contienen ceros y unos

Matriz de adyacencia-Dígrafos

“Dado un dígrafo D=(V,E), con n-vértices {v1, v2, v3, ……,vn}, su matriz de adyacencia es la matriz de orden nxn, M(D )=(a_ij), donde a_ij es el número de arcos que tienen a v_i de inicio y a vj de fin”

Matriz de incidencia-Dígrafos

“Cada fila representa a cada uno de los nodos del grafo, y las columnas las aristas, en la casilla M(i,j), aparecerá un 1 cuando el nodo de la fila i es inicial, y un -1 cuando el nodo i es final”

 

Exploración e Grafos: Recorridos

1. Recorrido en profundidad.
2. Recorrido en anchura.