Graflar

GRAFLAR

Merhaba arkadaşlar,

Bugünkü yazımda sizlerle graflar hakkındaki bilgilerimi paylaşacağım. Graf tanımı olarak çok kısa ve net bir tanım vereceğim.

Graf : Bilgi parçaları arasındaki ilişkileri gösterir. Bir G grafı V ile gösterilen düğümlerden (verteks) ve E ile gösterilen kenarlardan (edge) oluşur.

Matematiksel olarak modellersek  G=(V,E) şeklindeki yapı  olarak tanımlayabiliriz.

Peki ne işe yarar bu graflar nerede kullanılırlar ?

Bu sorunun yanıtı için günlük hayattan çok sayıda örnekler verebiliriz.

Ulaşım hatlarında, elektronik devrelerde, bilgisayar ağlarında, veritabanı sistemlerinde kullanıldığını görebiliriz. Hemen bir örnek ile daha açık bir hale getirelim.

Örnek :  Bursaray metrosundaki durakları ele alabiliriz.

Gördüğünüz gibi durakların birbiriyle bağlantılarını anlatan graf modelini oluşturduk.

Graflar yönlü, ağırlıklı olarak çeşitlendirilebilir ilerleyen bölümlerde ele alacağım.

Şimdi bir grafın matematiksel modelini daha ayrıntılı ele alalım.

Yukarıdaki  G grafının düğüm kümesi  {v1,v2,v3,v4} ve ayrıt kümesi {e1,e2,e3,e4,e5} tir.

f: E­­ → P(V)  fonksiyonu şöyle tanımlanmaktadır.

f : e1→ a{V1}

f : e2→ a{V1,V2}

f : e3→ a{V1,V3}

f : e4→ a{V2,V3}

f : e5→ a{V2,V3}

Bu dönüşümler sayesinde e1 ayrıtının V1 düğümünü kendisine, e2 ayrıtının V1 düğümü ile V2 düğümünü birbirine bağladığını görüyoruz.Yani kısaca V1 ve V2 noktaları arasında yönsüz olarak bir bağlantı olduğunu çıkarıyoruz.

Burada en önemli nokta şekil olarak verilen model bir graf değildir. Çünkü bir grafı farklı şekillerde birden fazla gösterebiliriz. Buda bize bir grafı bir fonksiyon ile göstermemiz gerektiğini belirtir.Graflar ile ilgili bazı tanımları yapalım.

Digraf: Bir grafta ayrıtların düğümleri bağlarken yön kavramı mevcut ise bu graflara digraflar denir.

Ağırlıklı Graf: Graftaki her bir ayrıtın kendine ait ağırlıkları mevcut ise bu graflara ağırlıklı graf denir.

Komşuluk : e1, e2 grafın 2 ayrıtı olsun. Eğer e1 ve e2 nin bağlı olduğu ortak bir düğüm var ise bu ayrıtlar birbirine komşudur.

Derece: Bir v düğümünün derecesi kendisine bağlı olan ayrıt sayısıdır. Eğer  bir ayrıt v yi kendisine bağlıyor ise ve herhangi bir belirtme yapılmamış ise bu ayrıt v düğümünün derecesini 2 arttırır.

KomşulukMatrisi: Graflar için önemli bir tanımdır.Bir G grafında V={vq,v2,…,vn} düğüm kümesi olsun.

Aij , vi düğümünün vj düğümüne bağlantılı olup olmadığını ve bağlantı sayısını belirtir.  Örnek olarak ;

Grafının komşuluk matrisini oluşturalım.

Şeklinde oluştururuz burada satırlar ve sütunlar düğümleri matristeki değerlerde o düğümler arasındaki ayrıt sayısını vermektedir. Dikkat ettiyseniz matrisimiz köşegene göre simetriktir.Komşuluk matrisleri eğer graf yönlü bir graf değil ise her zaman simetriktir.  Ve matrisimiz daima nxn lik kare matristir ki buradaki n değişkeni düğümler kümesindeki toplam düğüm sayısına eşittir. A² matrisimizde grafın herhangi bir düğümünün 2 birim uzaklıkla ulaşabildiği düğümleri belirtir. Aynı şekilde Aⁿ matriside n birim uzaklıkla ulaşılabilen düğümleri belirtir. A.A = A² matris işlemiyle herhangi bir düğümden 2 birim uzaklıkla ulaşılabilen düğümleri görebiliriz.

YOLLAR ve DEVRELER :

Yol: Bir yol v1 den vn e kadar sıralı düğümleri  (v1,v2), (v2,v3),…(v(n-1),vn)  ayrıtlarıyla birbirine bağlar.Eğer bu yol boyunca herhangi bir düğüm tekrarı yok ise bu yol Basit Yol olarak adlandırılır.

Çevre:  Başlangıç ve bitiş noktaları aynı düğüm olan yollara çevre denir. Eğer çevre içerisinde düğüm tekrarı yok ise basit çevre olarak adlandırılır. 

Örnek :  v2,v3,v4,v5,v3,v2 bir çevre, v2,v3,v4,v2 ise basit çevredir.

Euler ve Hamilton teoremleri ile ilgili ilerleyen zamanlarda yazacağım.