Geomania.Org Forumları
Yarışma Soruları => Tübitak Lise 2. Aşama => 2010 => Konuyu başlatan: geo - Ağustos 06, 2013, 03:44:25 öö
-
Bir ülkede başkente doğrudan karayolu ile bağlı kentlerin sayısı $ 2010$ dur. Başkent dışındaki her kent $2010$ dan az sayıda kente doğrudan karayolu ile bağlı olup, aynı sayıda kente doğrudan bağlı olan herhangi iki kent için bu sayı çifttir. Başkenti doğrudan çeşitli kentlere bağlayan yollardan $k$ tanesi kapatılarak bakıma alınacaktır. Bu ülkedeki karayolu ağı nasıl oluşturulmuş olursa olsun, bunun aralarında karayolu ulaşımı mümkün olan herhangi iki kent arasındaki ulaşımın hala mümkün olacağı biçimde yapılmasını olanaklı kılan en büyük $k$ sayısını belirleyiniz.
(Azer Kerimov)
-
Cevabımız $503$.
Şeklimizi grafa dönüştürelim.$G$ grafımız genelliği bozmadan bağlantılı olsun. $v_0$ başkent olsun. $v_0$'ı graftan kaldırdığımızı düşündüğümüzde geriye kendi içinde bağlantılı birbiriyle ayrık $C_1,C_{2,\dots ,}C_m$ altgrafları kalsın. $v_0$'dan altgraflara giden yolların toplamı $2010$' dur. Bu yolların sayısını $C_i$ için $d_{C_i}\left(v_0\right)$ ile gösterelim. $$\sum\limits^m_{i=1}{d_{C_i}\left(v_0\right)=2010} \tag {*}$$
Her altgraf için bu yollardan $d_{C_i}\left(v_0\right)-1$ tanesini $G$'nin bağlantılılığı bozulmadan silebiliriz. Çünkü $v_0$'dan altgrafa giden bir kenar bağlantılılığı korumak için yeterlidir. Bu nedenle $G$'den $2010-m$ tane kenar silebiliriz.Dolayısıyla problem altgraf sayısının maksimumunu bulmaya indirgendi.
$d_{C_i}\left(v_0\right)=1$ olacak şekilde kaç altgrafımız olabileceğine bakalım.Eğer $d_{C_i}\left(v_0\right)$ tekse $C_i$ başka tek dereceli bir köşeye daha sahiptir. Çünkü $C_i$ altgrafında köşelerin dereceleri toplamı çifttir. Bununla birlikte eğer $2$ köşe aynı dereceye sahipse bu derece çifttir. Tüm köşelerin dereceleri $\le 2009$ olduğundan en fazla $1005$ tane tek dereceli köşe olabilir. Yani en fazla $1005$ tane altgraf için $d_{C_i}\left(v_0\right)$ tektir.
Ayrıca $\left(*\right)$'dan ötürü $d_{C_i}\left(v_0\right)$ tek olan çift tane $i$ olmak zorundadır. Yani en fazla $1004$ altgraf için $d_{C_i}\left(v_0\right)=1$ olabilir. Kalan her altgraf için $d_{C_i}\left(v_0\right)\ge 2$' dir.O halde $\left(*\right)$'dan ötürü toplam en fazla $1004+\frac{2010-1004}{2}=1507$ altgraf olabilir. Dolayısıyla her durumda $2010-1507=503$ kenar silebiliriz.
Şimdi $503$' ten fazla kenar silemeyeceğimiz bir graf kuralım. $v_0$'a $1004$ kenar ile $K_3,K_5,\dots ,K_{2009}$ bağlayalım. $1006$ kenar ile de $503$ tane $K_2$ bağlayalım. ($K_n$: $n$ köşeli tam graf) $,K_5,\dots ,K_{2009}$'a giden kenarlardan hiçbirini silemeyiz. Kalan $503$ tane $K_2$'nin her birinden en fazla $1$ kenar silebiliriz.
\[k_{max}=503.\]