Graf Teorisi

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:

set1

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…

set3

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.

 

graf1Ş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.

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.