Matematik Olimpiyatı 2007, 2. Aşama, Soru 6

\(n\) kentin bulunduğu bir ülkede, herhangi iki kent arasında, bu kentleri doğrudan birleştiren en çok bir yol bulunuyor. Farklı yolların sadece kentlerde kesiştiği bu ülkede, herhangi bir kentin tüm yolları kapansa bile, bu kent dışındaki her kentten başka her kente, gerekirse diğer kentlerden geçerek ulaşılabiliyor. Farklı \(A\) ve \(B\) kentleri verildiğinde, seçtiğimiz en çok \(k\) yolu istediğimiz gibi tek yönlü yapmak suretiyle, geri kalan yollar nasıl tek yönlü yapılırsa yapılsın, iki kenti doğrudan birleştiren herhangi bir \(l\) yolu için, \(A\) dan başlamak, belirlenmiş yönlere uymak, \(l\) yolunu kullanmak ve herhangi bir kentten en çok bir kez geçmek üzere \(B\) ye ulaşabiliyorsak, “A kenti \(B\) kentine \(k\)-yönlü bağlanabilir” diyoruz. Her \(A\) kenti başka her \(B\) kentine \(k\)-yönlü bağlanabiliyorsa, \(k\) en az kaç olur?

Şıklar:

Cevap:  En küçük değer: \(k = 2n - 3\)

Çözüm:
Cevap: En küçük değer: \(k = 2n - 3\). 


Soruyu çizge kavramı kullanarak yeniden formüle edelim: \(G\) çizgesinde herhangi bir köşe ve bu köşeden çıkan tüm kenarlar silindikten sonra kalan çizge bağlantılı olacaktır. Bir diğer deyişle \(G\) 2-köşe bağlantılıdır. \(G\) çizgesinde herhangi iki farklı \(A\) ve \(B\) köşeleri verildiğinde, en fazla \(k\) kenarı tek yönlü yapmak suretiyle, geri kalan kenarlar nasıl yönlendirilirse yönlendirilsin, herhangi bir \(L\) kenarı için, \(A\) dan başlamak, belirlenmiş yönlere umeş, \(L\) kenarını kullanmak ve herhangi bir köşeden en çok bir kez geçmek üzere \(B\) ye ulaşılıyorsak, “A köşesi \(B\) köşesine \(k\)-yönlü bağlanabilir” diyoruz. Her A köşesi her \(B\) köşesine \(k\)-yönlü bağlanabiliyorsa, \(k\) nın alabileceği en küçük değer nedir? 


İlk önce \(k \ge 2n - 3\) olduğunu gösteren iki örnek verelim: 


Örnek 1. \(G\) bir tam çizge olsun. Bu durumda uç noktalarından en az biri \(A\) veya \(B\) köşelerinden en az biri olan tüm kenarların yönlendirilmesi gerekiyor. Buna göre, \(k \ge (n-1) + (n-1) - 1 = 2n - 3\). 


Örnek 2. \(G\) çizgesinde \(der(A) = der(B) = n - 2\) ve tüm kalan köşelerin dereceleri 2 olsun. O zaman bu çizgenin \(2n - 3\) kenarının her birinin yönlendirilmesi gerekiyor. 


Şimdi en fazla \(2n - 3\) kenarın yönlendirilmesinin yeterli olacağını göstereceğiz. 


\(G\) çizgesinde \(\Gamma = \{C_1, C_2, C_3, \dots, C_{l-1}, C_l\}\) yolu \(l - 1\) yönlendirilmemiş kenardan oluşan bir yol olsun. \(G\) çizgesinde \(1 \le i, j \le l\), \(|i - j| \ne 1\) olacak şekilde bir \((C_i, C_j)\) kenarı yoksa ya da \(\Gamma\) tek bir kenardan oluşuyorsa \((l = 2)\) \(\Gamma\) yoluna *asgari* yol diyelim. Şimdi bir kenar yönlendirme süreci tanımlayacağız. 


İlk adımda \(A\) köşesinde başlayan ve \(B\) noktasında sona eren bir \(\Gamma_1 = \{C_1, C_2, C_3, \dots, C_{i-1}, C_i\}\) (\(A = C_1, C_i = B\)) asgari yolu alalım ve bu yoldaki tüm kenarları \(A\) dan \(B\) ye doğru yönlendirelim. \(\Gamma_1\) yolu \(G\) çizgesindeki tüm köşeleri içeriyorsa, yönlendirme sürecini tamamlıyoruz. 


\(G\) çizgesinin 2-köşe bağlantılı olması nedeniyle herhangi bir \(D_1 = C_{p_1} \in \Gamma_1\) köşesinde başlayan ve herhangi bir \(D_m = C_{p_2} \in \Gamma_1\) (\(D_1 \ne D_m\)) köşesinde sona eren ve bu iki köşe dışında \(\Gamma_1\) üzerinde bulunmayan \(D_2, D_3, \dots, D_{m-1}\) köşelerini içeren en az bir \(\Gamma\) asgari yolu bulunacaktır. \(G\) çizgesinde \(1 \le i \le p_1 - 1\) veya \(p_2 + 1 \le i \le l\) ve \(2 \le j \le m - 1\) olacak şekilde herhangi bir \(C_iD_j\) kenarı yoksa \(D_1, D_2, D_3, \dots, D_{m-1}, D_m\) yoluna *gerilmiş* yol idiyelim. Bir başka deyişle gerilmiş \(\Gamma\) yolunda \(A\) kenarına en yakın köşe \(D_1\), \(B\) kenarına en yakın köşe ise \(D_m\) dir. İkinci adımda tüm \(\Gamma\) yolları içinde bir gerilmiş \(\Gamma_2\) yolu alıp bu yoldaki tüm kenarları \(D_1\) den \(D_m\) ye doğru yönlendirelim. \(\Gamma_1\) ve \(\Gamma_2\) yolları \(G\) çizgesindeki tüm köşeleri içeriyorsa yönlendirme sürecini tamamlıyoruz. 


text<|/ref|><td>Aksi takdirde üçüncü adımda \(\Gamma_1 \cup \Gamma_2\) yolunun bir köşesinde başlayan ve yine \(\Gamma_1 \cup \Gamma_2\) yolunun bir köşesinde sona eren ve yeni köşeler içeren bir asgari ve gerilmiş \(\Gamma_3\) yolu alıp bu yoldaki tüm kenarları benzer şekilde yönlendiriyoruz. 

q adım sonucunda \(\Gamma = \bigcup_{i=1}^{q} \Gamma_i\) bileşimi \(G\) çizgesindeki tüm köşeleri içerecektir. Her L kenarı ya bir \(\Gamma_s\) yoluna dahildir ya da harhangi \(\Gamma_s\) ve \(\Gamma_t\) yollarını birleştiriyordur. 


Durum 1: \(L = (C, D)\) kenarı bir \(\Gamma_s \in \Gamma\) yoluna dahildir. Bu yol yönlendirme sürecinde \(C\) den \(D\) ye doğru yönlendirilmiş olsun. Bu kenar için \(A\) köşesinden başlayan ve \(B\) köşesinde sona eren yolun bulunduğunu gösterelim. \(C\) köşesinden başlayarak \(G_s\) kenarlarıyla yönlenmeye ters olarak ilerlersek \(\Gamma_s\) in ilk kenarına kadar varırız. Daha sonra \(G_s\) ile ortak köşesi bulunan bir \(G_i\) yolunun kenarlarıyla \((i = s - 1\) olmak zorunda değildir) yine yönlenmeye ters olarak ilerlersek yeni bir \(G_j\) yoluna varırız ve benzer şekilde ilerlersek en sonunda \(A\) köşesine ulaşırız. \(D\) köşesinden başlayarak yönlenmeye uygun şekilde ilerlersek \(\Gamma_s\) in son kenarına kadar varırız. Daha sonra \(G_s\) ile ortak köşesi bulunan bir \(G_u\) yolunun kenarlarıyla \((u = s + 1\) olmak zorunda değildir) yine yönlenmeye uygun şekilde ilerlersek yeni bir \(G_v\) yoluna varırız ve benzer şekilde ilerlersek en sonunda B köşesine ulaşmış oluruz. Her adımda eklenen yollar asgari ve gerilmiş olduğu için bu iki yolun birleşimiyle \(A\) dan başlayan, sadece yönlendirme sürecinde yönlendirilmiş kenarları kullanan, L kenarından geçen ve \(B\) köşesinde sona eren yolu elde ederiz. 


Durum 2: \(L = (C, D)\) kenarı bir \(\Gamma_s \in \Gamma\), yoluna dahil değildir (L kenarı \(\Gamma = \bigcup_{i=1}^{q} \Gamma_i\) birleşimine dahil değildir). Bu durumda L kenarının uç noktaları bir \((s, t)\) ikilisi için \(C \in \Gamma_s\) ve \(D \in \Gamma_t\) köşeleri olacak. L kenarı \(C\) köşesinden \(D\) köşesine doğru yönlendirilmiş olsun. Yine ilk durumda olduğu gibi önce \(C\) köşesinden başlayarak yönlendirmeye ters olarak ve \(D\) köşesinden başlayarak yönlendirmeye uygun şekilde ilerleyip \(A\) dan başlayan, L kenarı dışında sadece yönlendirme sürecinde yönlendirilmiş kıranları kullanan L kenarından geçen ve \(B\) köşesinde sona eren yulu elde ederiz. 


Son olarak kenar yönlendirme sürecinde en fazla \(2n-3\) kenarın yönlendirildiğini gösterelim. Bir adımda eklenen köşe sayısı \(a\) ise, yönlendirilmesi gereken kenar sayısı \(a+1\) dir. Bu nedenle yönlendirilmesi gereken kenar sayısı en fazla \(1+2(n-2) = 2n-3\) olur. Çözüm tamamlanmıştır.