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

ÇÝZGE KURAMI (GRAF)
A ile B ara sýn da ki en ký sa yol A ile B ara sýn da ki uzak lýk týr. Bu uzak lýk d(A, B) þek lin de
gös te ri lir.
Baþ la dý ðý kö þe de bi ten yo la dön gü de nir.

Alý nan her fark lý iki li için A dan B ye yol olan gra fa bað lan tý lý graf de nir.
Dön gü ol ma yan bað lan tý lý gra fa aðaç de nir. Bir aðaç ta n kö þe var sa n – 1 ke nar var dýr.
Dön gü ol ma yan bað lan tý sýz gra fa or man de nir.

a ným:
T Ta ným:

Bir graf ta her yol bir ke re kul la ný la rak tüm kö þe ler do la þý la bi li yor sa bu gra fa Eu ler Yo -
lu var dýr de nir. Eu ler yo lu bir dön gü ise bu na da Eu ler dön gü sü de nir. Eu ler yo lu fark lý
kö þe ler de baþ lar ve bi ter ken Eu ler dön gü sü ay ný kö þe de baþ lar ve bi ter.
Aþa ðý da ve ri len Eu ler yo lu; BBADC DEBC

Di ðer bir Eu ler yo lu ise; CDCBBA DEB dir.

Bir graf ta her kö þe den bir ke re ge çe rek tüm kö þe ler do la þý la bi li yor sa bu gra fta Ha mil -
ton Yo lu var dýr de nir.

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