01 Teoria De Grafos V3

Universidad Tecnológica Nacional – Gestión de Datos

Teoría de grafos.
Modelos matemáticos : El objetivo es obtener información
que sea útil para la toma de decisión. Si una información
llega tarde, no sirve. Para eso se necesita la velocidad
que ofrece el computador. Entre el modelo de la realidad y
el modelo computacional, existe una interfaz que debe ser
solucionada por medio de un modelomatemático.
┌──────────────┐
┌──────────────┐
┌──────────────┐
│ Modelo del │
│
Modelo
│
│
Modelo
│
│ mundo real ├───>│ matemático ├───>│ computacional│
└──────────────┘
└──────────────┘
└──────────────┘
Figura 2.4.

Grafo : Dado un conjunto de puntos P y un conjunto de
relaciones E, la representación gráfica es lo que
comunmente denominamos grafo G(P, E).
Ejemplo :Sea P = { x, y, z }
E = { (x, y) ;(x, z) ; (z, z) }
El grafo G(P, E) es

e1
┌─────┐
┌─────────────>│ y │
│
└─────┘
┌──┴──┐
│ x │
└──┬──┘
│
e2
┌─────┐
e3
└─────────────>│ z │<────┐
└──┬──┘
│
└────────┘
Figura 2.5.

Donde x, y, z son los nodos del grafo y e1, e2 y e3 son los
arcos del grafo
Los grafos sirven para modelizar matemáticamente una
estructura de datos. De este modelo, se pueden derivar
resultados matemáticos teóricos.Ing. Juan Zaffaroni

01 – Teoria de Grafos v3.DOC
1 de 23

Universidad Tecnológica Nacional – Gestión de Datos

Subgrafo parcial : El grafo G'(P', E') es un subgrafo
parcial de G(P, E) si P' = P .and. E' está incluido en E

Subgrafo : El grafo G'(P', E') es un subgrafo G(P, E)
si P' esta incluido en P .and. E' está incluido en E

Implementación de un grafo en memoria
En el siguiente ejemplo se puedever como se implementaría
un grafo en memoria volátil, por medio de celdas y links de
memoria o en memoria permanente de un computador por medio
de archivos relativos o indexados.
El objetivo de implementaciones en memoria volátil (RAM) es
didáctico y permite aprender el manejo de punteros en
memoria. A tal efecto, es importante el significado del
valor null o nil simbolizado con el caracter (^),utilizado
en Pascal o C.
Un campo que posee este valor, es
equivalente a decir que ese campo es de dirección (tipo
pointer) y que identifica la ausencia de dirección de
memoria.

Ing. Juan Zaffaroni

01 – Teoria de Grafos v3.DOC
2 de 23

Universidad Tecnológica Nacional – Gestión de Datos

Ejemplo : Sea el grafo de la Figura 2.5., un grafo que
representa un organigrama. De esta manera podemosdeducir
que x supervisa a z y también a y . Derivado del modelo, z
se supervisa a si mismo, lo cual no tiene sentido y por lo
tanto se descarta esta relación. Si se desea implementar
este grafo, por medio de archivos relativos, entonces el
conjunto P sería el archivo maestro de legajos y el
conjunto E, el archivo estructura de empleados.
Maestro de empleados
┌──────┬────────┬─────────┐
│ NRR │Nombre │ Legajo │
├──────┼────────┼─────────┤
│ 001 │ x
│ A00001 │
│ 002 │ y
│ B23514 │
│ 003 │ z
│ B25663 │
└──────┴────────┴─────────┘

Estructura de empleados
┌──────┬──────┬──────┐
│ NRR │ From │ To │
├──────┼──────┼──────┤
│ 001 │ 001 │ 002 │
│ 002 │ 001 │ 003 │
└──────┴──────┴──────┘

Si el maestro de empleados fuera indexado con el campo
Legajo como clave, el archivo de estructura de empleadosquedaría de la siguiente manera :
Estructura de empleados
┌────────┬────────┐
│ From
│ To
│
├────────┼────────┤
│ A00001 │ B23514 │
│ A00001 │ B25663 │
└────────┴────────┘

Si la implementación se
diseñarse un registro
identificador del nodo y
memoria como arcos salgan

hiciera en memoria RAM, debería
con un campo para guardar el
tantos campos para direcciones de
del nodo.

Complejidad espacial ycomputacional.
A lo largo del desarrollo de la materia, se estudiarán
distintos tipos de algoritmos, muchas veces destinados a
resolver un mismo problema. Al aplicar un algoritmo para la
resolución de un problema, se busca que el mismo sea óptimo
en términos de recursos utilizados.
Un ejemplo es la persona que utiliza un cajero automático.
El objetivo del cajero automático es minimizar el tiempo...