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

ÇÝZGE KURAMI (GRAF)
12. BÖLÜM

Bir gra fýn ke nar ve kö þe sa yý sý son lu sa yý da ise bu gra fa son lu graf de nir. Kö þe ve ya ke -
nar sa yý sý son suz sa yý da olan gra fa da son suz graf de nir. Bir gra fýn kö þe sa yý sý na gra fýn mer -
te be si de nir.

Graf ýn tü rü be lir til me di ði müd det çe ve ri len graf son lu ba sit graf týr.

a ným:
T Ta ným:
Bir kö þe den çý kan ke nar la rýn sa yý sý na o kö þe nin de re ce si
de nir. Bir kö þe de il mek (lo op) var sa, il mek (lo op) kö þe nin de -
re ce si ni iki art tý rýr. Bir kö þe nin de re ce si deg(V) þek lin de gös -
te ri lir.

deg(V ) = 3,
1
deg(V ) = 2
2
deg(V ) = 5 tir.
3

eo rem:
T Teo rem:
V: Kö þe le rin oluþ tur du ðu kü me, V = {V , V , V , …, V } olan her han gi bir graf ta ke nar
1 2 3 n
sa yý sý e ol mak üze re, aþa ðý da ki eþit lik sað la nýr.
deg(V ) + deg(V ) + ... + deg(V ) = 2e
1 2 n
Her bir kö þe si nin de re ce si d olan n kö þe li bir graf ve ri li yor. Bu na gö re, graf ta ki top lam ke-

nar sa yý sý, dir. Daha ge nel bir ifa dey le, graf ta ki kö þe le rin de re ce le ri top la mý s ise,

graf ta ki ke nar sa yý sý,

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