Hayatta olduğu gibi matematikte de küçük seçimlerin büyük sonuçları olabilir. Bu, özellikle nesnelerin ağlarını ve aralarındaki bağlantıları inceleyen bir alan olan grafik teorisi için geçerlidir. İşte nedenini anlamanıza yardımcı olacak küçük bir bilmece.

Altı nokta verildiğinde amacınız, herhangi bir nokta çifti arasında her zaman bir yol olması ve hiçbir yolun iki çizgi parçasını aşmaması için bunları çizgi parçalarıyla birbirine bağlamaktır. Bir an için kaydırmayı bırakın ve bir çözüm bulmaya çalışın.

Çözdüyseniz, bahse girerim şuna benzer bir şeye sahipsiniz:

Bunun gerçekten bulmacanın gereksinimlerini karşıladığına dikkat edin. Herhangi iki nokta arasında bir yol vardır - grafik teorisyenlerinin köşe dediği şey - ve hiçbir yol iki çizgi parçasından veya kenardan uzun değildir. (Not: Bulmacada ve sütun boyunca, yolların aynı kenarı birden fazla kullanmasına izin verilmez.) Çözümünüz biraz farklı görünebilir, ancak sonunda aynı temel yapıyı elde edeceksiniz ve köşeleri biraz hareket ettirirseniz bunu görmek daha kolay olacaktır.

Grafik teorisindeki bu "yıldız" yapısı, diğer köşe gruplarının her birine tek bir kenarla bağlanan ve diğer köşeler arasında kenar olmayan bir merkezi köşeye sahiptir. Bu yıldız sadece yapbozumuz için bir çözüm değil; tek çözüm bu. (Sütunun sonundaki alıştırmalarda bunu kanıtlama şansınız olacak.)

Bu bilmece, 3 veya daha uzun yolları yasaklamak gibi yerel kısıtlamaların bazen yıldız gibi küresel yapıları sonuç olarak ortaya çıkmaya nasıl zorlayabildiğini göstermektedir. Bunun gibi ilişkilerden yararlanmak, özellikle belirli önemli yapıları ararken grafikleri ve ağları anlamak için güçlü bir araç olabilir.

Böyle bir yapı, bir "klik"tir - her tepe noktasının bir kenarla diğer tüm tepe noktalarına doğrudan bağlandığı bir dizi köşe noktasıdır. Klikler önemlidir çünkü maksimum bağlantı ve bağımlılık alanlarını tanımlarlar. Örneğin, bir havayolu rotaları ağında, bir klik, her iki yönde doğrudan uçuşlarla birbirine bağlı bir grup şehri temsil eder. Bu, ağdaki bir güç kaynağıdır, çünkü tek bir uçuşta herhangi bir şehre ulaşabilirsiniz ve bir rota iptal edildiğinde herhangi bir varış noktasına görece kolaylıkla bağlanabilirsiniz.

Buna karşılık, bir "anti-klik", hiçbirinin diğerine doğrudan bağlı olmadığı bir dizi köşe noktasıdır. Bir uçuş haritasında bu, aralarında doğrudan uçuş olmayan bir grup şehri temsil eder. Yine de A noktasından B noktasına bir anti-klik içinde gidebilirsiniz, ancak doğrudan değil. Önce grup dışına seyahat etmeniz gerekecek, bu nedenle oraya varmak size mal olacak: zaman, para veya daha genel olarak verimlilik. Bir bakıma, klikler karşıtları bir ağda maksimum bağımsızlığa sahip alanları tanımlar ve bu nedenle bağımsız kümeler olarak da bilinirler. (Bu setlerin başka yerlerde "cocliques" veya "stabil setler" olarak anıldığını da görebilirsiniz.)

Büyük klikler veya büyük bağımsız kümeler bulmak, hatta var olduklarını garanti etmek, grafikleri ve ağları analiz etmenin önemli bir parçası haline geliyor. İşte burada Erdős-Hajnal varsayımı devreye giriyor. Bu, grafiklerde belirli yerel yapıları yasaklarsanız, o zaman belirli küresel yapıların - özellikle, nispeten büyük klikler veya nispeten büyük bağımsız kümelerin - kaçınılmaz olduğunu söylüyor. Birçok açık sorudan biri Paul Erdős'e atfedilen, binlerce işbirlikçiyle kahve ve varsayımlar paylaşarak dünyayı dolaşan ünlü matematik göçebesi. Erdős-Hajnal varsayımı geçerli olduğunda, biyoloji, lojistik ve bilgisayar bilimi gibi çeşitli alanlardaki bilim adamlarının ağlarının küresel yapıları hakkında daha da güçlü sonuçlar çıkarmak için kullanabilecekleri bilgiler sağlar.

Aslında Erdős-Hajnal varsayımını zaten iş başında gördük. Orijinal bulmacamızda yıldız şekli kaçınılmazdı ve ortaya çıktığı üzere, bu şekil büyük bir bağımsız kümeyi garanti ediyor. Yıldızın merkezine bağlı beş köşenin birbiriyle başka bağlantısı yoktur. Bu bağımsız kümeyi, merkezi köşeyi ve ona bağlanan kenarları göz ardı ederek görebilirsiniz.

Bu bağımsız kümenin varlığının bizi ağımızdaki bir güvenlik açığına karşı uyardığına dikkat edin. Bu bir uçuş haritası olsaydı ve o merkez şehre ulaşılamaz hale gelseydi, hiç kimse herhangi bir yere uçamazdı.

Bulmacamızda, 3 veya daha uzun uzunluktaki yolların yerel yapısını yasaklamak, 5 boyutlu bağımsız bir diziyi garanti eder. Ancak, bu bulmaca, Erdős-Hajnal varsayımının yapmadığı bir şeye, yani herhangi iki köşe arasında bir yolun var olduğuna dayanır. Bu, grafiğin "bağlı" olması gerektiği anlamına gelir ve bu, Erdős-Hajnal varsayımının bir parçası değildir. Böyle bir grafik mutlaka bağlı değilse, büyük bir bağımsız küme kaçınılmaz mıdır?

Grafiğimizde büyük bir bağımsız kümeden kaçınıp kaçınamayacağımızı görmek için, bir matematikçi gibi düşünelim ve uç durumları dikkate alarak başlayalım. Her şeyi bağlamamız gerekmiyorsa, ya hiçbir şeyi bağlamazsak?

Hiç kenar eklememek aslında bize mümkün olan en büyük bağımsız kümeyi, altı köşenin tümünü verir. Aslında, bir kenara bağlanmayan herhangi bir köşe, onu büyütmek için mevcut herhangi bir bağımsız kümeye eklenebilir, bu nedenle daha küçük bağımsız kümeler elde etmek için muhtemelen her köşenin en az bir kenara sahip olmasını isteriz. Böyle bir şeye ne dersin?

Bu grafik iki parçalıdır ve her parçanın ucundaki iki köşeyi seçerek bağımsız bir 4 boyutlu set elde edebilirsiniz. Seçilen dört köşeden hiçbirinin diğerlerine bir kenarla bağlı olmadığına ve böylece bağımsız bir küme oluşturduğuna dikkat edin.

Böyle bir grafik nasıl olur?

Bu grafik bağlantısız üç parçadan oluşuyor ve her parçadan bir tepe noktası seçerek bağımsız bir 3 boyutlu set elde edebilirsiniz.

Bu, verilen koşullar altında elde edebileceğimiz en küçük bağımsız küme olarak ortaya çıkıyor. Başka bir deyişle, altı köşeli bir grafikte, 3 uzunluğundaki yolları yasaklamak, orijinal grafiğin boyutunun en az yarısı kadar olan bağımsız bir kümeyi garanti eder ve bu, grafikler söz konusu olduğunda oldukça büyüktür.

Aslında daha genel bir şeyler oluyor. Keşfettiğimiz tüm grafiklerin önemli bir ortak noktası var: Hepsi yıldız koleksiyonları!

Soldaki grafik, her biri üç köşeli iki yıldızdır ve sağdaki grafik, her biri iki köşeli üç yıldızdır. Kenarları olmayan grafik bile, her biri bir köşeye sahip altı yıldız olarak düşünülebilir. 3 uzunluğundaki yolları yasaklayan kural, grafiği bir yıldızlar koleksiyonu olmaya zorlar ve bu, altı köşeyle veya 600 köşeyle başlasanız da geçerlidir. Dolayısıyla, bağımsız kümeler bulmaya gelince, tek soru, kaç tane bağlantısız yıldızla sonuçlanacağınızdır.

Genel olarak, çok fazla yıldızınız varsa, büyük bir bağımsız set elde etmek kolaydır. Yıldızlar birbirine bağlı olmadığından, her yıldızdan sadece bir tepe noktası seçebilirsiniz, bu da en az yıldız sayısı kadar bağımsız bir kümeyi garanti eder. Yukarıdaki sağdaki örnekte, 2 büyüklüğündeki üç yıldızın her birinden bir tepe noktası alabilir ve 3 boyutunda bağımsız bir küme oluşturabilirsiniz.

Öte yandan, yalnızca birkaç yıldızla sonuçlanırsanız, yıldızların kendileri orijinal grafikteki tüm köşeleri hesaba katacak kadar büyük olmalıdır ve bir yıldızdan nispeten büyük bir bağımsız kümenin nasıl elde edileceğini zaten gördük - sadece merkezi tepe noktası dışında her şeyi alın. Örneğin, bir grafik yalnızca iki yıldızdan oluşuyorsa, o zaman yıldızlardan birinin orijinal grafiğin köşelerinin en az yarısını içermesi garanti edilir ve bu, orijinal grafiğin boyutunun kabaca yarısı kadar bağımsız bir kümeyi garanti eder. Bağlantısız yıldızlardan bağımsız kümeleri birleştirerek örneğimizde daha da büyük bir bağımsız küme oluşturabiliriz. (Mümkün olan en büyük bağımsız küme ne kadar küçük olabilir? Bununla ilgili daha fazla bilgi için alıştırmalara bakın.)

Genel olarak, bağlantısız yıldızların bir koleksiyonundan oluşan bir grafik için, büyük bir bağımsız küme kaçınılmazdır. Büyük yıldızlar, büyük bağımsız kümeler oluşturur, ancak küçük yıldızlar, aynı zamanda büyük bağımsız kümeler de oluşturan çok sayıda yıldız anlamına gelir. Bu yaklaşım sadece bizim basit örneğimizde işe yaramıyor. Ayrıca daha karmaşık bir sorunun nasıl ele alınacağını da önerir.

ile bir grafiğiniz olduğunu varsayalım. n ve aşağıdaki yerel kısıtlamayı uygularsınız: Hiçbir üç köşe birbirine bağlanamaz. Bu, yerel olarak gereksiz rotaları en aza indirmeyi hedefleyen bir uçuş haritası tasarlamaya benzer. A ile B arasında ve B ile C arasında gidebiliyorsanız, A ile C arasında ayrı, doğrudan bir rota oluşturmanıza izin verilmez.

Başka bir deyişle, 3 boyutlu klikler olamaz. Geometri açısından, grafik "üçgensizdir".

Üçgensiz bir grafiğin nispeten büyük bir bağımsız kümesi olmalı mı? Cevap evet ve daha önce olduğu gibi sır yıldızlarda yatıyor. Üçgen içermeyen bir grafiği şu şekilde gösterebiliriz: n köşe noktaları, grafik teorisi standartlarına göre nispeten büyük olan, en azından kabaca $latex sqrt{n}$ boyutunda bağımsız bir kümeye sahip olmalıdır. Örnek olarak aşağıdaki üçgensiz grafiği kullanarak argümanı inceleyelim.

Grafikteki herhangi bir köşeyi seçerek ve tüm komşularını - ona bir kenarla bağlı olan köşeleri - göz önünde bulundurarak başlayın.

Seçtiğiniz tepe noktasının bu komşularının hiçbiri birbirine bağlı değil - çünkü bu bir üçgen olur ve bu üçgensiz bir grafiktir - yani her köşe ve onun komşu kümesi esasen bir yıldız oluşturur.

Bu yıldız grafikteki diğer köşelere bağlı olsa da, yine de büyük bir bağımsız kümeyi garanti etmek için onun özelliklerini kullanabiliriz. Anahtar, bir yıldız oluşturmak ve ardından onu ve ona bağlanan tüm kenarları çıkarmaktır.

Şimdi kalan grafikte bir yıldız bulun ve onu da kaldırın.

Bu örnekte artık iki tek köşeli köşemiz kaldı - tek köşeli yıldızların kendileri - ve bulduğumuz diğer iki yıldızın merkezi köşelerini ekleyerek bağımsız bir 4 boyutlu küme oluşturuyoruz. Orijinal grafiğimizin dokuz köşesi olduğundan ve $latex sqrt{9}=3$ olduğundan, bağımsız 4 boyutlu kümemiz varsayımımıza uyuyor.

Bu argüman genel olarak herhangi bir üçgen içermeyen grafik için çalışır. Anahtar, tüm köşeleri hesaba katana kadar yıldızları ve onlara bağlanan kenarları bulmaya ve çıkarmaya devam etmektir. Bunu yaptıktan sonra, sadece yıldız sayısını sayın.

diyelim ki bitirdin k yıldızlar. $latex k > sqrt{n}$ ise, bağımsız bir boyut kümesi oluşturabilirsiniz. k her yıldızdan merkezi tepe noktası alınarak. Bu işe yarar çünkü herhangi iki yıldızın iki merkezi köşesi birbirine bağlanamaz, çünkü bu onları orijinal grafikte komşu yapacaktı.

$latex k < sqrt{n}$ ise, bu daha az sayıda yıldız, yıldızlardan en az birinin nispeten büyük olması gerektiğini garanti eder. Aslında, en az $latex sqrt{n}$ köşelere sahip olmalıdır. Neden? çünkü hepsi n grafiğin köşeleri arasında bulunmalıdır k yıldızlar. eğer hepsi k yıldızların her biri $latex sqrt{n}$ köşelerinden daha azına sahipti, o zaman grafikteki toplam köşe sayısı $latex k çarpı sqrt{n}$'den az olurdu. Ancak $latex k < sqrt{n}$ olduğundan, bu, grafikteki toplam köşe noktası sayısının $latex sqrt{n} çarpı sqrt{n} = n$'den az olması gerektiği anlamına gelir. grafiğin olduğunu bildiğimiz için n köşeler, yıldızların küçük olduğu varsayımı bazı köşeleri hesaba katmaz, bu da yıldızlardan en az birinin en az $latex sqrt{n}$ köşelere sahip olması gerektiği anlamına gelir. Ve $latex sqrt{n}$ boyutunda bir yıldız, en az $latex sqrt{n} -1$ boyutunda, kabaca $latex sqrt{n}$ olan bağımsız bir kümeyi garanti eder. (Grafik teorisyenleri genellikle bir alt grafiğin orijinal grafik boyutuna göre ne kadar büyük olduğuyla ilgilenirler, dolayısıyla $latex sqrt{n}$, $latex – 1$'den çok daha önemlidir.)

Orijinal örneğimizde olduğu gibi, üçgensiz grafiklerle ilgili bu sonuç Erdős-Hajnal varsayımıyla ilgilidir. Bir grafik üçgensiz ise, o zaman 2 boyutundan daha büyük bir kliğe sahip olamaz, çünkü 3 veya daha büyük boyutlu bir klik bir üçgen gerektirecektir. Üçgenleri yasaklamak, büyük klikleri yasaklamak anlamına gelir ve bu, tıpkı Erdős-Hajnal varsayımının öngördüğü gibi, büyük bağımsız kümelerin ortaya çıkmasına neden olur.

Matematikçiler son zamanlarda çok daha fazlasını kanıtladılar. Erdős-Hajnal varsayımı, yasak alt grafiğin dört veya daha az köşeden oluştuğu (bir kare veya 4 uzunluğunda bir yol gibi) tüm durumlarda kanıtlanmıştır. Ve 2021'de bir grup matematikçi kanıtladı bir grafik beşgen içermiyorsa - yani beş köşeyi birbirine bağlayan bir döngü - sonuç olarak alışılmadık derecede büyük bir klik veya alışılmadık derecede büyük bir bağımsız küme var olmalıdır. Bu, Erdős-Hajnal varsayımının beşgenler için yanlış olmasını bekledikleri için bunu kanıtlayan bazı matematikçileri şaşırttı. Küresel olarak hareket etmek için yerel olarak düşünmekten gelen bir başka şaşırtıcı derecede güçlü matematiksel sonuçtu.

1. Bir grafikte bulabileceğiniz en büyük bağımsız kümenin boyutunun 1 olduğunu varsayalım. Grafik hakkında ne söyleyebilirsiniz?

2. 3 veya daha uzun yolu olmayan bağlı bir grafikte yıldızdan başka bir şey elde etmenin neden imkansız olduğunu açıklayın.

3. Diyelim ki bir grafik n köşelerin 3 uzunluğunda yolu yoktur. Böyle bir grafikte bağımsız bir kümenin ne kadar büyük olması garanti edilir?