Perpustakaan Digital ITB

Abstrak : Diberikan suatu graf G = (V, E) dengan V(G) himpunan titik dan E(G) himpunan sisi. Tentukan nilai terkecil k sedemikian sehingga semua titik dan sisinya dapat dilabeli dengan bilangan 1, 2, ..., k (label dapat berulang) dan mempunyai sifat bahwa bobot setiap sisi pada G berbeda. Nilai k itu disebut dengan kekuatan total sisi tak beraturan dari G, yang dinotasikan dengan tes(G). Pada tesis ini, kita akan mengkaji sifat umum dari kekuatan total sisi tak beraturan pada sebarang graf. Khususnya, untuk beberapa kelas graf kita telah menemukan nilai tes(G) yaitu pada graf lintasan. graf buku, graf bintang, graf bipartit lengkap, dan beberapa graf gabungan.