Perpustakaan Digital ITB

Suatu subgraf-lintasan panjang n, P_n (k)=(VP,EP), dari suatu graf terhubung G=(V,E) disebut k-lintasan-pusat dari G (untuk suatu n,k?Z_(?0)), jika berlaku: untuk setiap v? V terdapat v^'? VP sedemikian sehingga d(v,v^' )? k. Graf Lobster adalah graf pohon yang memuat 2-lintasan-pusat dan pohon-berakar dua-tingkat adalah graf lobster yang memuat 2-lintasan-pusat panjang 0. Multiset representasi suatu titik v terhadap himpunan tak kosong W? V adalah multiset dari jarak antara titik v dan titik-titik pada W, dinotasikan r_m (v|W). Jika r_m (u?W)? r_m (v|W) untuk setiap pasangan titik berbeda u dan v di G, maka W disebut himpunan pembeda dari G. Lebih jauh, jika G memiliki himpunan pembeda, maka kardinalitas dari himpunan pembeda terkecil disebut dimensi multiset dari G (dinotasikan md(G)). Jika G tidak memiliki himpunan pembeda, md(G)=?. Dalam tugas akhir ini, dibahas syarat perlu dan cukup bagi pohon-berakar dua-tingkat untuk memiliki dimensi multiset bernilai hingga. Selain itu, dibahas pula syarat perlu untuk graf lobster memiliki dimensi multiset bernilai hingga.