Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

GRAPH COLORING ALGORITHM, AN APPROACH TO EXAM SCHEDULING OF

No description
by

Coleen Raine Abueva

on 13 March 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of GRAPH COLORING ALGORITHM, AN APPROACH TO EXAM SCHEDULING OF

GRAPH COLORING ALGORITHM, AN APPROACH TO EXAM SCHEDULING OF COLLEGE OF ARTS AND SCIENCES OF SOUTHERN LUZON STATE UNIVERSITY
design by Dóri Sirály for Prezi
SCOPE AND LIMITATIONS
METHODOLOGY
OBJECTIVES
1. To satisfy one of the applications of graph coloring and to come out with a graph model in solving the schedule problem for examination of College of Arts and Sciences using Graph Coloring Algorithm.
SIGNIFICANCE
OBJECTIVES
3. To make examination schedule for College of Arts and Sciences for 1st Semester and 2nd Semester using the application of Graph Coloring Algorithm.
SIGNIFICANCE
OBJECTIVES
2. To present a specific algorithm for exam scheduling using the application of Graph Coloring Algorithm.
To the Professors and Instructors.
SCOPE AND LIMITATIONS
To the mathematics students.
To the future researchers.
In this study, determining the upper bound for coloring the graph is necessary only for the large Acquaintanceship Graph to acquire the limit of colors to be used while in simple and small Acquaintanceship Graph, there’s no need for upper bound since it can be colored using proper vertex coloring through inspection.
This study is limited only in the application of graph coloring algorithm to exam scheduling of College of Arts and Sciences of Southern Luzon State University for the 1st Semester and 2nd Semester. The study focused only on vertex coloring of a graph. In scheduling the examination, the maximum number of rooms to be used is only 9.
The concern of the study Graph Coloring Algorithm, an Approach to Exam Scheduling of the College of Arts and Sciences of Southern Luzon State University is to make a schedule for the subjects that are from College of Arts and Sciences only including the General Education that are offered by the different program of the said college. The researcher will not include ICT01, PE01, PE02, NST01 and NST02 on the subjects to be scheduled because these subjects have its own respective room for examination. Also, RES02 is not included in the subjects to be scheduled since it has no written examination.
This study was conducted in the College of Arts and Sciences of Southern Luzon State University that covers the six courses; BS Biology, BS Mathematics, BA Communication, BA Public Administration, AB History and AB Psychology. This study will be conducted during the Academic Year 2013-2014.
Descriptive design utilizing qualitative approach was used to demonstrate the graph coloring algorithm application to exam scheduling by determining the subjects offered by each course of College of Arts and Sciences for 1st Semester and 2nd Semester. This was made by constructing an acquaintanceship graph with different subjects representing each vertex, a time slot representing each color and applying the concept of graph coloring algorithm in coloring the vertices so that no two adjacent regions are assigned the same color.
The data used in this study was the different subjects offered in the six courses of the College of Arts and Sciences for the Academic Year 2012-2013. These data were supplemented by the researcher’s readings from books, educational magazines and online resources such as internet and online journals.
A letter of request was sent to the Dean of College of Arts and Sciences to ask permission to secure the needed data for the research work. These data were the basis of the researcher in working on the application of graph coloring algorithm in exam scheduling. Also, an interview on different department chairperson was done to secure the guidelines in scheduling of examinations.
Locale of the Study
Research Design
Sources of Data
Data Gathering
SUMMARY
1. Graph Coloring Algorithm is the process of allocating the different color to each vertex so that two adjacent vertices will have different color. Vertices with the same edge must represent with different color. These processes will continuously selecting a vertex and assigning it a new color such that no two adjacent vertices have the same color. It is used to generate an examination schedule for College of Arts and Sciences for 1st and 2nd Semester. An acquaintanceship graph model which shows relationship between two or more vertices connected by edges was made to solve the schedule problem for examination.

2.After applying the concept and process of Graph Coloring Algorithm, an algorithm for exam scheduling is defined. It involved (1) presenting the subjects offered by each courses in table or matrix form, (2) making an acquaintanceship graph with difference subjects representing each vertices where every vertices with common students will be connected by an edge, (3) finding the upper bound of colors to be use using greedy coloring theorem and assign colors for each time slot considering limited number of classrooms, and (4) applying the concept of Graph Coloring Algorithm in coloring the vertices so that no two adjacent regions are assigned the same color. By this concept, it is possible to make an examination schedule.

3. Graph Coloring Algorithm can be applied in generating examination schedule of College of Arts and Sciences. The matrix served as the basis of the list of subjects with common students enrolled. With the application of this algorithm, it shows that it can provide a systematic way of scheduling and that there’s no room for overlapping of examination as shown in Tables 3, 4, 5 and 6.
CONCLUSIONS
1. Graph Coloring Algorithm provides systematic ways in making an examination schedule to assure that there will be no conflict with the schedule of a group of students taking examinations that are enrolled in the same subjects.

2. In Graph Coloring Algorithm, the number of colors that will be used in coloring the graph can be determined by the given number of rooms, such that the larger the number of rooms, the lesser the color that will be use.

3. It is possible to have more systematic way of scheduling of examination by creating an acquaintanceship graph so that no two adjacent vertices assigned the same color after applying the concept of graph coloring algorithm.

RECOMMENDATIONS
1. Conduct a study using other properties of Graph Coloring Algorithm applied to different real life situations.

2. Apply Graph Coloring Algorithm in finding the systematic way of scheduling in different public and private institutions.

3. Apply Graph Coloring Algorithm in scheduling classes for schools and universities.

4. Make a computer program that can generate the application of Graph Coloring Algorithm in scheduling.

RESULTS
Acquaintanceship Graph for major subjects of 1st Semester
Acquaintanceship Graph for General Education and some major subjects of 1st Semester
Acquaintanceship Graph for major subjects of 2nd Semester
Acquaintanceship Graph for General Education and some major subjects of 2nd Semester
Colored Acquaintanceship Graph for major subjects of 1st Semester
Colored Acquaintanceship Graph for General Education and some major subjects of 1st Semester
Colored Acquaintanceship Graph for major subjects of 2nd Semester
Colored Acquaintanceship Graph for General Education and some major subjects of 2nd Semester
RESULTS
Table 8. Schedule for 2nd Day of Examination of College of Arts and Sciences for 1st Semester.
Table 10. Schedule for 1st Day of Examination of College of Arts and Sciences for 2nd Semester.
Table 11. Schedule for 2nd Day of Examination of College of Arts and Sciences for 2nd Semester.
Table 7. Schedule for 1st Day of Examination of College of Arts and Sciences for 1st Semester.
Table 12. Schedule for 3rd Day of Examination of College of Arts and Sciences for 2nd Semester.
Table 9. Schedule for 3rd Day of Examination of College of Arts and Sciences for 1st Semester.
To the College of Arts and Sciences.
METHODOLOGY
ICT01, PE01, PE02, NST01, NST02 and RES02 are not included on the subjects to be scheduled
ICT01, PE01, PE02, NST01, NST02 and RES02 are not included on the subjects to be scheduled
Full transcript