PROBLEMA DAN MODEL GRAPH DALAM METODE GREEDY

PROBLEMA DAN MODEL GRAPH DALAM METODE GREEDY

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.

How useful was this post?

Click on a star to rate it!

Average rating / 5. Vote count:

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
Sistem Informasi