Bir Tane Rastgele Çizge Var!




Yüklə 47.95 Kb.
tarix22.04.2016
ölçüsü47.95 Kb.

Bir Tane Rastgele Çizge Var!



Bir çizge (ya da bir başka adıyla, graf), sezgisel olarak, noktalardan ve bu noktaları ikişer ikişer birleştiren (doğru ya da eğri) çizgilerden oluşur. Herhangi iki nokta birleşmek zorunda değildir. Örneğin,

yedi noktalı bir çizgedir. Noktalara 1, 2, 3, 4, 5, 6, 7 adlarını verdik. Birleştirdiğimiz noktalar şunlar:

{1, 2}, {1, 3},{1, 4},{1, 6},{3, 5},{5, 6},{5, 7},{6, 7}.

Bu iki öğelik kümelere bağıntı adı da verilir. Noktaları nasıl bir çizgiyle birleştirdiğimiz önemli değil. Hatta çizgiler kesişebilir bile (kesiştikleri yere çizgenin bir noktasını koymayız o zaman.) Noktaların yerleri de önemli değil. Okur neyin önemli olduğunu merak edebilir! Önemli olan hangi noktayla hangi nokta arasında çizgi (ya da bağıntı) olduğu. Başka bir şey önemli değil. Örneğin, yukardaki çizgeyle aşağıdaki çizgeler aynı çizgelerdir:



Bu yazıda ilginç olduğu kadar da şaşırtıcı bir teorem kanıtlayacağız. Size sonsuz tane nokta verdim:

1, 2, 3, 4, 5, 6, 7, 8,...

noktalarını. Bu noktalardan bir çizge yapmanızı istiyorum. Çizgeyi şöyle yapacaksınız: Her iki nokta için yazı-tura atacaksınız. Yazı gelirse o iki noktayı birleştireceksiniz, tura gelirse birleştirmeyeceksiniz. Her iki nokta için yazı-tura atmayı bitirdiğinizde (!) noktaların adlarını silin. Hangi noktanın 1 noktası, hangi noktanın 2 noktası olduğu belli olmasın. Elinizde adsız noktalar ve noktalar arasında (yukarda “bağıntı” diye adlandırdığımız) birtakım çizgiler kalacak. Ben de aynı şeyi yapacağım. Sizin çizgenize bakmadan... Böylece adsız iki rastgele çizge elde edeceğiz. Sizin rastgele çizgeniz ve benimkisi... Şimdi çizgelerimizi karşılaştıralım. İki çizgenin de aynı olduklarını göreceğiz. Tıpatıp birbirine benziyorlar! Sanki biri öbürünün hık demiş burnundan düşmüş. İnanılır gibi değil ama doğru! Ne sihirdir ne keramet, matematiktir matematik!

Dahası var. Diyelim, ben noktaları birleştirmek için yazı-tura atmadım da zar attım. 6 geldiğinde noktaları birleştirdim, gelmediğinde birleştirmedim. Sizse yazı-tura attınız. Noktaların adlarını sildiğimizde gene aynı çizgeleri elde ederiz!

“Çizge” kavramının matematiksel tanımıyla başlayalım:



N bir küme olsun. N’ye noktalar kümesi diyeceğiz. B, N’nin iki öğelik altkümelerinden oluşan (hepsini içermek zorunda değil) bir küme olsun. B kümesine bağıntılar kümesi adını verebiliriz1. (N, B) çiftine çizge denir. Yukardaki örnekte, noktalar kümemiz

N = {1, 2, 3, 4, 5, 6, 7}

ve bağıntılar kümemiz



B = {{1, 2}, {1, 3}, {1, 4}, {1, 6}, {3, 5}, {5, 6}, {5, 7}, {6, 7}}

olarak alınmıştır.

Rastgele çizgelerden sözetmeden önce az noktalı çizgeleri bulalım. Eğer N = {1} ise, yani N’de yalnızca bir nokta varsa, B boşküme olmak zorunda. Dolayısıyla N = {1} üzerine bir tek çizge kurulabilir. İşte o çizge:

Şimdi de iki noktalı çizgelere bakalım. N = {1, 2} olsun. Bu durumda B ya boşkümedir ya da {{1, 2}} kümesidir. Demek ki iki noktalı iki çizge var:



Şimdi amacımız üç noktalı çizgeleri bulmak. Ama bu çizgelerden çok olduğundan, arada unuttuklarımız kalmasın diye önce n noktalı kaç tane çizge olduğunu bulalım. n noktalı, tane çizge olduğunu iddia ediyorum ve hemen kanıtlıyorum: N noktalar kümesinin n tane öğesi varsa (yani n tane noktamız varsa), N’nin tane, yani n(n–1)/2 tane iki öğeli altkümesi vardır2. B iki öğelik altkümelerden oluştuğundan, B bağıntılar kümesi için 2n(n–1)/2 seçeneğimiz var3. Demek ki n noktalı 2n(n–1)/2 tane çizge vardır. Eğer n = 3 olarak alırsak, bundan 3 noktalı 8 tane çizge olduğu anlaşılır. Bu 8 çizgeyi teker teker bulalım. N = {1, 2, 3} olsun. İşte 8 çizge:



Üç nokta arasındaki bağıntıları yazı-tura atarak karar verecek olursak, yukardaki çizgelerden herbirini elde etme olasılığı 1/8’dir.

Bu çizgelerdeki noktaların adlarını, yani sayıları silersek, çizge sayımız azalır. Örneğin, bir bağıntısı olan üç çizgenin noktalarının adları silindiğinde bir çizge olurlar. Bunun gibi, iki bağıntısı olan üç çizgeden de bir adsız çizge elde ederiz. Böylece noktaların adlarını sildiğimizde geriye dört çizgemiz kalır:

Eğer çizgeyi yazı-tura atarak bulmuşsak, yani her bağıntının olasılığı 1/2 ise, bu adsız çizgelerin olasılıkları sırasıyla 1/8, 1/8, 3/8 ve 3/8’dir.

İki çizgenin noktalarının adlarını sildiğimizde aynı çizgeyi elde etmek ne demektir? Bunun matematiksel tanımını bilmek bu yazı için gerekli değildir, bu yazı için sezgiler yeterlidir. Bir örnek daha verelim ki kuşkuya yer kalmasın. Aşağıdaki iki çizgeye bakalım.



Bu iki çizge birbirlerine çok benzerler. Tek ayrımları noktalarının adlarıdır. Soldaki çizgede 3 ve 4 noktalarının yerlerini değiştirirsek (bağıntılarıyla birlikte) sağdaki çizgeyi buluruz. Yani noktaların adları olmasaydı iki çizge arasında bir ayrım olmayacaktı. Soldaki çizgenin bağıntıları şunlar:



B = {{1, 2}, {2, 4}, {4, 3}, {3, 1}}.

Sağdaki çizgenin bağıntılarıysa,



B = {{1, 2}, {2, 3}, {3, 4}, {4, 1}}.

Şimdi, f(1) = 1, f(2) = 2, f(3) = 4, f(4) = 3 göndermesini (fonksiyonunu) ele alalım. Bu gönderme, B bağıntılarını B bağıntılarına gönderiyor. İşte iki çizgenin noktalarının adları silindiğinde aynı çizge bulunması bu demektir4.

Dört noktalı ve adsız çizgeleri bulalım. Bunları bağıntı sayısına göre bulabiliriz: önce hiç bağıntısı olmayanlar, sonra bir bağıntısı olanlar, sonra iki bağıntısı olanlar...

Çizgelere iliştirilen 1/64, 6/64, 12/64 gibi sayılar, bağıntılara karar vermek için yazı-tura atıldığında çizgenin elde edilme olasılığıdır. Yukarda yaptığımız hesaplardan, 4 noktalı çizge sayısının 243/2 = 26 = 64 olduğunu biliyoruz. 4 noktalı ve bir bağıntılı kaç çizge vardır? Dört noktadan ikisini seçip aralarına bir bağıntı koymamız gerekiyor. Demek ki = 6 tane bir bağıntılı çizge var. Herbirinin olasılığı 1/64 olduğundan, bir bağıntılı çizge elde etme olasılığımız 6/64’dır5.

Şimdi sonsuz rastgele çizgelere gelelim. N kümesi, 1, 2, 3, 4,... gibi pozitif doğal sayılardan oluşan küme olsun. Bunlar noktalarımız. İki nokta arasında bağıntı olup olmadığına karar vermek için yazı-tura atacağız. Böylece bir bağıntılar kümesi elde edeceğiz. Bu çizgeye R adını verelim (R, “rastgele”nin R’si.) R çizgesi hakkında ne söyleyebiliriz? Rastgele çizge olduğundan hiçbir şey bilmemiz olası değil diye düşünebilir okur. İlk bakışta öyle bile görünse, ikinci bakışta R çizgesi üzerine çok şey bildiğimiz anlaşılır.

Basit bir örnekle başlayayım. Rastgele çizgenin herhangi iki noktası arasındaki “uzaklığın” en fazla iki olduğunu, yani bir noktadan bir başka noktaya üçüncü bir noktadan geçilerek (bağıntıları izleyerek elbet) gidilebileceğini kanıtlayayım.



R rastgele çizgesinde herhangi iki nokta alalım; diyelim 1 ve 2 noktalarını. Savım şu: Öyle bir üçüncü nokta vardır ki, bu üçüncü nokta hem 1 noktasıyla, hem de 2 noktasıyla bağıntılıdır. Savımı kanıtlayayım. 3 noktasını ele alalım. Eğer şanslı bir günümdeysem, 3 noktası dilediğim gibi bir noktadır, yani hem 1 noktasıyla, hem de 2 noktasıyla bağıntılıdır. Bunun böyle olma olasılığı 1/4. Demek ki 1/4 olasılıkla, 3 noktası varlığını iddia ettiğim noktalardan biri olacak. Öte yandan 3/4 olasılıkla 3 noktası istediğim gibi bir nokta olmayacak. Şimdi 3 ve 4 noktalarını ele alalım. Bu iki noktadan hiçbirinin dilediğim gibi bir nokta olmama olasılığı (3/4)2 tür. Eğer n tane nokta alırsak, bu n noktadan hiçbirinin dilediğim gibi bir nokta olmama olasılığı (3/4)n tür. Ama n büyüdükçe (3/4)n azalıyor, sıfıra yakınsıyor. Demek ki, 3, 4, 5, 6,... noktalarından hiçbirinin benim istediğim gibi bir nokta olmama olasılığı

limn (3/4)n = 0,

ve en az birinin benim istediğim gibi bir nokta olma olasılığı

limn (1 – (3/4)n) = 1.

Dolayısıyla 1 olasılıkla dilediğim gibi bir nokta vardır.

Rastgele çizgeler üzerine bir başka sonuç daha kanıtlayalım. R, rastgele çizgeniz olsun. Noktaların adlarını silin. Sonra herhangi bir sonlu çizge alın, örneğin yazının başında örnek olarak sunduğumuz 7 noktalı çizgeyi. Onun da adlarını silin. Bu adsız ve sonlu çizgeye S adını verelim. S sonlu çizgesi, rastgele çizgenizin bir altçizgesidir, yani S çizgesini R çizgesinin içinde bulabilirsiniz. Neden?

Şu nedenden: Rastgele çizgenizin noktalarını yedişer yedişer ayırın. Örneğin şöyle (noktaların adlarını silmiştik; aşağıdaki sayılar noktaların adları değil; yalnızca birbirinden değişik noktalar olduğunu vurgulamak için kullanıyoruz bu sayıları):

R1 = {1, 2, ..., 7}

R2 = {8, 9, ..., 14}

...


Rn = {7n + 1, 7n + 2, ..., 7n + 7}

R1 altçizgesine bakalım. Bu çizgenin S çizgesi olma olasılığı en az 1/276/2 (neden?), olmama olasılığıysa en fazla 1 – 1/276/2. Bu son olasılığa  diyelim.

0 <  ≤ 1 – 1/276/2 < 1

eşitsizliklerine dikkatinizi çekerim. R1 çizgesinin S çizgesi olmama olasılığı . R1 ve R2 çizgelerinden hiçbirinin S çizgesi olmama olasılığıysa 2. Genel olarak, R1, ..., Rn çizgelerinden hiçbirinin S çizgesi olmama olasılığı n; en az birinin S olma olasılığıysa 1 – n. , 1’den küçük olduğundan, n sayıları n arttıkça küçülüp 0’a yakınsarlar6. Dolayısıyla 1 – n sayıları 1’e yakınsar. Sonsuz tane Rn çizgesi olduğundan, bunlardan birinin S olma olasılığı 1’dir. Dolayısıyla, R çizgesinde S’ye tıpatıp benzeyen bir altçizge (1 olasılıkla, yani yüzde yüz) vardır.

Son olarak yazının başında iddia ettiğim savı kanıtlayayım. Sizin elinizde rastgele bir çizge var. Bu çizgeye R = (N, B) diyelim, noktalarınız da



a1, a2, a3, a4,...

olsun. Benim çizgeye R = (N, B) diyelim. Noktalarım



a1, a2, a3, a3,...

olsun. Bu iki çizgenin noktalarının adlarını değiştireceğim. a ve a noktalarını b ve b yapacağım. Ve bu ad değiştirmeyi öyle yapacağım ki, noktaların adlarını sildiğimizde iki çizgenin birbirinin aynısı olduğu apaçık belli olacak. Bağıntılara dokunmayacağım. Yalnızca eski adları silip yeni adlar koyacağım yerine, daha sonra bu yeni adları da sileceğim.



Gelgit yöntemi denilen kullanacağım yöntem, daha çok matematiksel mantıkta kullanılır.

Birinci Adım. Birinci adımda dişe dokunur bir şey yapmayacağız. R çizgesinden başlayalım işe. a1 noktasına b1 diyelim bundan böyle. R çizgesinde b1’e benzeyen bir nokta bulabilir miyiz? Elbette! Herhangi bir nokta b1’e benzer. Örneğin a1 noktası. Bundan böyle a1 noktasına b1 adını verelim. Çizgelerimizin noktaları şimdilik şöyle:

R:

b1

a2

a3

a4

a5

...

R:

b1

a2

a3

a4

a5

...


İkinci Adım. Şimdi R çizgesine geçelim. a2 noktasına b2 diyelim bundan böyle. Ve {b1, b2} altçizgesine bakalım. b1 ve b2 arasında bağıntı olabilir ya da olmayabilir. R çizgesinde öyle bir an noktası bulmak istiyorum ki {b1, an} çizgesiyle {b1, b2} çizgesi – noktalarının adları dışında – birbirinin aynı olsun. Diyelim b1 ve b2 arasında bir bağıntı var. O zaman, R çizgesinde öyle bir an noktası seçmeliyim ki, an noktasıyla b1 noktası arasında bağıntı olsun. Böyle bir an noktası bulabilir miyim? 1 olasılıkla bulabileceğimi iddia ediyorum. R çizgesinin hiçbir noktasının b1 noktasına bağıntılı olmama olasılığı sıfırdır. Bu şöyle anlaşılır. m herhangi bir doğal sayı olsun. a2, a3, ..., am+1 noktalarından hiçbirinin b1 noktasıyla bağıntısı olmamasının olasılığı 1/2m dir. Sonsuz tane noktamız olduğundan, noktalardan hiçbirinin dilediğim gibi bir nokta olmama olasılığı limm 1/2m = 0 dır. Demek ki, 1 olasılıkla dilediğim gibi bir nokta vardır. Bu nokta a2 olmayabilir, a3 olmayabilir, belki a4 de olmayabilir, ama bir tanesi b1’e bağıntılı olacak. R çizgesinde böyle bir nokta seçelim. Diyelim a4 noktası b1 noktasına bağıntılı. a4 noktasına bundan böyle b2 diyelim. Şimdi

{b1, b2} ve {b1, b2}

altçizgeleri – noktalarının adları dışında – birbirinin aynıdır.

Eğer b1 ile b2 arasında bağıntı yoksa, R çizgesinde b1 ile bağıntısı olmayan bir nokta seçilir ve bu noktaya b2 adı verilir.

Çizgelerimizin noktalarını yeni adlarıyla sıralayalım:


R:

b1

b2

a2

a3

a5

a6

a7

...

R:

b1

b2

a3

a4

a5

a6

a7

...



Üçüncü Adım. R çizgesine geri dönelim. a2 noktası; R çizgesinin adı değiştirilmeyen ilk noktası. Bu noktayı b3 yapalım ve {b1, b2, b3} altçizgesine bakalım. Diyelim, b3 ile b1 bağıntılı, ama b2 ile bağıntılı değil. R çizgesinde öyle bir an noktası bulacağız ki an noktası b1 ile bağıntılı olacak ama b2 ile bağıntılı olmayacak. Eğer öyle bir anbulabilirsek,

{b1, b2, b3} ve {b1, b2, an}

altçizgeleri, noktalarının adları dışında, aynı çizge olacaklar.


R:

b1

b2

b3

a3

a5

a6

a7

...

R:

b1

b2

b3

a3

a4

a5

a7

...
Böyle bir an noktası bulabilir miyiz? Evet! Biri olmazsa, bir başkası olmak zorunda. Çünkü a3, a4, ..., am+2 noktalarından hiçbirinin dilediğimiz gibi bir nokta olmama olasılığı (3/4)m dir ve m sonsuza gittiğinde bu olasılık 0’a gider. Demek ki dilediğimiz gibi bir an noktası bulma olasılığımız 1’dir. Diyelim a6 noktası işimizi görüyor. a6 noktasının adı bundan böyle b3 olsun. Çizgelerimizin noktaları şimdi şöyle:
Dördüncü Adım. Bu kez R çizgesinden işe başlayacağız. Adını değiştirmediğimiz ilk nokta a3. Bu noktaya b4 diyelim bundan böyle. Şimdi R çizgesinde öyle bir an noktası bulalım ki,

{b1, b2, b3, b4} ve {b1, b2, b3, an}

altçizgeleri – noktaların adlarını dikkate almazsak – aynı çizge olsunlar. Öyle bir an noktası 1 olasılıkla bulunabilir. Nasıl bulunur? Yukardaki gibi... Hiçbir an noktasının istediğimiz gibi bir nokta olmaması olasılığı sıfırdır. Demek ki birinin dilediğimiz gibi bir nokta olma olasılığı birdir.

Böylecene sürdürürüz. Tek sayılı adımlarda R çizgesinden, çift sayılı adımlarda R çizgesinden başlarız. Bu yöntemle ne benim çizgemden ne de sizin çizgenizden nokta unutulmaz.

Sonsuza dek sürdürdüğümüzde, noktalarımız b ve b harfleriyle yazılmış olur ve her n için,

{b1, ..., bn} ve {b1, ..., bn}

altçizgeleri, adları dışında, birbirinin aynısıdır. Dolayısıyla, {b1, b2, b3,...} ve {b1, b2, b3,...} çizgeleri arasında – noktalarının adları dışında – hiç ama hiçbir ayrım yoktur.

Demek ki R ve R çizgeleri arasında  noktalarının adları dışında  bir ayrım yoktur.

Ne kanıtladık? Sizin rastgele çizgenizle benim rastgele çizgem birbirinin eşidir. 1 olasılıkla!

Hatta şunu da söyleyebilirim: R çizgesinden bir noktayı ve bu noktanın bütün bağıntılarını silersek, elde ettiğimiz çizge de rastgele bir çizge olur, yani başlangıçtaki çizgeyle  noktalarının adları dışında  bir ayrım yoktur.




1 N, “nokta”nın N’si, B ise “bağıntı”nın B’si.

2 sayılarını Pokerin Matematiği başlıklı yazıda tanımlamıştık.

3 Sayfa 39’da m öğesi olan bir kümenin 2m tane altkümesi olduğunu kanıtlamıştık. Burada m yerine alıyoruz.

4 Bunu matematiksel olarak ifade edelim: (N, B) ve (N,B) iki çizge olsunlar. Eğer, f(B) = B eşitliğini sağlayan ve birebir ve örten olan bir f: NNgöndermesi varsa, (N, B) ve (N, B) çizgelerine eşyapısal çizgeler denir. İki eşyapısal çizgenin birbirinden tek ayrımı noktalarının adlarıdır. Bu çizgelerden birindeki noktaların adları uygun bir biçimde değiştirildiğinde (x noktasına f(x) denildiğinde örneğin), öbür çizge bulunur.

5 Yukardaki 11 çizge rastgele konulmamıştır. Altalta gelen çizgeler birbirleriyle ilintilidir. Üst kattan herhangi bir çizgeyi alalım. Bu çizgenin bağıntılarını silelim ve bağıntı olmayan yerlere bağıntı koyalım. Böylece alt kattaki çizgeyi elde ederiz. En sağdaki çizge için aynı şeyi yapacak olursak gene aynı çizgeyi elde ederiz. Altalta gelen iki çizgenin olasılıkları aynıdır. Yazı-tura atıldığında aynıdır. Eğer zar atarak bağıntılara karar verecek olursak olasılıklar değişebilir. Örneğin, zar attığımızda 6 gelirse bağıntı koymaya, gelmezse bağıntı koymamaya karar verecek olursak, çizgenin bağıntı sayısı çoğaldıkça olasılığı azalır.

6 Eğer sayısı 0 ≤ < 1 eşitsizliklerini sağlıyorsa, n sonsuza gittiğinde, rn sayıları sıfıra yakınsarlar. Bunu Yakınsamak başlıklı yazıda açıklamıştık.


Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azrefs.org 2016
rəhbərliyinə müraciət

    Ana səhifə