JAWABAN :
1.
Manfaat Coloring
: Problema pemberian warna kepada semua simpul, sedemikian sehingga 2 simpul
yang berdampingan (ada ruas yg menghubungkan ke dua simpul tsb) mempunyai warna
yang berbeda. Dimana banyak warna yang diminta seminimal mungkin.
2.
a.
b.
Jalur yang bersilangan :
Ö AC bersilangan dengan BA, BD, CB, DB
Ö AD bersilangan dengan BA, CA, DB
Ö BA bersilangan dengan AC, DB
Ö BD bersilangan dengan AC, CB, CA, DC
Ö CB bersilangan dengan AC, BA, BD, DC
Ö CA bersilangan dengan AD, BD, DB, DC
Ö DB bersilangan dengan AC, AD, BA, CA
Ö DC bersilangan dengan AD, BD, CB, CA
c.
Jalur yang lampunya selalu hijau : AB,
BC, CD, DA