Agustus 4, 2020
Sistem Informasi

PROBLEMA DAN MODEL GRAPH DALAM METODE GREEDY

ICON CREATOR MEDIA MAKET CREATOR

Supported by: Jasa Maket by MaketCreator.com

 

1. PEWARNAAN ( COLORING )
Problema pemberian warna kepada semua simpul, sedemikian sehingga 2 simpul yang berdampingan ( ada ruas menghubungkan ke dua simpul tersebut ) mempunyai warna yang berbeda .Banyak warna yang dipergunkan , diminta seminimal mungkin

Langkah-langkah penyelesaian masalah :

  1. Tentukan simpul dari perjalanan yang diperbolehkan ( untuk peletakan simpulnya bebas )
  2. Tentukan ruas untuk menghubungkan 2 simpul yg menyatakan 2 perjalanan yg saling melintas.
  3. Beri warna pada setiap simpul dengan warna
    warna baru.
    – Bila Simpul berdampingan maka berilah warna
    lain.
    – Bila simpul tidak bedampingan maka berilah
    warna yang sama
  4. Kita lihat Bahwa simpul AB , BC dan ED tidak dihubungkan oleh suatu ruas jadi untuk simpul tersebut tidak pernah melintas perjalanan-perjalanan lain dan simpul tersebut selalu berlaku lampu hijau
  5. Tentukan pembagian masing –masing simpul yang
    sudah diberikan warna.
    Putih = ( AC, AD )
    Hitam = ( BD, EB )
    Merah = ( EC )
    Catatan :
    Pembagian simpul berdasarkan simpul yang tidak langsung berhubungan seminimal mungkin ( BISA DILAKUKAN DENGAN BEBERAPA KEMUNGKINAN )
  6. Dari langkah ke 5 diperoleh 3 fase, sehingga bisa kita simpulkan keseluruhan situasi dan hasilnya.