Graf Teorisi I

Graflar, ayrık matematiğin çok popüler bir konusudur. Bunlar, nesnelerin sınırlı bir koleksiyonunu ve aralarındaki çiftli ilişkileri temsil eder. Örnek: Bir “arkadaşlık grafiği”, bize hangi gruptaki insanların arkadaş olduğunu söyler.

Grafları tanımlamak için, kümelerle ilgili birkaç temel şeyi bilmemiz gerekir.

Kümeler

Bir küme farklı nesnelerin iyi tanımlanmış sırasız bir koleksiyonudur. Bir kümeyi oluşturan nesneler herhangi bir şey olabilir: rakamlar, insanlar, alfabe harfleri vs…Kümedeki her eleman tam olarak bir kez oluşur.

Şöyle bir küme örneği belirleyebiliriz:

P = {Ali, Burak, Can}

Bu, {Burak, Ali, Can} ile aynıdır. Kümenin elemanları sırasızdır. Küme üyeliğini şu şekilde ifade ederiz:

Ayrıca diğer kümelerden oluşan kümeleri ele alabiliriz. Örneğin, F kümesi, P içindeki insan çiftlerinin arkadaş olanlarını gösterebilir:

F = {{Ali, Burak}, {Ali, Can}}

Her seferinde büyük veya sonlu kümelerle çalışmamız gerekecek. Bu gibi durumlarda, tüm elemanları listelemek iyi bir seçenek değildir; bu nedenle, elemanların yerine getirmesi gereken bir yüklem tarafından bir gruba üyelik belirtiriz.

E = {n: n çift tam sayı}
= {n: k bir tam sayıdır, n = 2k}

Bazı kümeler standart adlara sahiptir, boş set için ø, tam sayılar için Z, doğalsayılar için N, gerçel sayılar için R gibi…

Kardinalite (Nicelik): Kardinalite |A|, sonlu A kümesinin elemanlarının sayısıdır. Yukarıdaki örneklerde, |P| = 3, |F| = 2 ve |E| tanımsızdır çünkü E  kümesi sonsuzdur.

Kümeler arasındaki ilişkiler ve kümeler üzerinde işlemler: Diyelim ki A, B’nin alt kümesidir o halde A⊆B şeklinde ifade ederiz. Eğer A’nın her elemanı B’nin de bir elemanıysa A kapsanır B veya A, B’nin öz altkümesidir diye ifade ederiz.Gösterimi:A⊂B şeklinde olur. A, B’nin bir alt kümesidir fakat eşit değildirler.

Dikkat!: ⊆, ⊂, ∉ ifadelerini karıştırmayalım.

A ve B kümelerinin birleşimi (A∪B), A veya B’de bulunan şu elemanlardan oluşur:

(A∪B) = {x: x∈A veya x∈B}

A ve B kümelerinin kesişimi (A∩B), hem A’da hem B’de bulunan şu elemanlardan oluşur:

(A∩B) = {x:x∈A ve x∈B}

Eğer A∩B = Ø ise A ve B ayrık kümelerdir. Küme farkı (A-B) ise A kümesinde olup B’de olmayan elemanları kapsar.

A – B = {x: x∈A ve x∉B}

A kümesinin tümleyeni (A’) ise A kümesi dışındaki elemanları ifade eder.

A’={x:x∉A}

 Örneğin, tamsayılar hakkında konuşursak, çift sayılar kümesinin tümleyeni tek sayılar kümesidir.

Graflar

Basit bir graf bir çift kümedir (V,E) burada V boş olmayan sonlu bir kümedir. E ise V’nin iki elemanlı alt kümeleridir.

V (vertices) elemanları köşeler olarak adlandırılır; E (edges) elemanları kenarlar olarak adlandırılır.

Dikkat edin {v,v} kenar değildir. Çünkü {v,v} = {v}, V’nin 1 elemanlı bir altkümesidir.

Örnek: G = (V,E)

V = {a,b, c, d, e}
E = {{a, b}, {b, c}, {a, c}, {c, d}}

G grafı, 5 köşe 4 kenardan oluşur. Grafik küçük olduğunda, bu durumda olduğu gibi, diyagramını rahatlıkla çizebiliriz. Noktaların konumu ve kenar şekilleri önemli değildir.Grafın şekli Şekil-1’deki gibidir.

 

Şekil-1

Eğer {u,v} bir kenarsa u köşesi v köşesine bitişiktir veya komşudur denilir. v köşesinin derecesi deg(v) v’nin komşu köşe sayıları kadardır. Örneğin G’de, a’nın ve b’nin derecesi 2, c’nin derecesi 3, d’nin derecesi 1 ve e’nin derecesi 0’dır.

Önsav: Tüm köşelerin derece toplamı kenar sayısının iki katına eşittir.

Gerçekten de G’nin 4 kenarı ve toplam derecesi 8’dir.