Jump to content
Sign in to follow this  
-_-

Pohon bermuatan sempurna

Recommended Posts

Suatu graf disebut pohon bila graf itu terhubung dan tidak memiliki siklus (cycle). Suatu pohon disebut pohon bermuatan bila setiap sisinya diberi bilangan real. Jarak dua verteks $x$ dan $y$ pada suatu pohon bermuatan didefinisikan sebagai jumlah bilangan-bilangan pada sisi-sisi lintasan (path) yang menghubungkan verteks $x$ dan $y$. Suatu pohon bermuatan yang mempunyai tepat $n$ verteks dikatakan sempurna jika untuk setiap $k\in \mathbb{N}$ dengan $k\leq \binom{n}{2}$ terdapat dua verteks berbeda di pohon bermuatan tersebut yang jaraknya $k$. Tunjukkan bahwa jika ada pohon bermuatan sempurna yang mempunyai tepat $n$ titik, maka $n$ atau $n-2$ adalah kuadrat sempurna.

 

Tes 3 Nomor 4 Pelatnas Tahap 3 IMO 2016

Share this post


Link to post
Share on other sites

Saya pernah liat soal ini untuk kasus Bipartite (beserta solusinya) ntah dimana. Saya coba re-create solusinya (karena setiap tree adalah bipartite)

 

Pertama-tama perhatikan bahwa tree dengan $n$ verteks pasti mempuyai $n-1$ buah edge (ini pasti ada di lecture Teori Graf dan buktinya pakai Induksi).  Kita misalkan setiap edge pada tree tersebut mempunyai label $\{e_1, \cdots , e_{n-1}\}$. 

 

Lemma Jika $T$ sempurna  maka $e_i \in \mathbb{N}$ untuk setiap $i$.

 

Bukti :  

 

Misalkan $\mathcal{V}=\{ \{v,w\} :   \, v,w \in V\}$ yakni himpunan semua pasangan verteks dari $T$, dan misalkan $A=\left\{1,\cdots, \frac{n(n-1)}{2}\right\}$ . Maka $|\mathcal{V}| = \frac{n(n-1)}{2} = |A|$. Misalkan ada $e_k$ yang bukan bilangan asli, katakanlah $e_k$ menghubungkan verteks $r$ dan $s$. Perhatikan bahwa $\{r,s\} \in \mathcal{V}$ dan $e_k \not\in A$, menurut definisi soal $r$ dan $s$ mempunyai panjang $e_k$.  

Dengan demikian setiap $ d \in A \cup \{e_k\}$ terdapat paling sedikit satu pasangan verteks di $\mathcal{V}$ yang berjarak $d$.  Sedangkan $A \cup \{e_k\}$ mempunyai $n(n-1)/2+1$ buah anggota dan  $\mathcal{V}$ mempunyai $n(n-1)/2$ anggota, jadi dengan PigeonHole principle terdapat sepasang verteks katakanlah $x$ dan $y$ yang mempunyai dua jarak, kontradiksi. 

 

 

Kita akan melakukan algoritma pewarnaan sebagai berikut:

 

  • STEP 1 :  Ambil sebuah verteks $x_0$,  warnai $x_0$ dengan warna pink. 
  • STEP 2 :  Ambil salah satu dari tetangga dari $x_0$, katakanlah $x_1$, jika jarak $x_0$ dan $x_1$ genap maka warnai $x_1$ juga pink, jika jarak  mereka   ganjil warnai $x_1$ ungu. Lakukan pewarnaan dengan aturan yang sama dengan tetangga dari $x_1$, katakanlah $x_2$. Kemudian untuk $j \geq 2$ ambil salah satu tetangga dari $x_j$ katakanlah $x_{j+1}$ dan warnai dengan aturan yang sama. 

Karena tree tidak mempunyai cycle, maka algoritma diatas akan berhenti dan menghasilkan sebuah rantai 

\[x_0 - x_1 - \cdots - x_{k}\]

 

Kita lakukan algoritma diatas dengan tetangga lain dari $x_0$ (jika ada) selain $x_1$. Jika semua tetangga dari $x_0$ sudah habis, maka kita lakukan algoritma yang dengan mulai dari tetangga-tetangga $x_0$  (generasi kedua).

 

Singkatnya pewarnaan tersebut mewarnai tree dari atas yaitu $x_0$ ke $x_1$ terus sampai paling bawah yaitu $x_k$ lalu kemudian mulai lagi dari atas (tetangga lain dr $x_0$) sampai ke bawah lagi dan begitu terus menerus. 

Karena $T$ tidak memuat cycle, maka setiap kali kita melakukan pewarnaan seperti itu tidak ada verteks yang terwarnai dua kali.  Dan karena $T$ terhubung, maka semua verteks akan terwarnai.

 

Sekarang perhatikan bahwa dari pewarnaan diatas, himpunan verteks  $V$ terpartisi menjadi dua yaitu $V= P \cup U$ dimana $P$ yang berwarna pink dan $U$ berwarna ungu.  Misalkan $|P|=p$ dan $|U|=u$, maka berlaku $p+u=n$.

 

Dua verteks katakanlah $x$ dan $y$ berjarak ganjil jika dan hanya penjumlahan label edge yang menghubungkan $x$ dan $y$ adalah ganjil, jika dan hanya jika,  terdapat ganjil buah angka ganjil pada penjumlahan tersebut jika dan hanya jika terjadi perubahan warna sebanyak ganjil kali, jika dan hanya jika $x$ dan $y$ berbeda warna.  

Jadi banyaknya $x$ dan $y$ yang berjarak ganjil sama dengan banyaknya pasangan yang berbeda warna yaitu $|P| \times |U|  = p \times u$.

  • Jika $\frac{n(n-1)}{2}$ genap, maka pada $\{1, \cdots , n(n-1)/2\}$ terdapat $\frac{n(n-1)}{4}$ buah angka ganjil, jadi banyak jarak yang ganjil adalah

     

    \[\begin{align*}\frac{n(n-1)}{4} = p u &\Leftrightarrow  (p+u)(p+u-1) = 4pu  \\ &\Leftrightarrow p^2+u^2 - 2pu  = p+u =n  \\  &\Leftrightarrow  n = (p-u)^2 \end{align*}\]

 

jadi $n$  bilangan kuadrat.

 

  • Jika $\frac{n(n-1)}{2}$ ganjil, maka pada $\{1, \cdots , n(n-1)/2\}$ terdapat $\frac{\frac{n(n-1)}{2}+1}{2}$ buah angka ganjil, jadi banyak jarak yang ganjil adalah

     

    \[\begin{align*}\frac{n(n-1)}{4} +\frac{1}{2} = p u &\Leftrightarrow  (p+u)(p+u-1) = 4pu-2\\ &\Leftrightarrow p^2+u^2 - 2pu  = p+u-2 =n-2  \\  &\Leftrightarrow  n-2 = (p-u)^2\end{align*}\]

Jadi $n-2$ bilangan kuadrat. 

 

        

Edited by Adri
  • Upvote 1

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this  

×