PELABELAN KONSEKUTIF PADA GRAF-GRAF POHON

Abstract

. Pelabelan graf berkembang sangat luas dan dapat digunakan untuk merancang model sinar-X kristalografi, sistem alamat jaringan komunikasi dan circuit design. Salah satu macam pelabelan pada araf adalah pelabelan pada titik dan sisinya, misalnya pelabelan konsekutif. Pelabelan konsekutif ini idenya dad pelabelan araceful pada araf pohon yang dikemukan oleh Skater. Misal G araf dengan p titik dan q sisi Pelabelan konseklitif pada graf G adalah pemetaan satu-satu dan pada dari gabungan titik dan sisi pada graf G ke bilangan hulat positif (1, 2, 3. ... , n , n + 1 n + q} , dimana pelabelan sisinya merupakan harga mutlak dad selisih antara label dua titik yang hertetangga. Dalam tugas akhir ini dibahas bagaimana mencari pelabelan konsekutif pada araf sederhana dan araf hingaa, khususnya araf pohon. Graf pohon mempunyai beberana kelas khusus, diantaranya graf lintasan, graf bintang, dan araf katerpilar. Sehubungan dengan ide Slater bahwa araf potion yang graceful adalah konsek-utif, maka dapat disimpulkan klasifikasi sebagai berikut: kelas graf lintasan P„, kelas graf bintang Sr, dan araf katerpilar Cry, merupakan graf konsekutif.