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

ALIÞTIRMALAR VE ÇÖZÜMLERÝ 12.1 ÇÝZGE KURAMI (GRAF)

3. Bir ül ke de A, B, C, D, E, F, G, H, I kent le rin den A ile B; A ile F; A ile G; B ile C; C ile
D; C ile G; D ile E; D ile H; E ile F; E ile H; E ile I; F ile G; G ile H ve H ile I ara sýn -
da kar þý lýk lý uçak se fer ler ya pýl mak ta dýr. Bun la ra ye ni iki kar þý lýk lý se fer da ha ek len di -
ðin de, bir yol cu, bir kent ten ha re ket edip, mev cut se fer ler den her bi ri ni tam ola rak
bir yön de kul la na rak, yol cu lu ða baþ la dý ðý ken te ge ri dö ne bi lir ha le ge li yor. Ye ni ko nan
ek se fer ler, aþa ðý da ki ler den han gi si ola bi lir?

A) B ile H; G ile I B) A ile C; D ile F C) B ile F; F ile I
D) A ile E; C ile E E) A ile E; B ile F
Çö züm:
Çö züm: (Ce vap B)
Þe hir le ri kö þe ola rak ve kar þý lýk lý uçak

se fer le ri ni de ke nar (çiz gi) ola rak yan -
da þe kil de ki gi bi gös te re lim. Þim di kö -

þe le rin de re ce le ri ni ya za lým.
der(A) = 3, der(B) = 2, der(C) = 3,
der(D) = 3 der(E) = 4, der(F) = 3,
der(H) = 4 ve der(I) = 2 dir.
Bir yol cu nun, bir kent ten ha re ket edip,
mev cut se fer ler den her bi ri ni tam ola -
rak bir yön de kul la na rak, yol cu lu ða baþ la dý ðý ken te ge ri dö ne bil me si için kö þe
(kent)le rin de re ce le ri çift ol ma lý dýr. Bu na gö re de re ce si tek olan kö þe ler, A, C, D ve F
dir. O hal de, A ile C ve D ile F ara sýn da ek se fer ko nur sa bu kö þe le rin de re ce si çift olur
ve bir yol cu, bir kent ten ha re ket edip, mev cut se fer ler den her bi ri ni tam ola rak bir
yön de kul la na rak, yol cu lu ða baþ la dý ðý ken te ge ri dö ne bi lir.

4. n(n > 3) ki þi nin bu lun du ðu bir top lu luk ta ba zý la rý bir bi ri ni ta ný mak ta ve ba zý la rý bir-
birini ta ný ma mak ta dýr. En az bir ki þi di ðer le ri ni ta ný ma mak ta dýr. Bu na gö re grup ta
bir bi ri ni ta ný yan en çok kaç ki þi var dýr?

A) n –1 B) n –2 C) n –3 D) n –4 E) n –5
Çö züm:
Çö züm: (Ce vap B)
Bu du ru mu tem sil ede cek bir G gra fý çi ze lim. n ki þi yi n kö þe ile ve ta ný þýk lý ðý da iki kö -
þe yi bir leþ ti re rek gös te re lim. En az bir ki þi di ðer le rin den hiç bi ri ni ta ný mý yor sa, en az
iki kö þe bir ke nar la bir leþ ti ril me miþ tir. v , v kö þe le ri ni bir leþ ti ren (v , v ) = e ke na -
1 2 1 2
rý bu lun ma sýn. Bu na gö re, G, gra fý en faz la K dir. Bu du rum, K tam gra fýn dan e
n – e n
ke na rý nýn çý kar týl ma sý de mek tir. Bu na gö re, ge ri ye n – 2 kö þe ka lýr. Bu na gö re bir bi ri
ile ta ný þýk olan en faz la n – 2 ki þi var dýr.

Tübitak Ulusal Matematik Olimpiyatlarýna Hazýrlýk 515