ISSN : 2460 – 7797 e-ISSN : 2614-8234 Website : jurnal.umj.ac.id/index.php/fbc
Email : fibonacci@umj.ac.id

## TREE LEECH
Hafnani 1) , Saiful Amri 1) , Mahmudi 1*)
1) Jurusan Matematika, Fakultas MIPA, Universitas Syiah Kuala, Banda Aceh, 23111
* mahmudi@unsyiah.ac.id

## Abstract
Setiap  dua  simpul  pada  pohon  terhubung  dengan  tepat  oleh  jalur.  Karena  jumlah  lintasan pada  pohon  sama  dengan  jumlah  pemilihan  dua  simpul,  kami  memiliki ( ) jalur  di  pohon dengan n simpul. Pohon tertimbang dengan n simpul yang berisi bobot 1, 2, 3,…, ( ) disebut Tree Leech. Dalam artikel ini, kami menunjukkan bahwa jika pohon dengan n simpul adalah Tree Leech, atau n-2 adalah kuadrat sempurna (Teorema Taylor). Selain itu, untuk pohon garis dan bentuk bintang, kami menunjukkan bahwa keduanya adalah Tree Leech untuk n=2, 3, 4.
Kata Kunci: Vertex, Edge, Weight, Path, Tree Leech

## PENDAHULUAN
Misal  pohon  ( tree ) terdiri  dari buah  simpul  ( vertex ).  Setiap  sisi  ( edge ) dalam  pohon  dapat  diberi  nilai  dengan suatu bilangan asli. Pemberian bilangan asli untuk  setiap  sisi  disebut  pembobotan dan setiap  bilangan  asli  yang  diberikan  itu disebut  bobot.  Dengan  memberi  bobot berbeda  pada  setiap  sisi,  tentu  saja banyaknya sisi akan sama dengan banyaknya bobot (Cohen, 1978). Pada tahun 1975,
John Leech
mengemukakan sebuah permasalahan terkait  dengan  pembobotan  pohon  yang kemudian  dikenal  dengan  pohon  Leech. Leech  menunjukkan  bahwa  untuk dan , pohon dapat memuat bobot lintasan  ( path ) ( ) Selebihnya, tidak diketahui apakah ada pohon lain yang
dapat diperlakukan demikian (Leech, 1975).  Permasalahannya  untuk yang bagaimana pohon memuat bobot lintasan
( ) ?
Berselang sekitar dua tahun kemudian atau  tepatnya  pada  November  1977, Herbert  Taylor  membuktikan  bahwa  jika pohon dengan simpul  merupakan pohon  Leech, maka atau
merupakan suatu bilangan kuadrat.
Selanjutnya,  pohon disebut  Memenuhi
Kondisi Taylor (MKT) bila ada pembobotan  pada sehingga memuat bobot ( ) (Taylor, 1977).
Ada  dua  buah  tipe  pohon  yang memiliki  ciri  mudah  untuk  dikenali,  yaitu pohon berbentuk garis dan pohon berbentuk bintang.  Tepatnya,  pohon  garis adalah
Volume 6 No. 1 Bulan Juni Tahun 2020
pohon  yang  dua  buah  simpul  berderajat dan simpul lainnya berderajat , sedangkan pohon  bintang adalah  pohon  yang  satu simpulnya  berderajat
dan  simpul lainnya  berderajat .  Baik  Leech  maupun Taylor,  tidak  membahas  kedua  tipe  pohon ini secara khusus.
Oleh  karena  itu,  dalam  tulisan  ini akan dikaji kembali mengenai Dalil Taylor, yaitu untuk “beberapa” , dipastikan bahwa pohon tidak  MKT.  Kemudian  khusus untuk  pohon  garis  dan  bintang  akan diselidiki  karakterisasi  dari agar  pohon yang demikian itu MKT.

## METODE PENELITIAN
Tulisan ini merupakan kajian literatur penelitian  bidang  matematika  teoritis, khususnya  tentang  teori  graf.  Penulis mempelajari  ulang  berbagai  dalil  yang terkait  dan  menulis  ulang  Dalil  Taylor. Penulis  juga  mencoba  mengumpulkan berbagai  sifat-sifat  tentang  pohon  Leech yang ada dalam literatur.

## HASIL DAN PEMBAHASAN
Misal pohon dengan banyaknya simpul . Sebarang pemetaan disebut  pembobotan  untuk ;  bilangan  asli
disebut bobot dari sisi . Pohon  dengan  pembobotan  seperti  ini ditulis  dengan atau  cukup dengan bila tidak dipersoalkan. Misal himpunan  semua  lintasan di pohon . Sebuah  sifat  yang  cukup  dikenal untuk  pohon  adalah  sebarang  dua  simpul dihubungkan  tepat  oleh  sebuah  lintasan. Misal dan adalah sebarang simpul di berdasarkan  sifat  ketunggalan  lintasan,
maka lintasan dengan titik ujung dapat ditulis  sebagai 〈    〉 . Dengan  demikian, diperoleh
{〈    〉           } dan
| |   ( )
Jika 〈    〉 ,  maka  didefinisikan sebagai  jumlah  bobot  dari  semua  sisi  yang ada di dalam 〈    〉 . Jadi

## ∑
〈   〉
dengan adalah  sisi  yang  berada  dalam lintasan 〈    〉 . Perlu  dicatat  bahwa terdefinisikan dengan baik sebab setiap dua simpul  (berbeda)  pada  pohon  dihubungkan tepat oleh sebuah lintasan.
Selanjutnya,  pohon disebut  MKT bila ada pembobotan , sehingga {        〈    〉    }   {         ( )} .
Sebagai contoh, kelima pohon pada gambar berikut MKT.
Gambar 1. Contoh pohon MKT
Untuk pohon ke- pada Gambar 1(d),
{          }      {            }
dengan pembobotan
terlihat  bahwa  pohon  tersebut mempunyai ( ) buah  lintasan  dengan bobot
(a) a (b) a (c) a
(d) (e)
FIBONACCI : Jurnal Pendidikan Matematika dan Matematika. Vol. 6 (1), pp: 39 - 44.

## yang memberikan kesimpulan
{        〈    〉    }   {           }
{         ( )}
Pohon  pada  Gambar  1(a),  1(b)  dan 1(c)  merupakan  pohon  garis,  Gambar  1(d) merupakan  pohon  bintang.  Pohon  1(a)  dan 1(b)  juga  merupakan  bintang.  Pohon  yang terakhir (1(e)) tidak termasuk garis ataupun bintang.
Herbert  Taylor  membuktikan  bahwa untuk beberapa dipastikan pohon bukan pohon Leech. Dengan menghitung banyaknya lintasan ganjil, Taylor
menemukan  bahwa  pohon dengan
simpul merupakan pohon Leech jika atau merupakan suatu kuadrat.
Berikut ini akan dituliskan  kembali pembuktian  Dalil  Taylor  dengan  struktur penulisan  yang  berbeda.  Yaitu,  dengan menyusun  dua  sifat  yang  digunakan  untuk membuktikan Dalil Taylor sebagai lemma.
Lemma  1 Misal Jika {       } maka Bukti. Misal adalah  sembarang  tiga simpul  berbeda  pada dan  diasumsikan 〈    〉   〈 〉 . Jika { } ,  maka  jelas  bahwa 〈    〉 〈               〉 dan . Karena  itu, Asumsikan { } . Dengan sifat  ketunggalan  lintasan,  dipastikan  ada
〈 〉 dengan 〈    〉
〈 〉 dan 〈    〉   〈 〉 .
Dengan  definisi sebagai  jumlah  dari
semua  bobot  sisi  pada 〈    〉 dapat dituliskan
sehingga
,
yaitu Lemma  2 Tinjau  pohon Ambil  sembarang Misal { } dan
adalah  bilangan  ganjil  jika  dan hanya jika satu  dari atau terletak di dan simpul lainnya di . Dengan kata lain, bila  semua  simpul  di diwarnai  dengan hitam dan semua simpul di dengan warna putih,  maka ganjil  jika  dan  hanya jika dan berbeda warna.
Bukti. Ambil  sembarang di dan asumsikan ganjil. Berdasarkan Lemma , Karena ganjil,  berakibat  satu  dari atau ganjil, sehingga jika maka atau  sebaliknya.  Sebaliknya, asumsikan satu dari atau di dan yang lain  di ;  sebutlah dan Maka ganjil dan genap, sehingga dari Lemma didapat  hubungan
Dalil 1 (Taylor) Jika pohon MKT,  maka atau berupa suatu kuadrat.
Bukti. Misalkan pohon MKT,  berarti T memuat  bobot  lintasan ( ) Buat dan seperti  pada Lemma .  Misal | | dan | |
Maka
dan  banyak  lintasan
dengan bobot ganjil pada adalah
Bila ( ) genap, maka
Volume 6 No. 1 Bulan Juni Tahun 2020
( )
sehingga
Di lain pihak, bila ( ) ganjil, maka
(( )    ) ( )
sehingga
Telah  dilihat  pada  Gambar bahwa
pohon dengan simpul adalah MKT untuk Berdasarkan  Dalil Taylor,  jelas  bahwa tidak  MKT  untuk untuk dan
adalah  dua terkecil yang belum diketahui apakah ada yang MKT.
Dua buah tipe pohon T , yaitu bintang dan garis, baik Leech maupun Taylor tidak membahasnya  secara  khusus. Dua  dalil berikut  memberikan  nilai agar dengan kedua tipe ini MKT.
Dalil 2 Tidak ada bintang
yang
MKT kecuali bila | |
Bukti. Untuk
jelas
MKT  seperti  yang  tampak  pada  Gambar untuk pohon yang ke- dan Selanjutnya  akan diselidiki  untuk  bintang dengan simpul.  Mudah  diperiksa bahwa harus ada sisi yang berbobot dan
4,  karena ( ) Karena  pohon  berupa bintang,  sehingga  lintasan  dengan  bobot tidak  bisa  dikonstruksi  dari  bobot-bobot
dan Jadi harus ada sisi yang berbobot
Dengan alasan serupa harus ada sisi yang
berbobot
Akibatnya  ada  dua  lintasan
yang  berbobot  sama,  yaitu dan Mustahil  pohon  yang  seperti  ini MKT.
Dalil  3 Tidak  ada  garis yang MKT  kecuali  untuk | | Bukti. Misal  pohon merupakan  garis.
memiliki
buah  sisi  dan ( ) buah lintasan.  Lintasan  dengan  bobot  terbesar adalah  lintasan  yang  memuat  semua  sisi pada dan bobot lintasan itu haruslah ( ) , karena merupakan garis. Karena
( ) , tentu  saja merupakan bobot  dari buah  sisi  pada Bobot lintasan telah diwakili oleh buah  sisi.  Tinjau  sisi  yang  berbobot .  Jika  sisi  ini  berdampingan  dengan  sisi berbobot  lebih  kecil  dari
maka  ada lintasan  yang  terdiri  dari  kedua  sisi  ini berbobot  lebih  kecil  dari padahal sembarang  bobot  yang  lebih  kecil  dari telah ada (yaitu bobot dari suatu sisi). Dengan  demikian  sisi  yang  berbobot harus  berdampingan  dengan  sisi  berbobot Sekarang  lintasan  dengan  bobot telah diwakili oleh sisi dengan bobot dan sisi  dengan  bobot .  Dengan  alasan
serupa,  sisi  berbobot hanya  dapat berdampingan  dengan  sisi  yang  berbobot Selebihnya,  tidak  ada  lagi  sisi  yang bisa dipasangkan dengan sisi yang berbobot Jadi, garis MKT hanya mungkin bila memiliki  maksimum  tiga  buah  sisi,  yaitu dan Dengan  maksimum  tiga buah  sisi,  ini  hanya  dipenuhi  oleh Bukti  ini  sekaligus  menyimpulkan bahwa  sisi  yang  berbobot dan berderajat
FIBONACCI : Jurnal Pendidikan Matematika dan Matematika. Vol. 6 (1), pp: 39 - 44.
Nilai terkecil yang belum diketahui apakah pohon MKT adalah Berdasarkan    Dalil dan jelas  bahwa
pohon
dengan simpul  tidak  MKT  untuk  tipe  garis
dan  bintang,  namun  hal  itu  sama  sekali tidak  menunjukkan  bahwa  pohon tidak MKT  untuk  tipe  yang  lain.  Untuk menyelidiki apakah dengan
MKT,
haruslah diketahui dengan jelas bentuk dari tersebut. Ada formula untuk menentukan berapa  banyak  pohon  berbeda  dengan namun  tidak  ada  metode  untuk mengetahui dengan tepat bagaimana tipenya.  Tanpa  mengetahui  dengan  tepat bentuk pohon, mustahil melakukan pembobotan  agar  pohon  MKT.  Dengan alasan  ini,  tentu  saja  akan  sulit  dan membutuhkan  waktu  yang  tidak  dapat dipastikan untuk menyelidiki secara manual atau  dengan  bantuan  komputer  apakah dengan MKT.

## SIMPULAN
Berdasarkan  hasil  dan  pembahasan dapat disimpulan tidak ada bintang
yang MKT kecuali bila
| | dan tidak ada garis yang MKT kecuali untuk | |

## DAFTAR PUSTAKA
Cohen, Daniel I.A. 1978. Basic Techniques of  Combinatorial  Theory .  John
Willey & Sons Inc, Canada.
Leech,  John. 1975. Another Tree Labelling
Problem. The American Mathematical Monthly. Vol. 82, pp:
923 - 925.
Taylor, Herbert. 1977. Odd Path Sums in an Edge-Labeled  Tree. The  American Mathematical  Monthl. Vol.  50,  pp:
258 - 259.
Volume 6 No. 1 Bulan Juni Tahun 2020