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

ÇÝZGE KURAMI (GRAF)
12. BÖLÜM
3) De re ce si 5 olan 5 kö þe için 5×5 = 25 ve de re ce le ri 4 olan 5 kö þe için ise 4×5 = 20
olup de re ce ler top la mý 25 + 20 = 45 ke nar var dýr. Her bi ri iki de fa sa yýl dý ðýn dan

top lam ke nar ol ma lý dýr. oldu ðun dan bu þart lar da ve ri len bir gra fý
oluþ tur mak (ula þým aðý ný in þa et mek) im kan sýz dýr.

Her bi rin de re ce si d olan n kö þe li bir graf ta ke nar var dýr. Ge nel ola rak, de -

re ce ler top la mý s olan bir graf ta ki ke nar sa yý sý

Ö Ör nek:
r nek:
21 þe hir bu lu nan bir ül ke de, her bir þe hir den tam ola rak di ðer 7 þeh re di rekt uçu þun
ol du ðu bir uçuþ prog ra mý nýn im kan sýz ol du ðu nu gös te ri niz. (A dan B ye bir gi diþ var sa B
den de A ya dö nüþ var dýr.)
Çö züm:
Çö züm:

Oluþ tu ru la cak graf ta her bir kö þe nin de re ce si 7 ola ca ðýn dan bir kö þe den çý kan ke nar
sa yý sý 7 dir. Bu na gö re 21 kö þe için top lam ke nar sa yý sý oldu ðun dan so ru da

ve ri len þart lar da bir uçuþ prog ra mý ný yap mak im kan sýz dýr.

Ö Ör nek:
r nek:
6 ki þi den olu þan bir grup ta her han gi iki si nin bi ri nin di ðe ri ni ta ný dý ðý üç ki þi ve ya her -
han gi iki si nin bir bi ri ni ta ný ma dý ðý üç ki þi var dýr. (Ta ný ma si met rik olup A, B yi ta ný yor sa B
de A yý ta nýr.)
Çö züm:
Çö züm:
Bu so ru nun çö zü mü graf için gü zel bir ör nek olup, 6 ki þi yi gra fýn 6 kö þe si ola rak alýp,
iki ki þi ara sýn da ki ta ný þýk ol ma yý da ke nar çi ze rek gös te ri riz.

Þa yet üç ki þi den her bi ri di ðe ri ni ta ný yor sa, bu üç ki þi yi iki þer li ola rak bað la yan üç ke -
nar ola cak týr. Bu da bir üç gen oluþ tu rur. Her han gi iki si nin bir bi ri ni ta ný ma dý ðý üç ki þi lik
bir grup için ise, bir bi ri ne bað lan ma yan üç kö þe ola cak týr. Bu al tý ki þi için al tý kö þe den bi -
ri ni ala lým ve bu kö þe ye A di ye lim. A nýn 3 ki þi den faz la ta ný dý ðý nýn ol ma sý de mek,
der(A) 3 de mek tir.

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