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

ÇÝZGE KURAMI (GRAF)
12. BÖLÜM
a ným:
T Ta ným:

Ke nar la rý yön len di ril miþ ba sit gar fa yön lü graf de nir.

r nek:
Ö Ör nek:
n þeh rin bu lun du ðu bir ül ke de her iki þe hir ara sý tek yön lü uçak se fer le ri var dýr. Öy le
bir þe hir var dýr ki, bir ak tar may la her þeh re ula þý la bi le ce ði ni gös te ri niz.
Çö züm:
Çö züm:
Bir þe hir den çý kan yol la rýn sa yý sý nýn o kö þe nin de re ce si ol du ðu nu bi li yo ruz. De re ce si
en bü yük olan þe hir A þeh ri ol sun. A þeh rin den V , V , …, V þe hir le ri ne yol ol sun. Farz
1 2 m
ede lim ki, A þeh rin den B þeh ri ne yol ol ma sýn. O za man B þeh rin den V , V , …, V , A þe -
1 2 n
hir le ri ne yol var dýr. Bu ra dan da B nin de re ce si, A nýn de re ce sin den (deg(b) > deg(A)) bü -
yük ol du ðu el de edi lir ki, bu du rum De re ce si en bü yük olan þe hir A þeh ri ol sun ile çe li þir.

a ným:
T Ta ným:
Tüm kö þe le rin de ki de re ce le ri ay ný r sa yý sý na eþit olan gra fa bir r-düz gün graf de nir. Bu
þe kil de ki bir graf ta 2e = vr ola ca ðýn dan v ve r den en az bi ri si nin çift sa yý ol ma sý ge rek ti ði
gö rü lür. Ör ne ðin her kö þe sin den üç yol çý kan 11 kö þe li bir graf ola maz.

a ným:
T Ta ným:
A ve B gi bi iki kö þe ara sýn da ki yol e , e , …, e þek lin de son lu bir di zi oluþ tur sun. e ke -
1 2 k 1
na rý, A ile V i bir leþ tir sin, e ke na rý, V ile V yi bir leþ tir sin. Bu þe kil de de vam ede rek e
1 2 1 2 k
ke na rý V ile B yi bir leþ tir sin. Bu ra da ki, A dan B ye ulaþ tý ran her bir bað lan tý ya pa ti ka
k – 1
(ro ta) ve k po zi tif tam sa yý sý na pa ti ka nýn uzun lu ðu de nir.

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