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

ÇÝZGE KURAMI (GRAF)
12. BÖLÜM
þek lin de bir graf la da gös te rim ya pa bi li riz. Bu ra da nes ne ler þe hir iken, iki nes ne ara sýn da ki
iliþ ki ise iki nes ne (þe hir) in or tak sý nýr la rý nýn ol ma sý dýr. Bu iliþ ki de çiz gi ile be lir til miþ tir.
Aþa ðý da ve ri len üç graf da ay ný olup, V , V , V , V kö þe, bu iki li le ri bir leþ ti ren doð ru
1 2 3 4
par ça la rý [V V ], [V V ], [V V ], [V V ], [V V ], [V V ] ke nar lar dýr.
1 2 1 3 1 4 2 3 2 4 3 4

Gra fýn þek li ve kö þe le ri nin ye ri için her han gi bað la yý cý bir du rum yok tur. Eðer iki graf
ara sýn da bi re-bir ve ör ten lik var sa bu iki gra fa iso morp hic (izo mor fik) graf lar de nir. Ya ni iki
graf ay ný ya pý da de mek tir.

Gra fýn Ge nel Ta ný mý
V: Kö þe le rin oluþ tur du ðu kü me, V = {V , V , V , …, V } gi bi.
1 2 3 n
E: Ke nar la rýn oluþ tur du ðu kü me, E = {[V V ], [V V ], [V V ], …, [V V ]} gi bi.
1 2 1 3 1 4 n 1
V E = ve g : V×V E þek lin de bir eþ le me dir.
V V, E E, ise G = (V , E ) gra fý G = (V, E) gra fý nýn bir alt gra fý dýr. Ya ni, G nün
tüm kö þe le ri G nin kö þe le ri ve G nün tüm ke nar la rý G nin ke nar la rý dýr.
Aþa ðý da ve ri len G ve G graf la rý G gra fý nýn bir alt gra fý dýr.
1 2

V ve V kö þe le ri ni bir leþ ti ren bir ke nar var sa, V ve V ye kom þu kö þe ler de nir. Ýki kö þe
i j i j
kom þu kö þe ler de ðil se kom þu ol ma yan kö þe ler dir. Eðer V kö þe si e ke na rý nýn so nu ise bu kö -
þe ye in ci dent de nir. Bir ke nar bir kö þe yi ken di si ne eþ li yor sa bu kö þe ye Ýl mek (lo op) de nir.
Ay ný iki kö þe yi bir leþ ti ren iki ke na ra pa ra lel ke nar de nir.

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