Introduccion a grafos
Páginas: 3 (687 palabras)
Publicado: 28 de junio de 2011
MATEMÁTICA
DISCRETA
Tema
GRAFOS
Introducción
1
ÍNDICE
1. INTRODUCCIÓN A LOS GRAFOS. – Euler y los puentes de Könisberg. – Definiciones y terminología.
• • • Grafo, multigrafo,pseudografo, grafo dirigido y con peso, etc. Familias particulares de grafos. Subgrafos. Grado de un vértice. Teorema de Euler.
– Isomorfismo de grafos. 2. CONECTIVIDAD. – Recorridos y caminos. –Grafos conexos. – Grafos eulerianos. – Grafos hamiltonianos.
2
– Árboles. – Árboles recubridores.
3. GRAFOS PONDERADOS. – Árboles recubridores mínimos. Algoritmo de Kruskal. – Caminos mínimos.Centro y mediana. – Algoritmo de Dijkstra.
4. GRAFOS DIRIGIDOS ACÍCLICOS. (RELACIONES) – Preorden. Cierres. Diagramas de Hasse. – Orden topológico. – Planificación de tareas.
3
BIBLIOGRAFÍA
•[1] MATEMÁTICA DISCRETA, (2ª edición), "Notas de la asignatura" editadas por el Servicio de Publicaciones de la E.U. de Informática. • [2] GRIMALDI, R.P.: “Matemática Discreta y Combinatoria”.
AddisonWesley, 1997.
• [4] ROSEN, K.H.: “Matemática Discreta y sus aplicaciones”.
McGraw-Hill, 2004.
• [1-Complementaria] BRADLEY, J.: “Introduction to Discrete Mathematics”. Addison Wesley, 1988.
4 Introducción a los grafos.
• Euler y los puentes de Könisberg.
– Formulación del problema. – Modelización. – Generalización.
• Utilidad de los grafos.
– Modelización y resolución deproblemas. – Representación de la información. – Estructura de datos.
• Aplicación de los grafos.
– – – – Matemáticas. Informática. Otras ciencias: geografía, biología, ecología, economía, etc. Otrasartes: música, lingüística, literatura, etc.
5
Relaciones del tema con otras asignaturas
• Con la mayoría de las de matemáticas
– Matemática Discreta. • Árboles estructurales, tableaux, árboles dedependencia. – Lógica.
• Con bastantes de informática
– Estructuras de Datos I y II. – Algorítmica. – Ingeniería del Software. – Inteligencia Artificial.
6
Euler (1707-1783) y los puentes...
DISCRETA
Tema
GRAFOS
Introducción
1
ÍNDICE
1. INTRODUCCIÓN A LOS GRAFOS. – Euler y los puentes de Könisberg. – Definiciones y terminología.
• • • Grafo, multigrafo,pseudografo, grafo dirigido y con peso, etc. Familias particulares de grafos. Subgrafos. Grado de un vértice. Teorema de Euler.
– Isomorfismo de grafos. 2. CONECTIVIDAD. – Recorridos y caminos. –Grafos conexos. – Grafos eulerianos. – Grafos hamiltonianos.
2
– Árboles. – Árboles recubridores.
3. GRAFOS PONDERADOS. – Árboles recubridores mínimos. Algoritmo de Kruskal. – Caminos mínimos.Centro y mediana. – Algoritmo de Dijkstra.
4. GRAFOS DIRIGIDOS ACÍCLICOS. (RELACIONES) – Preorden. Cierres. Diagramas de Hasse. – Orden topológico. – Planificación de tareas.
3
BIBLIOGRAFÍA
•[1] MATEMÁTICA DISCRETA, (2ª edición), "Notas de la asignatura" editadas por el Servicio de Publicaciones de la E.U. de Informática. • [2] GRIMALDI, R.P.: “Matemática Discreta y Combinatoria”.
AddisonWesley, 1997.
• [4] ROSEN, K.H.: “Matemática Discreta y sus aplicaciones”.
McGraw-Hill, 2004.
• [1-Complementaria] BRADLEY, J.: “Introduction to Discrete Mathematics”. Addison Wesley, 1988.
4 Introducción a los grafos.
• Euler y los puentes de Könisberg.
– Formulación del problema. – Modelización. – Generalización.
• Utilidad de los grafos.
– Modelización y resolución deproblemas. – Representación de la información. – Estructura de datos.
• Aplicación de los grafos.
– – – – Matemáticas. Informática. Otras ciencias: geografía, biología, ecología, economía, etc. Otrasartes: música, lingüística, literatura, etc.
5
Relaciones del tema con otras asignaturas
• Con la mayoría de las de matemáticas
– Matemática Discreta. • Árboles estructurales, tableaux, árboles dedependencia. – Lógica.
• Con bastantes de informática
– Estructuras de Datos I y II. – Algorítmica. – Ingeniería del Software. – Inteligencia Artificial.
6
Euler (1707-1783) y los puentes...
Leer documento completo
Regístrate para leer el documento completo.