Subgraf planar maksimal yang mengandung subgraf dengan derajat setiap verteks maksimum dua
Atik Wintarti;
Belawati H. Widjaja, supervisor
([Publisher not identified]
, 1997)
|
|
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. |
 T9954-Atik Wintarti.pdf :: Unduh
|
| No. Panggil : | T-Pdf |
| Entri utama-Nama orang : | |
| Entri tambahan-Nama orang : | |
| Entri tambahan-Nama badan : | |
| Subjek : | |
| Penerbitan : | [Place of publication not identified]: [Publisher not identified], 1997 |
| Program Studi : |
| Bahasa : | ind |
| Sumber Pengatalogan : | LibUI ind rda |
| Tipe Konten : | text |
| Tipe Media : | computer |
| Tipe Carrier : | online resources |
| Deskripsi Fisik : | vi, 48 pages : illustration ; 30 cm + appendix |
| Naskah Ringkas : | |
| Lembaga Pemilik : | Universitas Indonesia |
| Lokasi : | Perpustakaan UI, Lantai 3 |
| No. Panggil | No. Barkod | Ketersediaan |
|---|---|---|
| T-Pdf | 15-18-094642552 | TERSEDIA |
| Ulasan: |
| Tidak ada ulasan pada koleksi ini: 78944 |
