Hasil Pencarian  ::  Simpan CSV :: Kembali

Abstrak :
ABSTRAK
Diberikan sebuah graph terhubung tak berarah G = (V,E). Didefinisikan bahwa pohon bentukan T adalah suatu subgraph dari graph G yang mengandung semua simpul dari graph yang merupakan pohon. Diameter dari pohon bentukan T adalah jarak maksimum antara dua simpul sembarang dalam pohon. Dalam tugas akhir ini dibahas tentang bagaimana mendapatkan sebuah Pohon Bentukan Berdiameter Minimum (PBDM) dari sekumpulan n simpul. Untuk menyel esaikan masalah tersebut dibutuhkan waktu O(n3)

Abstrak :
ABSTRAK
Tesis ini membahas masalah subgraf planar maksimal yang mengandung subgraf tertentu. Subgraf tertentu yang dimaksud adalah graf terhubung yang derajat setiap verteksnya maksimum dua.

Pada tahun 1993, Cal, Han dan Tarjan menyusun sebuah algoritma Maximal Planar Subgrapha (algoritma CHT) untuk mencari subgraf planar maksimal dalam sebuah graf G. Algoritma CHT disusun berdasarkan algoritma Planarity Testing yang dikemukakan oleh Hopcroft dan Tarjan pada tahun 1974. Algoritma terakhir ini menggunakan Depth-First-Search (DFS) untuk menyatakan graf sebagai masukan. Graf hasil DFS ini mengandung satu atau lebih spanning tree yang disebut DFS-tree.

Algortima CHT tersebut diimplementasikan pada mesin SUNsparc berbasis UNIX(r) System V Release 4.0 di Fasilkom Universitas Indonesia dengan menggunakan bahasa C. Uji coba dilakukan pada graf komplit K? dengan n verteks clan beberapa graf sembarang. Dari uji coba pada graf komplit K. dengan n 5 diperoleh kesimpulan bahwa agar memperoleh subgraf planar maksimal dari K,,, jumlah sisi yang harus dihapus minimal adalah 112 (n2 - 7n a- 12).

Pada tesis ini, algoritma CHT dikembangkan untuk menentukan subgraf planar maksimal Gp dari sebuah graf G yang mengandung subgraf terhubung Gs yang derajat setiap verteksnya maksimum dua. Hal ini dilakukan dengan menjadikan G5 sebagai subtree dari salah satu DFS-tree dari G.