• Document: Aplikasi Graf pada Penentuan Jadwal dan Jalur Penerbangan
  • Size: 2.88 MB
  • Uploaded: 2018-12-07 07:16:54
  • Status: Successfully converted


Some snippets from your converted document:

Aplikasi Graf pada Penentuan Jadwal dan Jalur Penerbangan Hishshah Ghassani - 13514056 Program Studi Teknik Informatika Sekolah Teknik Elektro dan Informatika Institut Teknologi Bandung, Jl. Ganesha 10 Bandung 40132, Indonesia hishshah@students.itb.ac.id Abstrak— Pesawat terbang merupakan salah satu Jadwal dan jalur penerbangan harus disusun dengan transportasi yang sering digunakan oleh masyarakat baik oleh maskapai penerbangan, selain untuk Indonesia, terutama mereka yang sering berpergian ke luar meminimalkan kecelakaan, juga karena mempengaruhi kota dengan jarak yang sulit ditempuh dengan transportasi efisiensi dan keuntungan bagi maskapai tersebut. Salah darat. Untuk meminimumkan kecelakaan di udara, maka harus penentuan jadwal dan jalur penerbangan harus satu metode yang dapat digunakan dalam menentukan diatur sedemikian sehingga tidak ada pesawat yang jadwal dan jalur penerbangan adalah dengan teori graf. bertabrakan. Makalah ini menawarkan salah satu ide cara Graf adalah kumpulan simpul-simpul (vertex) yang untuk menentukan jadwal dan jalur penerbangan, dengan dihubungkan dengan sisi (edge). Satu sisi dapat menggunakan teori graf. Dengan metode pewarnaan graf, mengubungkan satu simpul yang sama. Sisi yang seperti dapat ditentukan jalur dan jadwal yang bisa saja itu disebut gelang (loop). Dua sisi atau lebih juga dapat mengurangi jumlah kecelakaan. Selain pewarnaan graf, dibutuhkan juga algoritma-algoritma pendukung seperti menghubungkan dua simpul yang sama. Sisi-sisi tersebut algoritma Greedy dan algoritma Dijkstra untuk disebut sisi ganda. menentukan jalur terpendek dan efisien. Penerapan graf dalam kehidupan sangat banyak. Selain penentuan jadwal dan jalur transportasi, graf juga dapat Kata Kunci— graf, jadwal, jalur, pewarnaan graf, digunakan dalam bidang jaringan komunikasi, rangkaian algoritma Greedy, algoritma Dijkstra. listrik, turnamen round-robin, permodelan vending machine, dan lain-lain. I. PENDAHULUAN II. TEORI DASAR Banyaknya maskapai penerbangan yang beroperasi A. Teori Graf setiap waktunya menyebabkan pengaturan jadwal dan Graf biasanya digunakan untuk merepresentasikan jalur penerbangan menjadi tidak mudah. Menurut objek diskrit dan menghubungkan objek-objek tersebut. Wikipedia, jumlah maskapai penerbangan di Asia saja Graf terdiri dari simpul dan sisi. Suatu graf dapat G = (V, sudah mencapai lebih dari 100 maskapai. Banyaknya E). Graf dinyatakan sebagai graf kosong apabila tidak ada jumlah maskapai tersebut menyebabkan banyak pesawat sisi di antara simpul-simpul yang ada. Graf mungkin yang beroperasi pada satu waktu, sehingga kemungkinan memiliki arah dan mungkin juga berbobot. Graf berarah terjadinya kecelakaan di udara cukup besar apabila adalah graf yang tiap sisinya memiliki orientasi arah, penentuan jadwal dan jalur penerbangan tidak diatur sedangkan graf berbobot adalah graf yang tiap sisinya dengan baik. Oleh karena itu, dibutuhkan suatu metode memiliki bobot tertentu. agar jadwal dan jalur penerbangan dapat diatur sedemikian sehingga tidak terjadi kecelakaan di udara. (a) (b) (c) Gambar 1. Lalu lintas udara di daerah Asia Tenggara Gambar 2. (a) Graf Sederhana. (b) Graf Berarah. (c) Graf Berbobot Makalah IF2120 Matematika Diskrit – Sem. I Tahun 2015/2016 Terdapat beberapa terminologi graf, di antaranya: simpulnya. 1. Ketetanggaan (Adjacent) Dua simpul yang bertetangga adalah simpul yang dihubungkan dengan satu sisi yang sama. 2. Bersisian (Incidency) Suatu sisi bersisian dengan simpul-simpul yang dihubungkannya. 3. Simpul Terpencil (Isolated Vertex) Gambar 5. Graf lengkap Simpul terpencil adalah simpul yang tidak memiliki sisi yang bersisian dengannya. 4. Graf Bipartit 4. Derajat (Degree) Graf bipartit adalah graf yang himpunan simpulnnya Derajat

Recently converted files (publicly available):