Teori Graf (Pewarnaan Graf)

TUGAS

10.10.Eight mathematics majors at a small college are permitted to attend a meeting dealing with undergraduate research during final exam week provided they make up all the exams missed on the Monday after they return. The possible time periods for these exams on Monday are

(1)   8:00 – 10:00

(2)   10:15 – 12:15

(3)   12:30 – 2:30

(4)   2:45 – 4:45

(5)   5:00 – 7:00

(6)   7:15 – 9:15

Use graph theory to determine the earliest time on Monday that all eight students can finish their exams if two exams cannot be given during the same time period if some student must take both exams. The eight students and the courses [Advanced Calculus (AC), Differential Equations (DE), Geometry (G), Graph Theory (GT), Linear Programming (LP), Modern Algebra (MA), Statistics (S), Topology (T)] each student is taking are listed below:

·         Alicia    : AC, DE, LP

·         Carla     : G, LP, MA

·         Edward : DE, GT, LP

·         Grace    : DE, S, T

·         Brian     : AC, G, LP

·         Diane    : GT, LP, MA

·         Faith     : DE, GT, T

·         Henry    : AC, DE, S

JAWAB:

Pada kasus ini, delapan mahasiswa harus menyelesaikan masing - masing tiga ujian dari delapan ujian dalam sehari. Waktu pelaksanaan yang mungkin dipilih terdiri dari enam periode waktu dengan ketentuan dua ujian tidak dapat dilaksanakan pada periode waktu yang sama jika kedua ujian tersebut harus diikuti oleh beberapa mahasiswa.

Berdasarkan ketentuan tersebut maka dapat digambarkan sebuah graf sederhana dari kedelapan mata kuliah yang akan diujiankan sebagai berikut: (dua mata kuliah yang diambil oleh beberapa mahasiswa dibuat bertetangga) 

Dari Graf di atas dapat dilakukan penjadwalan dengan melihat simpul yang tidak bertetangga, maka diperoleh hasil sebagai berikut:

·         Periode waktu (1) untuk simpul: LP, T, S

·         Periode waktu (2) untuk simpul: DE, G

·         Periode waktu (3) untuk simpul: GT, AC, MA