Page 235 - OLİMPİK SONLU MATEMATİK
P. 235
ÇÝZGE KURAMI (GRAF)
eo rem:
T Teo rem:
Bir graf ta, tek de re ce li kö þe le rin sa yý sý çift tir.
s pat:
Ý Ýs pat:
Gra fýn kö þe le ri V , V , V , …, V ol sun. V , V , V , …, V kö þe le ri nin de re ce si tek ve
1 2 3 n 1 2 3 t
V , V , V , …, V kö þe le ri nin de re ce le ri de çift ol sun. Gra fýn de re ce ler top la mý nýn çift
t+1 t+2 t+3 n
sa yý ol du ðu ger çe ði (te ore mi)nden yo la çý ka rak,
d(V ) + d(V ) + ... + d(V ) + d(V ) + d(V ) + ... + d(V ) = 2e ise
1 2 t t+1 t+2 n
d(V ) + d(V ) + ... + d(V ) = 2e – (d(V ) + d(V ) + ... + d(V ) den
1 2 t t+1 t+2 n
d(V ) + d(V ) + ... + d(V ) = Çift sa yý ol ma lý dýr. t ta ne te kin top la mý nýn çift ol ma sý de -
1 1 t
mek, t nin çift ol ma sý de mek tir. Çift sa tý da te kin top la mý çift ya par.
Ö Ör nek:
r nek:
10 ta ne þeh rin ol du ðu bir ül ke de, in þa edi len yol aðý þe hir le ri bir bi ri ne bað lý yor ve her -
han gi iki yol bir bi ri ile ke siþ mi yor.
1) Bu ül ke de, her bir þe hir den çý kan 4 yol var sa, top lam kaç yol var dýr?
2) Bu ül ke de 6 þeh rin her bi rin den 5 yol ve di ðer 4 þeh rin her bi rin den de 5 yol çý -
ký yor sa, ül ke de ki top lam yol la rýn sa yý sý kaç týr?
3) Bu ül ke de ki 5 þeh rin her bi rin den 5 yol ve di ðer 5 þeh rin her bi rin den 4 yol çý ka -
cak þe kil de bir yol aðý oluþ tur mak müm kün mü dür?
Çö züm:
Çö züm:
1) 10 ta ne Ül ke nin her bir þe hir den çý kan 4 yo lun ol ma sý de mek, graf ta 10 kö þe nin
ol ma sý ve her bir kö þe nin de re ce si nin 4 ol ma sý de mek tir. Ya ni her kö þe ye ge len
(gi den) 4 ke nar var dýr. Bu na gö re de re ce ler top la mý 4×10 = 40 olup, her bir ke -
nar iki de fa sa yý la ca ðýn dan (AB ile BA gi bi) graf ta top lam; 40 : 2 = 20 ke nar bu -
lu nur. O hal de bu yol aðýn da top lam 20 yol var dýr?
2) De re ce si 6 olan 6 kö þe için 6×6 = 36 ke nar ve de re ce si 5 olan dört kö þe için
4×5 = 20 ke nar olup, ke nar iki de fa sa yýl dý ðýn dan ke nar var dýr. O
hal de ve ri len þart lar da, ula þým aðýn da top lam 28 yol var dýr.
234 Tübitak Ulusal Matematik Olimpiyatlarýna Hazýrlýk
