Tareas

Instituto tecnológico superior El Grullo
Trabajo sobre los grafos.

22/11/2011
Maestro : Miguel grajea
Alumno : isak Guzmán Jiménez
Materia : matemáticas discretas
Carrera: Ingenieroinformática

Teoría sobre los grafos
Un grafo se representa gráficamente como un conjunto de puntos (llamados vértices o nodos), unidos por líneas (aristas). Los grafos permiten estudiar lasinterrelaciones entre unidades que se encuentran en interacción.
Los especialistas consideran que el primer resultado de la teoría de grafos fue la respuesta de  LeonardEuler sobre el problema de los puentes dekönigsberg, en1736. este trabajo también se considera como uno de los primeros resultados topológicos en geometría.
Los grafos pueden ser simples (cuando sólo una arista une dos vértices cualesquiera)o complejos. los grafos simples están formados por dos conjuntos: el conjunto v de vértices o nodos y el conjunto de pares de vértices que se llaman aristas o arcos y que señalan qué nodos estánrelacionados.
un grafo simple es completo si existen aristas uniendo todos los pares posibles de vértices, mientras que un grafo es bipartito si sus vértices son la unión de dos grupos de vértices, bajouna serie de condiciones.
Representación de grafos
Las representaciones de grafos más habituales están basadas en matrices de adyacencia y listas de adyacencia. en este ejercicio se pretenderepresentar distintos grafos utilizando tanto matrices como listas de adyacencia.
Apartado a)
El plan de estudios de determinada titulación se compone de 6 asignaturas, que por simplicidad, denominaremosy . A la hora de matricularse de las distintas asignaturas se ha de tener en cuenta una serie de dependencias entre ellas (prerrequisitos). de esta forma, un alumno no se puede matricular en unaasignatura hasta haber aprobado aquellas otras que sean prerrequisito de dicha asignatura. Representaremos a continuación los prerrequisitos del plan de estudios como un grafo dirigido de dependencias....