Teori Graf

Posted on

Sebuah  graf  dapat di sebut  sebagai  kumpulan  titik  yang  disebut  simpul   dan  dihubungkan  oleh  garis yang  disebut  busur.  Graf  dapat  di gunakan  sebagai   cara  yang  sangat  sederhana untuk  memodelkan  banyak  jaringan.  Sebagai  contoh,  sebuah  jaringan  komunikasi dapat  dimodelkan  ke  dalam  bentuk  graf ,  dengan  simpul  menyatakan  pusat komunikasi  (contohnya,  saluran  tel epon)  dan  busur  menyatakan  jaringan komunikasi  (contohnya,  saluran  telegraf).  Dalam  memodelkan  sebuah  jaringan dengan  graf ,  simpul  dalam  graf  umumnya  dinyatakan  dalam  bentuk  titik  yang menyatakan  asal  aliran  serta  tempat  berakhir  (contohnya,  stasiun  kereta  api , terminal ,  pabrik,  gudang,  dan  lain-lain).  Busur  dalam  graf   secara  umum menyatakan  saluran  di   mana  komoditas  berakhir  (contohnya,  trayek  kereta  api , rute penerbangan, ali ran pipa, dan  lain-lain).

Sebuah  graf  memberi kan  model  struktural  dari   jaringan.  Dalam kebanyakan  jaringan, metode konstruksi   biasanya  dinyatakan oleh harga, efisiensi, kehandalan dan kapasitas.

Dalam  menggambarkan  graf ,  simpul   digambarkan  dengan  lingkaran  kecil atau  titik  tebal   dan  busur  digambarkan  dengan  garis,  dan  arah  panah  pada  garis melambangkan  arah dari  garis tersebut. Nomor atau nama  simpul dapat diletakkan di  dalam  lingkaran kecil atau di  tepi  titik tebal .

Busur  (i , j )  disebut  busur  berarah  jika  terdapat  suatu  aliran  dari  simpul  i menuju  ke  simpul  j .  Dalam  hal  ini  simpul  i  disebut  simpul  awal ,  sumber  atau pangkal  dan  simpul  j   disebut simpul akhir, ujung, tujuan,  atau terminal dari  busur (i ,  j ).  Jika  tidak  terdapat  aliran  dari   simpul  i  ke  simpul  j ,  maka  busur  (i ,  j )  disebut busur tidak berarah.

graf1

Graf   yang  memiliki  bobot pada  setiap  busurnya disebut jaringan.  Oleh  karena  itu,  pada  umumnya  graf  dinotasi kan  dengan  G (V, E) dan  jaringan dinotasi kan dengan G(V, E, W).

Jaringan  komunikasi  jika  dibuat  dalam  bentuk  graf ,  maka  simpul melambangkan pusat komunikasi dan busur melambangkan  link komunikasi.

Contoh Penerapan Graf :

  • Persoalan Penghubung

Sebuah  jaringan  komunikasi  (contohnya,  jaringan  tel epon)  yang menghubungkan  n pusat atau kota T1, T2, …, Tn harus diinstall . Masing-masing pusat  mampu  untuk  menerima  dan  menyalurkan  informasi.  Jadi  dua  pusat dapat  berkomuni kasi   secara  langsung  maupun  tidak  langsung.  Diberikan contoh nxn  matriks  C=[cij] dimana cij merupakan harga penginstalan jaringan  komuni kasi  (contohnya,  jaringan  telepon)  antara  pusat Ti  danTj, disusun menjadi sebuah  jaringan untuk mencapai dua tujuan berikut :

(i)  sedikitnya dua pusat  yang dapat berkomunikasi, dan

(ii)  jumlah biaya  instalasi   adalah  minimum.

Berdasarkan  Persoalan  Penghubung  di  atas,  jika  n  =  6,  dan  matriks  biayanya adalah :

Graphic1

Graf   yang  digambarkan  berdasarkan  matri ks  di  atas  adalah  di  bawah  ini :

Graphic1

Biaya  yang  bertanda  ∞  artinya  pusat  yang  berhubungan  tidak  dapat berkomunikasi  secara  langsung,  sehingga  kita  dapat  menghilangkan  busur tersebut dari  graf  kita.

  • Persoalan Lintasan Terpendek

Perhatian  khusus  di tujukan  untuk  menemukan  rute  terpendek  antara pasangan  pusat  dalam  sebuah  jaringan.  Contohnya,  sebuah  perusahaan  bisnis besar dengan kantor pusat di  New York mempunyai   beberapa cabang utama dinegara-negara  seluruh  dunia.  Kantor  pusat  mengkoordinasi  seluruh  kegiatan operasi  perusahaan,  dan  setiap  hari  seluruh  informasi  (meliputi   permintaan, penawaran  dan  biaya)  harus  diberikan  dari  kantor  pusat  ke  kantor-kantor cabang. Informasi  yang ada dikirimkan  via teleks. Diberikan  biaya pengiriman pesan  melalui  teleks  antara  dua  perusahaan,  dan  di tentukan  rute  komunikasi termurah dari  kantor pusat dan setiap kantor cabang lainnya.

Perusahaan  perbankan  dengan  kantor  pusat  di  New  York  (NY)  dan  kantor cabang  di   Paris(P),  Zurich (Z),  Berlin (B),  Tokyo (T),  Hongkong(HK)  dan Sydney (S).  Setiap  hari   informasi   penting  (meliputi   permintaan,  penawaran dan  biaya)  harus  diberikan  dari  kantor  pusat  ke  kantor-kantor  cabang.

Informasi  yang  ada  di kirimkan  via  teleks.  Biaya  pengiriman  pesan  antara  dua kantor cabang diberikan dalam matri ks di   bawah  ini  :

Graphic1

Graf   yang  digambarkan  berdasarkan  matriks  di  atas  adalah

Graphic1

Model   graf   ini  memberi kan  himpunan  semua hubungan  yang  mungkin  dan  permasalahannya  adalah  memilih  sebuah himpunan  bagian  dari   himpunan  ini  yang  menunjukkan  bahwa  jaringan  yang ada  sesuai  dan  jumlah  biaya  dari   pengi riman  informasi  dari   kantor  pusat  ke kantor cabang dapat diminimalkan

Materi Presentasi silakan didownload : Graf

One thought on “Teori Graf

    Diskripsi Matakuliah Matematika Diskrit | Wawan Laksito said:
    Oktober 30, 2013 pukul 6:57 pm

    […] Materi 3 […]

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s