TEORIA DE GRAFOS

Definición 1.-

Un GRAFO es un par G(V,E) donde V es un conjunto finito diferente de vacio cuyos elementos se llaman vertices, E tiene como elemento a pares de vertices llamados arcos.

GRAFOS NO ORIENTADOS

Definición 1.

i,j son adyecentes si E (i,j) o (j,i).

Definción 2.

(i,j) es incidente sobre i,j.

Definición 3.

El grado o valencia del vertice i,di es el número de arcos incidentes sobre i.

Definición 4.

El grafo no orientado G , = (V1, E1) es un subgrafo de G = (V, E)

si V1 y E1 estan incluidos en V y E respectivamente.

Definición 5.

Un camino del vertice i.al vertice j es una secuencia de vertices.

Definición 6.

Un camino es simple si ningun arco se repite , ningun vertice se repite

(con la exepcion del primer y ultimo vertice ).

Definicion 7.

Un camino es cerrrado si el primer vertice es identico al ultimo.

Definicion 8.

Un ciclo es un camino simple y cerrado.

Definicion 9.

Un grafo no orientado , G ( v,e) es conexo si para cada par de vertices

i¹ j existe un camino de i,a j.

Definición 10.

Un grafo es aciclico si no tiene ciclos.

 

GRAFOS ORIENTADOS

Definición 1.-

Se llama Grafo orientado a aquel grafo cuyos arcos tienen una orientación (flecha) parten de un vertice y llegan a otro vertice

Definición 2.-

Un arco orientado (i,j) se dice que es incidente a j o incidente desde i.

Definición 3.-

El grado de entrada del vertice i(diin) es el número de arcos incidentes a

i. El grado de salida del vertice i(diout) es el numero de arcos incidentes desde

Definción 4.-

Se llama camino orientado a una secuencia de vertices y arcos.

Definición 5.-

Un camino orientado es simple cuando todos los vertices son distintos excepto el primero y el último.

Definición 6.-

Un camino orientado es cerrado si el primer vertice es identico al último.

Definición 7.-

Se llama CIRCUITO o CICLO ORIENTADO a un camino orientado simple y cerrado.

Definición 8.-

Se llama a un grafo fuertemente conexo si para cada par de vertices

distintas i¹ j existe un circuito que los contiene.

 

Definición 9.-

Se llama SEMICAMINO a una secuencia de vertices P=i1,i2,....in

en un grafo G, si (ij,ij+1 )o (ij+1,ij) pertenece al conjunto de arcos.

Definicion 10.-

Un semicamino es simple cuando ningún arco o vertice se repite.

Definición 11.-

Un semicamino es cerrado cuando el primer vertice es identico al

último.

Definición 12.-

Un semiciclo es un semicamino simple y cerrado.

Definición 13.-

Un grafo orientado G es DEBILMENTE CONEXO si para cada par

de vertices distintos (i¹ j) existe un semiciclo en G de i a j.

Definición 15.-

Un grafo orientado es completo si cumple lo siguiente ï Eï =n (n-1)

 

ARBOL

Definición 1.-

Un árbol es un grafo no dirigido que es acíclico y conexo.

Definición 2.-

Un árbol parcial o generador de un grafo G es un subgrafo de G

que es árbol y contiene a todos los vertices G.

Definición 3.-

Sea G un grafo no orientado con pesos, se llama árbol parcial de peso

mínimo al árbol parcial de G cuyo peso sea menor o igual a cualquier otro.

Definición 4.-

Se llama árbol enraisado a aquel árbol orientado en la que un solo

vertice tiene grado de entrada 0 y todo lo demas grado de entrada 1.

Definición 5.-

El grado del vertice j es el número de arcos que parte desde j .

Definición 6.-

El grado de un árbol enraisado es igual al grado del vertice con el

máximo valor.

Definición 7.-

Se llama árbol K-ario a aquel árbol enraizado de grado K

 

 

RECORRIDO DE VERTICES (ALGORITMOS)

BUSQUEDA `PRIMERO A LO ANCHO(BFS)

1. Q=0

2. visitar y marcar v

3. insertar v en Q

4. Mientras Q¹ 0 hacer

4.1. x=valor en el frente de Q

4.2. eliminar x de Q

4.3. Para cada vertice w adyacente a x no marcado hacer:

4.3.1. visitar y marcar w

4.3.2. insertar w en Q

5. Fin

BUSQUEDA PRIMERO EN PROFUNDIDAD (DFS)

1. S=0

2. visitar, marcar e insertar V

3. mientras S ¹ 0 hacer

3.1 mientras hay un vertice W no marcado adyacente el valor en la cima

de S hacer

3.1.1 visitar, marcar y apilar W.

3.2 eliminar elemento de la parte superior

ALGORILMO DEL CAMINO MAS CORTO DE UN VERTICE A OTRO

DIJSTRA

1. X=V

2. mientras X¹ W hacer

2.1 seleccione un arco candidato (Y,Z) tal que

dist (V,Z) = dist (V,Y) + W (Y , Z) es mínimo entre todos los vertices

asociados.

2.2 añadir Z,(Y;Z) al árbol

2.3 X=Z.

3. fin

 

ALGORISMO DE ARBOL PARCIAL DE COSTO MINIMO

DIJSTRA- PRIM

1.- seleccione un vertice arbitrario.

2. MIENTRAS hay vertices vecinos hacer

2.1 seleccione un arco de peso mínimo entre un vertice del árbol y un

vertice vecino.

2.2 añadir el vertice y el arco escogido al árbol.

3. fin.

ALGORITMO PREORDER

Se emplea para recorrer los vertices de un arbol orientado

1. visitar la raíz R .

2. visitar el PREORDER los subarboles r1, r2, ....rn y en ese orden.

ALGORITMO POSTORDER

1. visitar el POSTORDER r1,r2, ....r n en ese orden.

2. visitar la raíz r.