ÇİZGE KURAMINA GİRİŞ

Çizge, boş kümeden farklı noktalar kümesiyle bu noktalar arasındaki çizgilerin kümesinden oluşur.

Köşe noktalarının arasındaki çizgilere kenar denir. Çizgenin bir kenarından bahsetmek için onun iki uç noktası söylenmesi yeterlidir. Örneğin, h ve b köşe noktalarını birleştiren kenarı hb 'dir.

Şekildeki çizgenin noktalar kümesi; H={e, g, m, p, s, z} şeklindedir.

Köşe noktalarının arasındaki çizgilere ise kenar denir. Çizgenin bir kenarından bahsetmek için onun iki uç noktasını söylemek yeterlidir. Çizgenin tüm kenarlarının kümesi B ise; B={ep, gp, mp, ms, ps, se, sz} şeklinde gösterilir.

Çizgelerin oluşturduğu noktalar kümesi Z={a, b, c, d} 'dir. e noktası noktalar kümesinde yer almaz. Çünkü e noktası Z'de bulunan herhangi bir nokta ile bir çizgi ile bağlantı oluşturmamaktadır.

Şekilde verilen çizgenin tüm kenarlarının kümesi olan S={cd, bd, ad, ac, ab, bc}'dir.

Çizgenin noktalar kümesi D={c, d, b, e, a, f, g} şeklindedir.

Verilen çizgede d köşe noktasıyla f, e, b ve c noktaları birleştiğinde bir kenar oluşturmaktadır.

Basit veya yalın çizge adı verilen yani bir köşe noktasından kendisine kenarı olmayan, iki köşe noktası arasında en fazla bir kenarı olan, kenarları yönlendirilmemiş ve sonlu sayıda köşe noktası olan çizgelerdir.

d köşe noktasından çıkan kenar sayısı 3, c köşe noktasından çıkan kenar sayısı 2, b köşe noktasından çıkan kenar sayısı 2, a köşe noktasından çıkan kenar sayısı 3, g köşe noktasından çıkan kenar sayısı 2, f köşe noktasından çıkan kenar sayısı 2, e köşe noktasından çıkan kenar sayısı 6'dır.

Bir çizgedeki tüm köşe noktalarının dereceleri toplamı çizgedeki kenar sayısının iki katına eşit olması durumudur.

Şekilde verilen her bir noktayı bir birey olarak düşünüp, bireylerin diğer bireyler ile tokalaşma sayısı o noktanın derecesini verir. s noktasına baktığımızda; s noktası p, z , mve e noktaları ile bir çizgi oluşturmuştur. Dolayısıyla s nin derecesi 4'dür. Doğru cevap D'dir.

d köşe noktasından çıkan kenar sayısı 3, c köşe noktasından çıkan kenar sayısı 3, b köşe noktasından çıkan kenar sayısı 3, a köşe noktasından çıkan kenar sayısı 3'dür. çizgeolayısıyla 3*4=12 olarak bulunur.

Şekilde verilen çizgenin ayrıt, diğer bir ismiyle kenar sayısı, sayısı 9 iken köşe sayısı 6'dır.

Her köşeden diğer köşeye geçen kenarları bir kez sayarsak ayrıt sayısı 10 olur ve şekilde 6 tane noktadan çizgi geçtiğinden köşe sayısı 6'dır.

Verilenler Euler formülünde yerine yazılırsa,

bölge sayısı+6=8+2 olup buradan bölge sayısı=4 olarak bulunur.

Bir çizgenin köşe noktaları, aynı kümenin herhangi iki köşe noktası arasında kenar olmayacak şekilde A ve B gibi iki kümeye ayrılabiliyorsa,
bu tür çizgelere iki kümeli çizge denir.

A = {a, b,c, d} ve B = {e, f , g} olmak üzere iki kümeli bir çizge olarak ifade edebiliriz.

Dört renk teoremi, her düzlemsel çizgenin köşe noktaları komşu noktalar farklı renklerde olacak şekilde dört renkle boyanabilmesidir.

Teorem (Brook, 1941), bir çizgenin tüm köşe noktalarının derecesi en fazla d ise bu çizgenin köşe noktaları, komşu noktalar farklı renklerde olacak şekilde d + 1 renk ile boyanabilmesidir.