Rastgele bir grafiğin çapı neden önemlidir?
Görebilirsiniz çapa bir grafik, olarak tanımlanan en uzun kısa yol uzunluğu, a önemsiz olmayan bir miktar rasgele , örneğin rastgele grafiğin grafiktir$G(n,p)$ arasına kenarlar eklenerek oluşturulur $n$ olasılıkla bağımsız puanlar $p$.
Ama onu matematiksel olarak bu kadar önemli kılan nedir? Diğer temel grafik fikirleriyle ne gibi ilişkileri var? Dahası, grafiğe derece dağılımı veya köşelerdeki uzamsal kısıtlamalar (yani rastgele geometrik grafik) gibi bazı kısıtlamalar eklersem, bu grafik çapının önemine ne yapar?
Yanıtlar
Kromatik sayı veya maksimum derece gibi, grafik çapı da kendi başına önemlidir. Grafiğinizin bir ağı modellemesini istiyorsanız, bir düğümden diğerine geçmek için gereken maksimum 'atlama' sayısını size söyler. Grafiğiniz, örneğin her kenarın 1 uzunluğunda düz bir çizgi olduğu bir grafik gibi geometrik olarak gömülmüşse, bu durumda (soyut) grafiğin çapı, gömülü grafiğin çapının bir alt sınırı olarak kabul edilir.$\mathbb{R}^n$.
İzin Vermek $D$ bir grafiğin çapı olmak, $n$ onun emri, $\Delta$ maksimum derecesi ve $\kappa$bağlantısı. Çapın nasıl davrandığına ilişkin bazı genel buluşsal yöntemler (bunlar teoremler değil trendlerdir):
- Bir grafiğin çapı düşükse ve çok sayıda köşesi varsa, o zaman birçok kenara sahip olmalıdır ve bu kenarlar, herhangi iki köşenin birbirinden uzaklaşmasına izin vermeyecek şekilde bir şekilde 'tek tip' bir şekilde dağıtılmalıdır.
- Grafiğin çapı köşe sayısına göre çok büyükse, grafiğin daha az kenarı vardır.
- Yukarıdaki noktalara benzer şekilde, çap ve maksimum derece birlikte bir grafiğin sahip olabileceği toplam köşe sayısını sınırlar. Sezgisel olarak, bir grafikten bir derinlik ağacı oluşturduğunuzda olduğundan daha fazla köşe elde edemezsiniz.$D$ kabaca dallanan $\Delta-1$her katmanda birkaç kez, işleri kapatmak için birkaç ekstra kenar ile. Bu sınırın incelenmesi, derece çapı probleminin konusudur .
- Çap ve maksimum derece bağlıyken $n$yukarıdan, çap ve bağlantı onu aşağıdan bağladı. Bağ kabaca benziyor$n \geq \kappa \cdot (D-1)$.
- Çap ayrıca grafiğin çevresini de sınırlar. Kısaca, çap düşükse ve grafik herhangi bir döngü içeriyorsa, kısa uzunlukta bir döngü içermelidir.
Son olarak, çap güzel bir karmaşıklık kısıtlamasıdır. Genel grafiklerde bazı yapı veya özellikleri incelemeye çalışıyorsanız ve umutsuzca kayboluyorsanız, çap 2 grafiklerinde ne olduğunu düşünmek genellikle yararlıdır (özellikle de başka bir kısıtlama veya buna uygun kısıtlı grafik sınıfı verildiğinde). Bu da hemen hemen tüm grafiklerin çap 2'ye sahip olmasını oldukça tesadüf yapar!