SELAMAT DATANG

Jumat, 04 Juni 2010

coloring graph

soal coloring graph....
Seorang penjaga kantor baby sitter mendapat titipan 7 orang anak, A,B,C,D,E,F,dan G. Penjaga tersebut harus menentukan loker yang diberikan kepada setiap orangtua anak – anak tersebut sebagai tempat menyimpan peralatan mengasuhnya. Anak – anak tersebut tidak setiap waktu berada di kantor baby sitter tersebut, mereka datang dan pergi tergantung dari pesanan orang tua mereka. Karena loker di kantor tersebut terbatas dan harus digunakan sehemat mungkin, penjaga tersebut diminta untuk menentukan jadwal pemberian loker kepada setiap orang tua. Jadwal penitipan untuk setiap anak diberikan pada uraian berikut ini :
A          B           C           D          E          F         G
*         –           -            *           *          -           -         07:00
*        *            *           -            -         -           -        08:00
*         -             *          *            -         *          -        09:00
*         -              *          -            -         *          *        10:00
*         –              –          –            -          *          *       11:00
*         -              -          -            *           -          -      12:00
Tanda bintang (*) menggambarkan bahwa anak tersebut berada pada kantor pada waktu yang diberikan, sedangkan tanda strip (-) berarti bahwa anak tersebut tidak sedang dititipkan.
Tentukan bagaimana petugas tersebut harus menentukan loker mana yang diberikan kepada setiap orangtua.Jelaskan dalam bentuk uraian kejadian !
Berapa bilangan khromatiknya ?
Gambarkan Graph nya !

JAWABAN
























  Penjelasan : 


Orang tua bayi A,D,E akan menitipkan anaknya pada jam 07.00, dengan ketentuan:
orang tua bayi A akan menaruh peralatan bayi pada loker 1
orang tua bayi D akan menaruh peralatan bayi pada loker 4
orang tua bayi E akan menaruh peralatan bayi pada loker 2



Orang tua bayi A,B,C akan menitipkan anaknya pada jam 08.00, dengan ketentuan:
orang tua bayi A akan menaruh peralatan bayi pada loker 1
orang tua bayi B akan menaruh peralatan bayi pada loker 2
orang tua bayi C akan menaruh peralatan bayi pada loker 3



Orang tua bayi A,C,D,F akan menitipkan anaknya pada jam 09.00, dengan ketentuan:
orang tua bayi A akan menaruh peralatan bayi pada loker 1
orang tua bayi C akan menaruh peralatan bayi pada loker 3
orang tua bayi D akan menaruh peralatan bayi pada loker 4
orang tua bayi F akan menaruh peralatan bayi pada loker 2



Orang tua bayi A,C,F,G akan menitipkan anaknya pada jam 10.00, dengan ketentuan:
orang tua bayi A akan menaruh peralatan bayi pada loker 1
orang tua bayi C akan menaruh peralatan bayi pada loker 3
orang tua bayi F akan menaruh peralatan bayi pada loker 2
orang tua bayi G akan menaruh peralatan bayi pada loker 4



Orang tua bayi A,F,G akan menitipkan anaknya pada jam 11.00, dengan ketentuan:
orang tua bayi A akan menaruh peralatan bayi pada loker 1
orang tua bayi F akan menaruh peralatan bayi pada loker 2
orang tua bayi G akan menaruh peralatan bayi pada loker 4






Orang tua bayi A,E akan menitipkan anaknya pada jam 12.00, dengan ketentuan:
orang tua bayi A akan menaruh peralatan bayi pada loker 1
orang tua bayi E akan menaruh peralatan bayi pada loker 2
> Bilangan Kromatiknya adalah 4
Readmore »» coloring graph