Banyak Sub Pohon k Titik dari Pohon yang Derajat Titik-Titiknya Diketahui

EasyChair Preprint 4988

Abstract

Misalkan S dan T merupakan pohon dengan |S| = k. Notasi c(S, T) adalah banyaknya copy S dalam T. Banyaknya sub pohon dari T dengan jumlah k titik dan pengertian banyaknya copy S pada T merupakan unsur penting dalam menentukan profil dari pohon secara lokal. Misalkan d = (d₀, d₁, d₂, ..., d_n) adalah barisan tidak naik dari derajat semua titik pada pohon. Himpunan pohon yang derajat titik-titiknya bersesuaian dengan d dinotasikan dengan T_d. Pohon T_d^* yang bersesuaian dengan d dan memiliki jumlah yang maksimum sub pohon dengan k titik dapat dikonstruksi. Langkah pertama adalah menetapkan titik yang bersesuaian dengan derajat d₀ sebagai akar dari pohon. Sebanyak s₁ = d₀ titik-titik pada level pertama adalah titik-titik yang bersesuain dengan d₀ suku berikutnya pada barisan derajat. Sebanyak s₂ = d₂ + d₃ + ... + - s₁ titik-titik pada level kedua yang bersesuaian dengan sebanyak s₂ suku berikutnya pada barisan derajat. Untuk titik-titik pada level ketiga dan selanjutnya dilakukan sama dengan pada level kedua. Pohon  adalah pohon yang mempunyai jumlah sub-pohon dengan  k titik terbanyak dari semua pohon pada T_d.

Keyphrases: optimal trees, profiles, trees, well-ordering

@booklet{EasyChair:4988,
  author    = {Efron Manik},
  title     = {Many Sub Trees k Dots from the Tree Where the Degrees of the Points are Known},
  howpublished = {EasyChair Preprint 4988},
  year      = {EasyChair, 2021}}