digilib@itb.ac.id +62 812 2508 8800

ABSTRAK.pdf:??_
PUBLIC Dwi Ary Fuziastuti

Misalkan G adalah suatugrafterhubungsederhanadan W adalah subhimpunan titik dari G. Representasimultisetdarititik v 2 G terhadap W, ditulis rm(vjW), didefinisikan sebagaimultisetjarakantaratitik v dengansetiaptitikdi W. Jika setiap titikdi G memiliki representasimultisetyangberbedaterhadap W maka W disebutmultisetpembeda.Multisetpembedadengankardinalitasterkecildisebut basis multisetsedangkankardinalitasdaribasismultisetdisebutdimensimultiset dan dinotasikandengan md(G). Jika G tidak memilikimultisetpembedamaka md(G) = 1. Dalam penelitianinidikajialgoritmaheuristikuntukmenentukandimensimultiset dari suatugraf.Algoritmatersebutkemudiandiimplementasikanuntukmenen- tukan dimensimultisetsemuagrafterhubungsederhanadenganorde2sampai10. Selain itu,algoritmainijugadigunakanuntukmenentukandimensimultisetgraf bukuberukurankecil.Hasiltersebutkemudiandigunakanuntukmendugadimensi multiset beberapakelasgrafbuku.Dapatditunjukkanbahwaterdapatgrafbuku dengandimensimultisetkonstandantakhingga