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

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

7. Do kuz köy 2, 3, 4, …, 10 sa yý la rýy la nu ma ra lan dý rýl mýþ týr. Her k, m {2, 3, 4, …, 9, 10}
içi k ve m ara la rýn da asal ise k ve m nu ma ra lý köy ler ara sýn da doð ru dan yol bu lu nur.
n nu ma ra lý köy den yo la çý kan bir ara ba, her yol dan en faz la bir kez geç mek üze re tüm
köy le ri do la þa bi li yor sa geç miþ ol du ðu yol sa yý sý nýn en faz la ol ma sý için n aþa ðý da ki ler -
den han gi ola bi lir?

A) 2 B) 3 C) 4 D) 5 E) 6
Çö züm:
Çö züm: (Ce vap D)
So ru da ve ri len ler doð rul tu sun da kö þe le rin de -
re ce le ri ni ya za lým;
der(v ) = 4, der(v ) = 6, der(v ) = 4,
2 3 4

der(v ) = 7, der(v ) = 2, der(v ) = 8,
5 6 7
der(v )=4, der(v ) = 6, der(v ) = 3 tür.
8 9 10
Bu na gö re, "Bir graf ta tek de re ce li kö þe sa yý sý
iki den faz la ise bu graf ta Eu ler yo lu yok tur. Bað -
lan tý lý bir graf ta sa de ce iki kö þe nin de re ce si tek
ise, bu graf ta en az bir Eu ler yo lu var dýr. Bu yol -

da tek de re ce li kö þe den baþ la yan Eu ler yo lu di -

ðer tek de re ce li kö þe de bi ter." te ore min den,
graf ta ki Eu ler yo lu 5 nu ma ra lý kö þe de baþ lar sa 10 nu ma ra lý kö þe de bi ter ve ya 10 nu -
ma ra lý kö þe de baþ lar sa 5 nu ma ra lý kö þe de bi ter.

8. n ki þi lik bir grup tan her bir ki þi en faz la üç ki þi yi ta ný mak ta dýr. Bu grup ta bir bi ri ni ta -
ný ma yan iki ki þi nin or tak bir ta ný dý ðý var dýr. Bu na gö re n nin ala bi le ce ði en bü yük de -
ðer kaç týr?
(Bir graf ta n nok ta var dýr. Her bi ri nin de re ce si en faz la 3 tür. Eðer iki nok ta yý bir -
leþ ti ren bir ke nar yok sa bu iki nok tay la bir leþ ti ril miþ olan üçün cü bir nok ta var dýr.
Bu na gö re n nin ala bi le ce ði en bü yük de ðer kaç týr?)

A) 5 B) 6 C) 8 D) 10 E) 12
Çö züm:
Çö züm: (Ce vap D)
A ile arkadaþ olmayan en fazla kaç kiþi vardýr diye bakalým. A ile arkadaþ olmayan bir
insanýn A ile ortak arkadaþý vardýr. A nýn en fazla üç arkadaþý ve bu arkadaþlarýn A dan
farklý en çok 2 arkadaþý var ise en fazla 6 arkadaþý olmayan üç arkadaþý var.
Grup ta ki 10 ki þi den bi ri A ol sun. A nýn ta ný dý ðý ki þi sa yý sý en faz la 3 ola bi lir. Bun lar B,
C, D ol sun B, C, D nin ta ný dý ðý iki þer ki þi da ha ala bi li riz fa kat bun lar n nin de ðe ri ni

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