Geçiş K Sayısı (9, 9)

Question

Grafik teorisi okuyorum ve bu problemi nasıl çözeceğimi çözemiyorum. Grafiklerde pek iyi değilim ve bu tür sorunları çözmek benim için oldukça zor. Bana bir açıklama getirebilirseniz çok memnun olurum. Şimdiden teşekkürler!

Soru: Her k bağlantılı olduğu doğru mu ($k>1$) Hamilton döngüsüne sahip olmayan grafik, aşağıdakileri içeren bir döngüye sahiptir: $k$bağımsız köşeler ve komşuları? Bunun doğru olduğu biliniyor$k = 2$ ve $3$. Örneğin, sağdaki grafik 3 bağlantılı, ancak Hamilton değil. Ve gösterilen noktalı döngü şunları içerir:$3$bağımsız köşeler (renkli olarak daha açık olan üç köşe) ve komşuları. Hamilton olmadığını görmek için, bu grafiğin sadece tam iki parçalı grafik olduğuna dikkat edin.$K(3,4)$.

Answer 1

İlk önce ne zaman olduğunu düşünelim $G$bağlandı. Eğer$|V| < k$o zaman kesinlikle bölümleme yapamayız $V$ içine $k$ boş olmayan alt kümeler, varsayalım $|V| \geq k$.

Bu durumda uygun bir bölüm olduğunu iddia ediyorum. Bunu göstermek için bir alt küme bulmak yeterli$V' \subseteq V$ ile $|V'| = k-1$ öyle ki $G - V'$ bağlı: o zaman alabiliriz $V_1$ olmak $V - V'$ ve biz yapabiliriz $V'$ her birinin alacağı bir öğe içeren setler halinde $V_2,\dots,V_k$. Böyle bir şeyi nasıl buluruz$V'$? Sezgisel olarak, yayılan bir ağaç alıyoruz$G$ ve biz kopana kadar yaprakları birer birer "koparın" $k-1$. Resmen, geçebiliriz$G$bazı algoritmalara göre (örneğin DFS). İzin Vermek$v_1, \dots, v_n$bu geçiş sırasında köşeleri ziyaret ettiğimiz sıra. Köşeleri bu sırayla geçebildiğimiz gerçeği gösteriyor ki, ilk$n-(k-1)$ köşeler bağlı bir alt grafiğini indükler $G$böylece alabiliriz $V'$ son olmak $k-1$ köşeler.

Farzedelim $G$bağlı değil mi? Peki, daha fazla bağlı bileşeni varsa$k$, o zaman böyle bir bölüm olamaz (neden?). Aksi takdirde (şartıyla$|V| \geq k$) esasen aynı fikri kullanabiliriz: $G$ ve kopan yaprak sayısı artı kalan bağlı bileşenlerin sayısı olana kadar yaprakları koparın. $k$. Yine, bu bir geçiş sırası kullanılarak yapılabilir, ancak bu durumda kaç yaprak koparmamız gerektiğini belirlemek için biraz düşünmeyi gerektirir.