TEORIA DE GRAFOS

ASIGNATURA TEORIA DE GRAFOS
CODIGO 840243
CAMPO DE FORMACION PROFESIONAL
PRERREQUISITOS
TERMINO CUARTO


DESCRIPCIÓN

Estudio de redes constituidas por puntos y flechas de flujo donde se pueden describir por medio de matrices, las cuales se les realiza operaciones adecuadas para hacer análisis y conclusiones acerca de las redes.


OBJETIVOS GENERALES

-Construir, describir, diferencias los grafos
-Considerar las condiciones de orden y dibujar un diagrama de Hasse
-Obtener resultados inherentes al orden como cotas, elementos extremos retículos.
-Distinguir y comparar los elementos de un árbol
-Aplicar la noción de recorrido para codificar y obtener a notación polaca de una expresión.
-Aplicar algoritmos de búsqueda y resolver problemas como el del camino más corto.
-Resolver un problema de red de transporte o un problema de asignación.

CONTENIDO


1.DEFINICIONES Y CONCEPTOS BASICOS
1.1.Producto cartesiano
1.2.Relaciones
1.3.Noción de grafo, nodos, arcos, notación.
1.4.Representación de un grafo, malle flecha, matriz de adyacencia.
1.5.Lazos, caminos, circuitos, circuitos de evler

2.CLASES DE GRAFOS RELACIONES DE UN CONJUNTO
2.1.Reflexivo, simétrico, transitivo, antisimétrico
2.2.Unión intersección.
2.3.Grafo parcial, subgrafo, grafo completo, grafo lleno, grafo vacío, grafo complementario, grafo no dirigido.

3.ORDEN
3.1.Orden Parcial
3.2.Diagrama de Hasse
3.3.Nodos comparables, orden total
3.4.Maximales, minimales, máximos, mínimos
3.5.Cotas y elementos superiores e inferiores
3.6.Retículos

4.ARBOLES
4.1.Arbol no dirigido
4.2.Arbol con raíz, padres, hijos, descendientes, hojas, nivel, altura
4.3.Arbol n - ario, árbol binario.
4.4.Recorrido de un árbol: preorden, orden, postorden
4.5.Codificación, notación polaca.

5.ALGORITMOS DE BUSQUEDA
5.1.Obtención de descendientes de un nodo
5.2.Detección de circuitos
5.3.Problema del camino más corto

6.REDES DE TRANSPORTE
6.1.Red de transporte, fuente, depósito, flujo, propiedades
6.2.Algoritmo del máximo flujo (Ford Fulkerson)

7.APAREAMIENTO
7.1.Generalidades
7.2.Problemas de asignación


TEXTO Programación Lineal y flujo de redes
Autor: Bazara
Edit.: Limusa