Grafos -Estructuras De Datos

INSTITUTO POLITECNICO NACIONAL

ESCUELA SUPERIOR DE INGENIERIA MECANICA Y ELECTRICA

DEPARTAMENTO DE INGENIERIA EN COMUNICACIONES Y ELECTRONICA

MATERIA: ESTRUCTURA Y BASES DE DATOS

PROF. JOSE GERARDO ROMERO BADILLO

GRAFOS
INDICE

INTRODUCCION……………………………………………………………3

* DEFINICION………………..……………………………………….. 3

* TERMINOLOGIA…………………………………………………….3

*PECULIARIDADES………………………………………………….5

DESARROLLO………………………………………………………………6

* GRAFOS Y MULTIGRAFOS………………………………………..6

* GRAFOS DIRIGIDOS………………………………………………..7

* REPRESENTACION SECUENCIAL DE GRAFOS……………….8

i. MATRIZ DE ADYACENCIA O MATRIZ DE CAMINOS....8

ii. MATRIZ DE ADYACENCIA ……………….…..…………...9

iii. MATRIZ DE CAMINOS …………………………………….9

iv. LISTAS DE ADYACENCIA…………………………......…10

*ELIMINACIÓN DE UN ARCO EN UN GRAFO ………………….11

* RECORRIDO DE UN GRAFO ……………………………………11

i. BUSQUEDA EN ANCHURA ………………………………12

ii. BUSQUEDA EN PROFUNDIDAD…….….…………….….12

BIBLIOGRAFIA…………………………………………………………….13

INTRODUCCION
DEFINICION
Un grafo está formado por un conjunto de nodos(o vértices) y un conjunto de arcos. Cada arco en un grafo se especifica por un par de nodos.El conjunto de nodos es {A, B, C, D, F, G, H} y el conjunto de arcos {(A, B), (A, D), (A, C), (C, D), (C, F), (E, G), (A, A)} para el siguiente grafo:

TERMINOLOGÍA

* Al número de nodos del grafo se le llama orden del grafo.

* Un grafo nulo es un grafo de orden 0 (cero).

* Dos nodos son adyacentes si hay un arco que los une.

* En un grafo dirigido, si A es adyacentede B, no necesariamente B es adyacente de A

* Camino es una secuencia de uno o mas arcos que conectan dos nodos.

* Un grafo se denomina conectado cuando existe siempre un camino que une dos nodos cualesquiera y desconectado en caso contrario.

* Un grafo es completo cuando cada nodo esta conectado con todos y cada uno de los nodos restantes.

* El camino de un nodo asímismo se llama ciclo.

Algunos ejemplos podrían ser los siguientes: un gráfico de una serie de tareas a realizar indicando su secuenciación, una red de carreteras, la red de enlaces ferroviarios o aéreos o la red eléctrica de una ciudad. En cada caso, es conveniente representar gráficamente el problema dibujando un grafo como un conjunto de puntos con líneas conectándolos (arcos). 

De aquí sepodría deducir que un grafo es básicamente un objeto geométrico aunque en realidad sea un objeto combinatorio, es decir, un conjunto de puntos y un conjunto de líneas tomado de entre el conjunto de líneas que une cada par de vértices.

Los grafos son estructuras de datos no lineales que tienen una naturaleza generalmente dinámica. Se pueden dividir en dos tipos de grafos:
* GrafosDirigidos.
* Grafos no dirigidos
Un ejemplo de grafo dirigido lo constituye la red de aguas de una ciudad ya que cada tubería sólo admite que el agua la recorra en un único sentido. Por el contrario, la red de carreteras de un país representa en general un grafo no dirigido, puesto que una misma carretera puede ser recorrida en ambos sentidos.

PECULIARIDADES
Un grafo sin ciclos es un árbol.* El entregado de un nodo indica el número de arcos que llegan a se nodo.

* El fuera de grado de un nodo indica el número de arcos que salen de él.

* Un grafo de N vértices o nodos es un árbol si cumple las siguientes condiciones :
a) Tiene N-1 arcos
b) Existe una trayectoria entre cada par de nodos.
c) Esta mínimamente conectado.

DESARROLLOGRAFOS Y MULTIGRAFOS

Un grafo G consiste en dos cosas:
* Un conjunto V de elementos llamados nodos (o puntos o vértices)

* Un conjunto E de aristas tales que cada arista e de E esta identificada por un único (desordenado) par [u, v] de nodos de V, denotado por e-[v, u].

A veces denotamos un grafo escribiendo G= (V, E). Suponga que e = [u, v], entonces los nodos u y...