El problema del conjunto independiente en la selección de horarios de cursos

• López Bracho, Rafael ^[1] ; Gutiérrez Andrade, Miguel Ángel ^[1] ; Ortuño Sánchez, María Paula ^[1] ; Ramírez Rodríguez, Javier ^[1]
  1. [1] Universidad Autónoma Metropolitana

     Universidad Autónoma Metropolitana

     México

     
• Localización: Revista de Matemática: Teoría y Aplicaciones, ISSN 2215-3373, ISSN-e 2215-3373, Vol. 10, Nº. 1-2, 2003, págs. 156-167
• Idioma: español
• DOI: 10.15517/rmta.v10i1-2.231
• Enlaces
  • Texto completo (pdf)
• Resumen
  • español

    El proceso de inscripción para alumnos de la Universidad Autónoma Metropolitana tiene como fundamento la libertad de cada alumno de seleccionar las asignaturas que cursará, así como los grupos en los que quedará inscrito. El éxito de este sistema, medido en términos del porcentaje de alumnos que obtienen inscripción en los cursos que seleccionaron, depende en gran medida tanto de las características de la oferta de grupos, relativas principalmente a la cantidad y a la variedad de horarios, como de la posibilidad por parte de los alumnos de hacer una selección adecuada de horarios para los cursos por los que optaron. Una selección adecuada de horarios de cursos es aquella en la que las asignaturas seleccionadas tienen horarios dos a dos compatibles. El problema de selección de horarios consiste en la obtención de una selección de horarios adecuada de cardinalidad máxima. En este trabajo se presentará un modelo de Teoría de Gráficas para este problema así como un algoritmo de solución para el mismo.

  • English

    Registration process at the Universidad Aut´onoma Metropolitana is such thatevery student is free to choose his/her own subjects and schedule. Success of thissystem, based in the percentage of students that obtain a place in the lectures chosen, depends principally on the characteristics of the supply of scheduled lectures, relativesto quantity and variety of timetables, as well as the oportunity of the students todo an adequate selection of lectures. An adequate selection of lectures is a subset ofthe lectures set with pairwise different subjects and timetables. The Choose LecturesProblem is to find the maximal adequate selection of lectures. A Graph Theory modelof the problem and an algorithm to solve it will be shown.Keywords: Graph Theory, Independent Set, Operations Research, Educational Timetabling.

• Referencias bibliográficas
  • Bergé, C. (1970) Graphes et Hypergraphes. Dunod, París.
  • Bron, C; Kerbosch, J. (1973) “Algorithm 457: Finding all cliques of an undirected graph”, Commun. ACM 161: 575–577.
  • Christofidès, N. (1975) Graph Theory: An Algorithmic Approach. Academic Press, New York.
  • Füredi, Z. (1987) “The number of maximal independent sets in connected graph”, Journal of Graph Theory 11(4): 463–470.
  • Garey, M.R.; Johnson, D.S. (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Co. Publishers,...
  • Golumbic, M.C. (1980) Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York.
  • Griggs, J.R.; Grinstead, C.M., Guichard, D.R. (1988) “The number of maximal independent sets in a connected graph”, Discrete Mathematics 68:...
  • Gutiérrez-Andrade, M.A. (1991) La Técnica de Recocido Simulado. Tesis de doctorado, UNAM, México.
  • Hammer, P.L.; Mahadev, N.V.R., de Werra, D. (1985) “Stability in CAN-free graphs”, Journal of Combinatorial Theory, Series B 38: 23–30.
  • Harary, F. (1972) Graph Theory. Addison Wesley, Reading, MS.
  • López-Bracho, R.; Ortuño-Sánchez, M.P. (2000) “Un algoritmo paralelo para el problema del conjunto independiente”, Revista de Matemática:...
  • Neumann-Lara, V. (1985) “Introducción a la Teoría de Gráficas”, IV Coloquio del Departamento de Matemáticas del CINVESTAV, México.
  • Papadimitriou, C.H.; Steiglitz, K. (1982) Combinatorial Optimization: Algorithms and Complexity. Prentice Hall Inc., Englewood Cliffs, N.J.
  • Syslo, M.; Deo, N.; Kowalik, J. (1983) Discrete Optimization Algorithms with Pascal Programs. Prentice Hall Inc., Englewood Cliffs, N.J.