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

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

1. 15 ki þi nin ka týl dý ðý bir top lan tý son ra sý bun lar dan bi ri kim sey le to ka laþ ma dý ðý ný; iki si
Al tý þar ki þiy le, üçü be ser ki þiy le, dör dü dör der ki þi liy le, be si iki þer ki þiy le to ka laþ tý ðý ný
söy le di. Bu 15 ki þi den en az bi ri nin söy le di ði nin yan lýþ ol du ðu nu gös te ri niz.
Çö züm:
Çö züm:
So ru yu gra fa dö nüþ tü rür sek, to ka la þan la to ka la þýl dý ðýn dan de re ce ler top la mý çift ol -
ma lý dýr. Bu na gö re, 2.6 + 3.5 + 4.4 + 5.2 = 53 tek sa yý ol du ðun dan hep si doð ru söy -
le miþ ola maz. En az bir ki þi nin söy le di ði yan lýþ týr.

2. 501 ki þi lik bir okul da her han gi üç öð ren ci den en az iki si ar ka daþ týr. Bu okul da en çok
ar ka da þa sa hip olan öð ren ci ler den bi ri nin ar ka daþ sa yý sý en az kaç ola bi lir?
Çö züm:
Çö züm:
Cevap n olsun. n 250 ol du ðu nu gös te re lim. Graf tam grafsa n = 500 olur. Graf tam
graf ol ma sýn. Aralarýnda kenar olmayan iki A ve B kö þe le ri ni ala ým. Di ðer 499 kö þe -
den her bi ri A ve ya B ile bað lan tý lý dýr. O za man A ve B den bi rin de re ce si en az 250
olur.

3. A ve B adýn da iki ha va yo lu þir ke ti var dýr. Bu ha va yo lu þir ket le ri nin An ka ra, Ýs tan bul,
Er zu rum, Ýz mir, Ma lat ya ve Kay se ri þe hir le ri ara sýn da uçak se fer le ri var dýr. Her han -
gi iki þe hir ara sýn da çift yön lü uçuþ var dýr. Öy le dört þe hir var dýr ki ay ný ha va yo lu þir -
ke ti ne ait uçuþ la uç ma nýn müm kün ol du ðu nu gös te ri niz. Bu þe hir ler bir cycle oluþ -
tu rur. (Ör nek: þe hir ler, P, Q, R, S ise, P Q R S P dir.)
Çö züm:
Çö züm:
Prob le mi mi zi graf te ori si nin bi li nen yön tem ve ku ral la rý ile çö ze lim. K : n kö þe li bir graf
n
ol mak üze re, so ru da ve ri len þe hir ler al tý kö þe li bir graf oluþ tu ra cak týr. Ya ni, K nýn ke -
6
nar la rý ný kýr mý zý ve ya ma vi gi bi iki fark lý renk le bo ya nýr sa C (4 lü cycle) var dýr. K da
4 6

ta ne ke nar ola ca ðýn dan kýr mý zý ren gin en az 8 ta ne bu lun ma sý ge re kir.

Tüm 4 kö þe li 6 ke nar lý graf la rý ele ala lým. Ýki ren ge bo yan mýþ ke nar la rýn sa yý sý ay ný
de ðil dir. K nýn da ol ma dý ðý gi bi. Gra fý mýz da kýr mý zý ke nar la rýn sa yý sý 4,5 ya da 6 olan
6
K ü oluþ tu ran P, Q, R, S kö þe le ri miz var dýr. Þa yet kýr mý zý ke nar sa yý sý 5 ya da 6 ise C
4 4
ko lay lýk la bu lu nur.

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