Otuz altı hava alanından herhangi ikisi arasındaki karşılıklı uçuşlardan her biri beş havayolu şirketinden biri tarafından yapılacaktır. Ulaştırma Bakanlığı her hava alanına, o hava alanında aralarında aktarma yapılabilen aynı şirkete ait her uçuş ikilisi için $1$ milyon lira destek vermeye karar veriyor. Bakanlığın bu uygulama için harcayacağı paranın en az ne kadar olabileceğini belirleyiniz.
(Azer Kerimov)
Çözüm:
Cevap: $3780$
Öncelikle cevabın daha az olamayacağını gösterelim. Soruyu çizge cinsinden ifade edelim, köşeler şehirleri, kenarlar uçuşları, renkler şirketleri temsil etsin. Her $A$ köşesinden çıkan $i$ renkli kenar sayısı $a_i$ olsun. İncelediğimiz toplam
$\binom{a_1}{2}+\binom{a_2}{2}+\binom{a_3}{2}+\binom{a_4}{2}+\binom{a_5}{2}=\frac{1}{2}(a_1^2+a_2^2+a_3^2+a_4^2+a_5^2)-\frac{1}{2}(a_1+a_2+a_3+a_4+a_5)$
Tüm köşeler için yazıp toplarsak toplam harcanan para
$\frac{1}{2}[\sum_{A\in G}{a_i^2}-\sum_{A\in G}{a_i}]\geq\frac{1}{2}[\frac{1}{36\cdot 5}(\sum_{A\in G}{a_i})^2-\sum_{A\in G}{a_i}]$
$\sum_{A\in G}{a_i}=\sum_{A\in G}{der(A)}=36\cdot 35=1260$ olduğunu göz önünde bulundurursak harcanan paranın minimum değeri $3780$ çıkar.
$3780$ için örneği kurarken köşeleri 6 köşelik 6 gruba ayıralım. $V_{i,j}$ notasyonunda $i$ grup numarasını, $j$ gruptaki sırayı belirtsin. Her grubu kendi içinde resimdeki gibi boyayalım.
Mor $0$, yeşil $1$, mavi $2$, siyah $3$, kırmızı $4$ olsun. $V_{a,x} - V_{b,y}$ ikilisi arasındaki kenarı şekilde $(a-b)$ kenarı ile $(x-y)$ kenarının toplamına boyayalım. ($a-a=0$ kabul edelim.) Örneğin sağladığı biraz inceleme ile görülebilir.
Öncelikle cevabın daha az olamayacağını gösterelim. Soruyu çizge cinsinden ifade edelim, köşeler şehirleri, kenarlar uçuşları, renkler şirketleri temsil etsin. Her $A$ köşesinden çıkan $i$ renkli kenar sayısı $a_i$ olsun. İncelediğimiz toplam
$\binom{a_1}{2}+\binom{a_2}{2}+\binom{a_3}{2}+\binom{a_4}{2}+\binom{a_5}{2}=\frac{1}{2}(a_1^2+a_2^2+a_3^2+a_4^2+a_5^2)-\frac{1}{2}(a_1+a_2+a_3+a_4+a_5)$
Tüm köşeler için yazıp toplarsak toplam harcanan para
$\frac{1}{2}[\sum_{A\in G}{a_i^2}-\sum_{A\in G}{a_i}]\geq\frac{1}{2}[\frac{1}{36\cdot 5}(\sum_{A\in G}{a_i})^2-\sum_{A\in G}{a_i}]$
$\sum_{A\in G}{a_i}=\sum_{A\in G}{der(A)}=36\cdot 35=1260$ olduğunu göz önünde bulundurursak harcanan paranın minimum değeri $3780$ çıkar.
$3780$ için örneği kurarken köşeleri 6 köşelik 6 gruba ayıralım. $V_{i,j}$ notasyonunda $i$ grup numarasını, $j$ gruptaki sırayı belirtsin. Her grubu kendi içinde resimdeki gibi boyayalım.
Mor $0$, yeşil $1$, mavi $2$, siyah $3$, kırmızı $4$ olsun. $V_{a,x} - V_{b,y}$ ikilisi arasındaki kenarı şekilde $(a-b)$ kenarı ile $(x-y)$ kenarının toplamına boyayalım. ($a-a=0$ kabul edelim.) Örneğin sağladığı biraz inceleme ile görülebilir.