Literatürde
Gossiping (Dedikodu Problemi) olarak geçen bir konu sorulmuş:
$n\geq 4$ kişi sayısını göstermek üzere, herkesin tüm bilgiye erişmesi için gerekli telefon görüşmesi sayısı $f(n) = 2n-4$ tür.
O halde sorunun yanıtı $f(6) = 2\cdot 6 - 4 = 8$ dir.
Bollobás'ın The Art of Mathematics kitabında ([1]) Gossiping Dons adlı problemin çözümünde anlatıldığı üzere, bu soru 1970'lerde popüler olmuş bir soruymuş.
Sorunun çözümünde iki temel aşama var:
Birincisi, minimum telefon görüşmesi sayısının $f(n) \leq 2n - 4$ olduğu;
İkincisi, $f(n) = 2n - 5$ görüşmede tüm bilginin paylaşılamadığı, yani $f(n)=2n-4$ olduğu.
Birinci aşama için birkaç çözüm paylaşacağım. İkinci aşama için sonda verdiğim kaynaklara müracaat edebilirsiniz. (Ya da birisi tüm çözümün çevirisini yapıp paylaşabilir.)
Açık şekilde; $f(1) = 0$, $f(2) = 1$.
$3$ kişi için, $A-B$, $A-C$, $B-C$, yani $f(3)=3$.
$4$ kişi için, $A-B$, $C-D$, $A-C$, $B-D$, $f(4)=4$.
$n$ kişi için yapılan görüşmeler $T_n$ listesi ile ifade edilsin. İlk görüşmedeki kişilerden biri $X_n$, son görüşmedeki kişilerden biri $Y_n$ olsun.
$(n+1).$ kişi $X_{n+1}$ olsun. $T_{n+1} = [X_{n+1}X_n] + T_n + [Y_nX_{n+1}]$ şeklinde bir görüşme ile $n+1$ kişi tüm bilgilere erişebilir.
Bu durumda her seferinde fazladan $2$ telefon görüşmesi ile kişi sayısını artırabildiğimiz ortaya çıkıyor. O halde $f(n) \leq 4 + 2(n-4) = 2n - 4$.
Burada $2n-4$ konuşma ile tüm bilgiyi paylaşabildiğimiz ortaya çıkıyor; ama daha az sayıda konuşma ile de belki tüm bilgi paylaşılabilirdi. Onun için $f(n) = 2n - 5$ konuşma ile tüm bilgiyi paylaşamayacağımızı göstermemiz gerekiyor. Sorunun bu kısmı daha zor.
$f(n) \leq 2n-4$ olduğu şu şekilde de gösterilebilir:
$n$ kişiden $4$ ü $A,B,C,D$ olsun. $A$ diğer $n-4$ kişi ile görüşsün.
Sonra $A,B,C,D$ kendi aralarında görüşsün. $f(4)=4$ olduğu için, $4$ görüşme yeterli olacak.
Sonra da $D$ diğer $n-4$ kişi ile görüşsün.
Bu durumda $(n-4)+4+(n-4) = 2n-4$ görüşmeyle herkes tüm bilgiye sahip olabilir.
Kaynaklar:[1]
Bollobás, B. (2006). The Art of Mathematics: Coffee Time in Memphis. Cambridge: Cambridge University Press. doi:10.1017/CBO9780511816574
Sayfa 136-139.
Google Kitaplar Linki[2]
Çeşitli Makaleler:
https://www.math.uni-bielefeld.de/~sillke/PUZZLES/gossips.pdf
