Grafo

I. INFORMACIÓN GENERAL

1. ASIGNATURA: TEORIA DE GRAFOS
2. PRERREQUISITO: ESTADÍSTICA
3. SEMESTRE: CUARTO (IV)
4. ÁREA: INGENIERIA APLICADA


II. OBJETIVOS GENERALES

• Capacitar al estudiante con los recursos que ofrece la Teoría de Grafos para el diseño y la construcción de modelos de situaciones reales de la ingeniería. Por lo tanto, debe manejar los conceptosbásicos de grafos, sus representaciones, y técnicas para la solución de problemas.

• Crear una disciplina que incentive al estudiante a la investigación y al desarrollo del trabajo independiente.

III. RESUMEN DE LA ASIGNATURA

• Descripción Sintética de la asignatura

1. Introducción a los grafos
2. Representación de grafos en computadores
3. Otros conceptos básicos
4. Grafos Dirigidos5. Árboles
6. Distancia en grafos
7. Redes

• Temas que se van a tratar en la asignatura

1 Introducción a los Grafos
1.1 Definiciones
1.2 Grafos Notables
1.3 Grado de un Vértice
1.4 Vecindad

2 Representación de un Grafo
2.1 Matriz de Adyacencia
2.2 Matriz de Incidencia
2.3 Lista de Adyacencia

3 Otros ConceptosBásicos
3.1 Grafos Isomorfos
3.2 Subgrafos
3.3 Grafos Conectados
3.4 Grafos Especiales

4 Grafos Dirigidos
4.1 Definición
4.2 Representación
4.3 Grados de los vértices
4.4 Grafo Subrayado
4.5 Isomorfismo
4.6 Subgrafos Dirigidos
4.7 Camino – Semicamino
4.8 Grafos Simétricos y Asimétricos

5Árboles
5.1 Definiciones
5.2 Propiedades
5.3 Árbol Dirigido
5.4 Árbol con raíz
5.5 Recorridos (Profundidad y Amplitud)
5.6 Grafo Ponderado
5.7 Árboles Abarcadores de Costo Mínimo (Prim y Kruskal).

6 Distancia en Grafos
6.1 Distancia en Grafos
6.1.1 Excentricidad
6.1.2 Radio
6.1.3 Diámetro
6.1.4Centro
6.1.4 Periferia
6.1.5 Mediana
6.2 Problema de los Caminos más cortos con un solo origen (Dijkstra)
6.3 Problemas de los caminos más Cortos entre todos los pares (Floyd)

7 Redes
7.1 Conceptos básicos
1. Definiciones
2. Flujo Entrante y Saliente
3. Corte
4. Trayectoria Insaturada
5. Trayectoria Aumentativa
7.2 Algoritmo de máximacapacidad - mínimo corte
7.3 Ejercicios y Aplicaciones de Redes

IV. CONTENIDO TEMÁTICO

PRIMERA UNIDAD: INTRODUCCIÓN A LOS GRAFOS

OBJETIVO GENERAL

Conocer y manejar la terminología y conceptos básicos para el desarrollo del curso.

OBJETIVOS ESPECIFICOS

• Conocer las diferentes definiciones de grafos, sus componentes y clasificación
• Manejar los conceptosde Grados y Vecindad
• Conocer aplicaciones referentes al tema
• Obtener habilidad en la solución de ejercicios respecto al tema.

DESARROLLO CALENDARIZADO DE LA UNIDAD I:

|Fecha |Contenido |Horas |Actividad del |Metodología |Recursos |
| | | |Estudiante| | |
| | |P |TI | | | |
|31/07/2006 |Encuadre Pedagógico |2 | | | | |
|03/08/2006 |Definiciones de Grafos, |2 |4 |Adquisición yanálisis|Explicitación del |Tablero proyector y|
| |Componentes y Clasificación | | |de contenidos. |tema, ejemplificación|computador con |
| | | | |Consultar en Internet |y asesoría en el |Internet. |
| | | | |y en biblioteca....