Matematikte ağır haberler var! Lingle'nin varsayımı kanıtlanacak ve 60 yıllık sorun kırılacak mı?
Nokta ve yüzey, bir grafik oluşturmak için birleştirilir. Bu grafiklerle ilgili çeşitli sorular düşünebiliriz, örneğin: Basit küçük resimlerin birden çok kopyasını büyük bir resmi mükemmel şekilde yeniden oluşturmak (örtmek) nasıl yapılır?
Evdeki mutfağın zeminine bakıyormuşsunuz gibi: Mağazadaki tüm zemini aynı boyuttaki karolardan herhangi biriyle tamamen kaplayabilir miyim? Gerçek hayatta her tür karonun mutfağınıza uygun olması imkansızdır.Genel olarak, farklı şekillerde karoların tüm zemini kaplaması için birleştirilmesi (veya kesilmesi) gerekir. Ancak belirli bir grafik dünyasında bu fikir elde edilebilir.
1963'te bir adam Gerhard Ringel Almanya'daki Alman matematikçi cesur bir varsayım öne sürüyor: bazı özel grafikler her zaman küçük resmin n kopyası ile mükemmel bir şekilde kaplanabilir. Bu bağlamda, n kenarlı herhangi bir T ağacının, 2n + 1 mertebesindeki K2n + 1 tam grafiğinde T'ye denk olmayan ve izomorfik 2n + 1 alt grafiği bulabileceğine dikkat çekti (yani, 2n + 1 T kopyalar K2n + 1'e mükemmel şekilde doldurulabilir)
Ringel'in varsayımını kanıtlamak için insanlar olasılıklı yöntemler, kanonik lemmalar vb. Gibi çeşitli matematiksel araçlar geliştirdiler ve kullandılar, ancak her zaman boşluklar var gibi görünüyor.
Yakın zamanda, Zürih'teki İsviçre Federal Teknoloji Enstitüsü'nden Benny Sudakov (Benny Sudakov), Birmingham Üniversitesi'nden Richard Montgomery (Richard Montgomery) ve Londra'daki Birkbeck Üniversitesi'nden Alex Poklovsky (Alexey Pokrovskiy) Üç matematikçi tarafından yayınlanan ilgili makaleler, yaklaşık 60 yıldır insanları şaşırtan bu matematiksel varsayımı kanıtlamak için umut verebilir.
01 Ringel'in varsayımı nedir? Tam grafik ve ağaç diyagramı
Bu varsayımı yayınladıktan sonra, Lingle bazı temel kavramları ortaya koydu: İlk olarak, 3'ten büyük herhangi bir tek sayı ile başlayın (bu sayı, spekülasyonu mantıklı kılmak için tek sayı olmalıdır) ve her nokta diğer tüm noktalara bağlanacak şekilde aralarında kenarlar çizin. Ortaya çıkan grafiğe tam bir grafik denir.
5 noktalı tam bir grafik
Ardından, başka bir grafik türüne bakıyoruz. Basit bir yol olabilir, başka şubeleri de olabilir, tabii şubeye şubeler eklemeye devam edebiliriz, Herhangi bir kapalı döngü içermediği sürece, grafik ihtiyaç duyulduğunda daha karmaşık hale getirilebilir.Bu tip grafiğe ağaç diyoruz.
Basit veya karmaşık ağaç diyagramı
Ringel'in varsayımı, tam bir grafik ile ağaç arasındaki ilişki hakkındadır.
Dedi ki: Önce 2n + 1 nokta içeren tam bir grafik hayal edin. Sonra n + 1 nokta kullanılarak kaç ağaç yapılabileceğini düşünün, aslında birçok farklı ağaç yapılabilir.
Şimdi, ağaçlardan birini seçin ve onu ağacın her kenarı tam grafikte kenara denk gelecek şekilde yerleştirin. Ardından, aynı ağacın başka bir kopyasını tüm grafiğin farklı bir kısmına yerleştirin.
Ringle, doğru yerden başlayıp bu eyleme devam ederseniz, yukarıdaki şeklin tamamını mükemmel bir şekilde kopyalayabileceğinizi tahmin ediyor. Bu, grafiğin tamamındaki her kenarın ağacın her kenarıyla kaplandığı ve ağacın hiçbir kopyasının birbiriyle çakışmayacağı anlamına gelir (aşağıdaki şekilde gösterildiği gibi).
Mükemmel kopya
Bu varsayım nasıl anlaşılır?
Tam bir grafik bilindiğinde, nokta sayısı n (3'ten büyük ve tek sayı) ise, o zaman grafiğin n adet alt grafikle mükemmel bir şekilde kaplanması gerekir ve alt grafiğin şekli (n-1) / 2 kenar Ağaç grafiği; Tersine m kenarlı bir ağaç grafiği biliniyorsa 2m + 1 noktalı tam bir grafik oluşturmak için 2m + 1 ağaçlar kullanılabilir.
Ringel'in varsayımı 11, 21 ve 31 noktalı grafiklerin tamamlanması için geçerli görünüyor, ancak gittikçe daha fazla noktayla tüm grafikler giderek daha karmaşık hale geliyor. Bu varsayım hala geçerli mi?
Bu aralık çok geniş olmasına rağmen, matematik topluluğunun Ringel'in varsayımının doğru olabileceğine inanmak için nedenleri vardır. En basit neden, 2n + 1 noktalı eksiksiz bir grafikteki kenar sayısının her zaman n + 1 noktalı bir ağaçtaki kenar sayısına eşit olarak bölünebilmesidir.
Gerçekte, matematikçiler hızla varsayımın en azından uygulanabilir olduğuna dair başka bir kanıt buldular.
02 Döndürme yöntemi yeni bir sorun getiriyor: ilk ağacın nasıl yerleştirileceği
Ringer varsayımını yayınladıktan kısa bir süre sonra, Slovak kökenli Anton Kotzig adlı Kanadalı bir matematikçi bu örneği Ringer'dan daha cesur bir tahmin yapmak için kullandı. Ringel, 2n + 1 noktalı her tam grafiğin n kenarlı herhangi bir ağaç grafiği ile döşenebileceğini söylerken, Koziger, döşemenin her zaman döner şekilde yapılabileceğini düşünüyor.
Varsayımlarını keşfetmek istiyorsanız, basit bir yıldız ağacı diyagramı iyi bir başlangıç noktası olabilir.
En basit ağaç diyagramlarından biri yıldızdır: bir merkez noktası vardır ve diğer kenarlar merkezden yayılır. Ancak tipik bir yıldız grafiğinden farklıdır, çünkü kenarların nokta etrafında eşit olarak düzenlenmesi gerekmez, ancak aynı konumdan dışarıya doğru uzanır ve merkezi nokta dışında hiçbir yerde kesişemez.
Basit yıldız ağacı diyagramı
Nitekim matematikçiler hızlı bir şekilde n + 1 noktalı bir yıldız ağacının her zaman 2n + 1 noktalı tam bir grafiğe mükemmel bir şekilde kopyalanabileceğini gözlemlediler. Bu gerçek tek başına çok ilginç, ancak bunun nasıl kanıtlanacağı matematikçileri zorlaştırıyor.
Basit bir durum verin. 11 noktadan başlayarak, bu noktaları bir daire şeklinde düzenleyin ve ardından tam bir resim oluşturmak için her noktayı birbirine bağlayın (aşağıda gösterildiği gibi).
Bağlantıdan sonra resmi tamamlayın
Sonra bir yıldız ağacı hayal edin: 1 merkez nokta ve bu noktadan uzanan 5 kenar (aşağıda gösterildiği gibi).
Yıldız ağacı
Ardından, merkezi nokta grafiğin tamamındaki bir noktayla hizalanacak şekilde yıldızı yerleştirin ve sonra dönmeye başlayın.Bu sırada, tüm grafiğin başka bir kısmıyla çakışan yıldız ağacının yeni bir kopyasına sahip olacaksınız.
Yıldız ağacını her seferinde bir nokta olmak üzere sürekli olarak döndürün. Lingle'nin öngördüğü gibi, başlangıç noktasına döndüğünüzde, herhangi bir kısmi örtüşme olmaksızın önceki tam resimle tamamen aynı olan bir resim elde edeceksiniz (aşağıda gösterildiği gibi).
Rotasyondan sonra tamamen çakışır
Ancak bu deneyde hala boşluklar var: yıldız diyagramı düzenli, bu yüzden nasıl yerleştirildiği önemli değil. Ancak ağaçların çoğu değildir.Ağaç üzerinde farklı uzunluklarda birçok farklı dal varsa, sadece bunların doğru yerleştirilmesi döndürme yönteminin çalışmasını sağlayabilir ve bu aşamada ilk adımın nasıl yerleştirileceği çok önemli olacaktır.
Neyse ki matematikçiler sonunda sezgisel bir renk yöntemi buldular.
03 Renk kodlamasına göre ağacın gökkuşağı kopyasını bulun
Renk kodlamanın yaşamda birçok uygulaması vardır, örneğin, günlük işin aciliyetini ve tamamlanmasını ayırt etmeye yardımcı olabilir. İlk ağacın nasıl yerleştirileceğini bulmanın da etkili bir yolu olduğu ortaya çıktı.
Renk kodlaması nasıl yapılır? İlk olarak, bir daire etrafına yerleştirilmiş 11 noktanın tam bir resmini hayal edin, Kodlama kuralı, mesafeye göre renklendirmektir (bir kenarla birbirine bağlanan iki nokta arasındaki mesafe).
İki noktanın birbirine bitişik olması durumunda aralarındaki mesafenin 1 olduğunu ve iki noktanın bir noktayla ayrılması durumunda aralarındaki mesafenin 2 olduğunu varsayarsak (aşağıdaki şekilde gösterildiği gibi).
Mesafe nasıl hesaplanır
Şimdi tüm grafiğin kenarlarını mesafeye göre renklendirin. 1 mesafeli tüm noktaların kenarları aynı renge, örneğin maviye boyanır. Noktanın 2 mesafeli tüm kenarları da sarı gibi aynı renkle işaretlenir. Bağlantı noktaları arasındaki eşit mesafelerin aynı renkle işaretlenmesi için bunu yapmaya devam edin.
2n + 1 noktalı tam bir grafikte, şemayı yürütmek için n farklı renge ihtiyacınız olduğu ortaya çıktı (aşağıda gösterildiği gibi).
Renklendirmeden sonra tam grafikler
Grafiğin tamamını renkle kodladıktan sonra, ilk ağacı yerleştirmenin bir yolunu nasıl bulursunuz?
Fikir Ağacı, her rengin bir kenarını kaplayacak ve iki kez herhangi bir rengi kapatmayacak şekilde yerleştirin (aşağıdaki şekilde gösterildiği gibi) Matematikçiler bu konuma ağacın gökkuşağı kopyası diyorlar. 2n + 1 noktalı eksiksiz bir grafik için, boyama için n renge ihtiyaç duyulduğundan ve gökkuşağı kopyasının her zaman n + 1 noktalı bir ağaç grafiği olduğundan, bir gökkuşağı kopyasının var olduğunu biliyoruz.
Ağacın gökkuşağı bir kopyası renklendirildikten sonra görünüyor
Bu noktada matematikçiler, 2n + 1 noktalı her tam grafiğin n kenarlı bir ağacın gökkuşağı kopyasını içerdiğini kanıtlayarak Ringel'in varsayımını kanıtlayabilir. Gökkuşağı kopyası her zaman mevcutsa, tüm haritanın tam kapsamı her zaman geçerlidir.
Üç matematikçinin bu gerçeği kanıtlaması 40 yıldan fazla sürdü.
04 Mükemmel yerleştirme, varsayımı kanıtlamanın son adımıdır
11 (2n + 1 = 11, sonra n = 5) nokta içeren ve 5 farklı renkte renklendirilmiş tam bir grafiğiniz ve 6 nokta ve 5 kenarlı bir ağaç grafiğiniz varsa, göreviniz Resmin tamamında ağacın gökkuşağı bir kopyasını bulmaktır.
Çalışma devam ettikçe, bir sonraki ağacı yerleştirme görevi gittikçe zorlaşır, bu nedenle ileriyi planlamanız gerekebilir. Üç matematikçi başından beri gökkuşağının bir kopyasını bulmanın zor olmayabileceğini, nasıl yerleştirileceğini biliyordu. Bu bir bavul hazırlamaya benziyor. Hepimizin bildiği gibi, bavullar, bisikletler vb. Gibi en zor ve karmaşık nesnelerle başlamalıyız, çünkü her durumda sonunda boşlukta bazı küçük şeyler bulabilirsiniz ve matematikçiler de onu benimsemiştir. Bu felsefe.
6 kenardaki noktaların bir araya toplandığı 11 kenarlı bir ağaç hayal edin. Geri kalanların çoğu, dalları gibi tek bir şekildir (aşağıda resmedilmiştir).
Dal gibi karmaşık ağaç diyagramı
Yerleştirmesi en zor kısım 6 kenarlı noktadır. Bu nedenle, matematikçi onu ağacın geri kalanından ayırır ve sonra ilk sıraya yerleştirir. Sanki söküp sonra yukarı çıkmak için bir yatak monte etmeniz gerekiyor.
Bunu yaparak, grafiğin tamamında kalan alanın rastgele olmasını sağladılar.
Bu üç matematikçinin araştırması, ağaç grafiğinin en zor kısmı gömüldüğünde ve tüm grafiğin kalan alanı rastgele olduğunda, bir gökkuşağı kopyası elde etmek için ağacın geri kalanını yerleştirmenin her zaman bir yolu olduğunu göstermektedir.
Ek olarak, üç matematikçinin araştırma sonuçları benzer çözülmemiş problemler için yeni fikirler sağlar. Belki uygun bir ayarlama daha bilinmeyen varsayımları çözebilir.
Metin | Huanhuan
Düzen | Tian Xiaona
Heyecan verici içeriğimizden daha fazlasını elde etmek için aşağıdaki mavi renkteki "Daha Fazla Bilgi" yi tıklayın.
