Page 242 - OLİMPİK SONLU MATEMATİK

ÇÝZGE KURAMI (GRAF)
12. BÖLÜM
r nek:
Ö Ör nek:

n ta ne þeh ri miz var ve her han gi bir þe hir den baþ ka her þeh re gi di le bi li yor sa yol sa yý sý
en az kaç olur?

Çö züm:
Çö züm:
Her þe hir den di ðer þe hir le re yol var sa bu graf bað lan tý lý graf ol mak zo run da dýr. Ör ne -
ðin bir dön gü yü ele ala lým. Dön gü de her kö þe den di ðer kö þe le re gi den yol var dýr. Böy le bir
dön gü de bir ke na rý çý kar dý ðý mýz da yi ne her han gi bir þe hir den di ðer þe hir le re yol ola cak -
týr. O za man bir dön gü de bir ke na rý çý kar týr sak yi ne bir bað lan tý lý yol el de ede riz. Bu gra fa
aðaç gra fý den di ði ni bi li yo ruz.
Aðaç graf lar da her kö þe bir bi ri ile ula þým ya pa bi lir. Fa-
kat dön gü yok tur.
n kö þe li bir graf ta dön gü var sa n ta ne yol var dýr. Dön -
gü den bir ke nar çý kar týl dý ðýn da yi ne her han gi bir þe hir den
di ðer þe hir le re yol ola ca ðýn dan en az n – 1 yol olur.

r nek:
Ö Ör nek:
14 þehrin bulunduðu bir ülkede bazý þehirlerarasýnda karþýlýklý uçak seferleri bulunmak-
tadýr. Herhangi bir þehirden baþka bir þehre ya hiç ulaþýlamýyor ya da aktarmalar da dahil
sadece bir þekilde ulaþýlabiliyor. Toplam 10 uçak seferi bulunduðuna göre, birbirine ulaþýla-
mayan þehir ikilisi sayýsýnýn alabileceði en büyük deðer ile en küçük deðerin toplamý kaçtýr?

A) 73 B) 88 C) 103 D) 109 E) 124

Çö züm:
Çö züm: (Ce vap D)
Birbirlerine ulaþým olan þehirleri gruplayalým.

a a a ... a
1 2 3 n
Her a gruplarý için bir þehirden bakla bir þehre tek türlü ulaþým olduðundan her grup-
i
ta x þehir varsa x – 1 yol vardýr.
i i
x + x + ... + x = 14 (þehir sayýsý)
1 2 n
(x – 1) + (x – 1) + ... + (x – 1) = 10 (yol sayýsý)
1 2 n
x + x + ... + x – n = 10 ise x + x + ... + x = 14 olduðundan n = 4 olur.
1 2 n 1 2 n
Tübitak Ulusal Matematik Olimpiyatlarýna Hazýrlýk 241