Matematik Atölyesi – Graf #3

Pardon, sizi tanıyor muyum?

1928 yılında Frank Ramsey bir matematik problemiyle uğraşıyordu. Bu genç matematikçi uğraştığı problemi çözebilmek için yepyeni bir matematik branşını başlatmak zorunda kalmıştı. Maalesef Frank Ramsey bulgularını açıkladığı makale henüz yayımlanmadan 27 yaşında hayatını kaybetmişti. Fakat genç yaşında hayata veda etmesine rağmen Ramsey ölümsüz olmayı başarmıştı: Çünkü bugün bahsi geçen matematik branşına Ramsey Teorisi diyoruz.

Ramsey teorisinde temel sorulardan biri şudur: Kaosun (ya da rastgeleliğin) olduğu bir ortamda her zaman düzen bulunabilir mi? (Burada kaostan kasıt düzensizliktir.)

220px-Frank_Plumpton_Ramsey
Frank Ramsey (1903-1930)

Ramsey teorisi matematiğin mantık branşının bir alt dalı gibi görünse de bu yeni branşın bir çok uygulama alanı vardır. Bunlardan biri hemen hemen Ramsey teorisiyle aynı zaman diliminde ortaya çıkan çizge teorisidir.

Bu yazıda iki branşı bir araya getiren bir sorudan bahsedeceğim.

İhtiyaç Duyulanlar: Rastgele seçilmiş altı kişi.

Kaos: Altı kişi içinde bulunanların hangilerinin arkadaş, hangilerinin birbirine yabancı olduğu. (Arkadaş olmak iki yönlüdür: Sean Connery’i filmlerden tanıyor olmanız onunla arkadaş olduğunuz anlamına gelmez.)

Aranan Düzen: Bu altı kişi içinde herhangi üç kişinin birbiriyle arkadaş çıkması veya herhangi üç kişinin birbirine yabancı olması.

IMG_6185

Altı kişinin grafını çizelim. Grafta noktalar kişileri, düz çizgi arkadaş olmayı, kesik çizgiyse yabancı olmayı ifade etsin.

IMG_6186

Peki kaos nerede diye sorabilirsiniz. Altı kişi için arkadaş olup olmama ihtimali 30.000’den fazladır. Yani bu graf 30.000’den fazla ihtimalden sadece birini gösteriyor.

220px-Rasputin_PA
Rasputin herkesi tanır…

Grafta üç kişinin arkadaş olması düz çizgili üçgen; üç kişinin yabancı olmasıysa kesik çizgili üçgenle gösterilmiş olur. O halde grafın içinde üçgenleri aramamız gerekiyor. Şekilde de görüldüğü üzere bu altı kişinin içinde her iki üçgenden de bulunuyor: Örneğin Bill-Rasputin-Lewinsky bir arkadaş üçgeni oluştururken Alexandra-Lewinsky-Hürrem bir arkadaş olmayanlar üçgeni oluşturur.

Peki çizilebilecek her grafta (30.000’den fazla olduğunu hatırlayın) arkadaş olan veya olmayan üçlü bulunur mu?

Evet

Her ihtimali tek tek denemek imkansız olduğuna göre bir ispat yöntemi bulmak gerekir.

Sadece Rasputin’i ele alalım. Rasputin herkesle arkadaş olsaydı arkadaş sayısı 5, yabancı olduğu kişi sayısı ise 0 olurdu. Eğer 4 kişiyle arkadaş olsaydı, 1 kişiyle yabancı olurdu. Bu ihtimallerin tamamı aşağıdaki gibidir:

Bu ihtimaller sadece Rasputin değil, gruptaki herkes için geçerlidir. Buradan şu çıkarımı yapabiliriz: Gruptaki herkeste hep en az 3 arkadaş veya yabancı (arkadaş değil) ilişkisi vardır.

Hadi biz Rasputin’in üç kişiyle arkadaş olduğu durumu ele alalım:

IMG_6188

Bu durumda Rasputin ile arkadaş üçgeni oluşturmamak için Lewinsky-Hürrem-Alexandra birbirleriyle tamamen yabancı olmalıdır.

IMG_6189
Bu durumda Lewinsky-Hürrem-Alexandra bir üçgen yaratır.

Fakat üç kişinin arkadaş olmaması bu sefer kesik çizgili bir üçgeni sağlar. Bu da altı kişi için geçerli olan 30.000’den fazla ihtimalin tamamında en az bir tane üç arkadaş veya yabancı olduğunu gösterir.

Lewinsky-Hürrem-Alexandra üçgenini bozduğumuzda bu sefer Rasputin ile iki kadını kapsayan bir üçgen oluşuyor.

Bi’ Göz Atmakta Fayda Var

5 kişilik bir grupta herhangi 3 kişinin arkadaş çıkması veya herhangi 3 kişinin arkadaş çıkmaması ihtimali var mıdır?

M. Serkan Kalaycıoğlu

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s