Graflar (Veri Yapıları)

Graf veri yapısı, bilgisayar bilimlerinde nesneler arasındaki ilişkileri ve bağlantıları göstermek amacıyla kullanılan doğrusal olmayan veri yapılarından biridir. Graf yapıları günlük hayatta karşılaşılan birçok sistemi modellemek için kullanılmaktadır. Sosyal medya ağları, şehirler arası yollar, bilgisayar ağları ve öneri sistemleri graf veri yapısının kullanım alanları arasında yer almaktadır. Graf veri yapısı düğümler (node veya vertex) ve bu düğümler arasındaki bağlantıları temsil eden kenarlardan (edge) oluşmaktadır.

Graf yapısında düğümler varlıkları temsil ederken, kenarlar bu varlıklar arasındaki ilişkileri göstermektedir. Örneğin sosyal ağlarda insanlar düğüm olarak ifade edilirken, arkadaşlık veya takip ilişkileri kenarlar ile gösterilmektedir. Şehirler arası yolların gösterildiği haritalarda şehirler düğüm, yollar ise kenar olarak değerlendirilmektedir.

Düğümler, graf içerisinde bulunan nesneleri temsil etmektedir. Bir kullanıcı, şehir, bilgisayar veya web sayfası bir düğüm olabilir.

Kenarlar düğümler arasındaki bağlantıları göstermektedir. İki düğüm arasındaki ilişki kenarlar ile ifade edilmektedir.

_{Şekil 1. Düğümler ve bağlantılardan oluşan örnek bir graph yapısı.}

Graf veri yapıları sahip oldukları özelliklere göre farklı türlere ayrılmaktadır.

Yönlü graf yapısında kenarlar belirli bir yön bilgisi içermektedir. Bir düğümden diğer düğüme geçiş tek yönlü olabilir.

Örneğin bir sosyal medya platformunda bir kullanıcının başka bir kullanıcıyı takip etmesi yönlü graf yapısına örnek olarak gösterilmektedir. Bir kişinin başka bir kişiyi takip etmesi, karşı tarafın da aynı kişiyi takip ettiği anlamına gelmemektedir.

Yönsüz graf yapısında kenarlar herhangi bir yön bilgisi içermez. İki düğüm arasındaki bağlantı karşılıklıdır.

Arkadaşlık ilişkileri yönsüz graf yapısına örnek olarak verilebilmektedir. Bir kişi başka biriyle arkadaş olduğunda bağlantı her iki taraf için de geçerlidir.

Ağırlıklı graf yapısında kenarlara sayısal değerler atanabilmektedir. Bu değerler uzaklık, süre, maliyet veya bant genişliği gibi bilgileri temsil etmektedir.

Şehirler arasındaki uzaklıkların gösterildiği haritalar ağırlıklı graf kullanımına örnek olarak gösterilmektedir.

Ağırlıksız graf yapısında tüm bağlantılar eşit kabul edilmektedir. Kenarlar arasında herhangi bir ağırlık değeri bulunmamaktadır.

Basit sosyal ağ sistemleri ağırlıksız graf örnekleri arasında yer almaktadır.

Döngülü graf yapısında bir düğümden başlanarak tekrar aynı düğüme ulaşılabilmektedir. Bu durum graf içerisinde döngü bulunduğunu göstermektedir.

Bazı ulaşım ağları döngülü graf yapısına örnek olarak gösterilmektedir.

Döngüsüz graf yapısında herhangi bir döngü bulunmamaktadır. Başlanan düğüme tekrar ulaşılamamaktadır.

Aile soy ağacı döngüsüz graf yapısına örnek olarak verilmektedir.

Bağlantılı graf yapısında her düğüm diğer düğümlere doğrudan veya dolaylı şekilde ulaşabilmektedir.

Bilgisayar ağlarında tüm cihazların birbirine erişebilmesi bağlantılı graf yapısına örnek oluşturmaktadır.

Bağlantısız graf yapısında bazı düğümler arasında herhangi bir bağlantı bulunmamaktadır.

Birbirinden bağımsız kullanıcı grupları bağlantısız graf örneği olarak değerlendirilmektedir.

Bipartite graf yapısında düğümler iki farklı kümeye ayrılmaktadır. Aynı küme içerisinde bulunan düğümler kendi aralarında bağlantı kuramamaktadır.

Öğrenci ve ders sistemleri bipartite graf yapısına örnek olarak gösterilmektedir. Öğrenciler ile dersler arasında bağlantı kurulurken aynı grup içerisindeki düğümler arasında bağlantı bulunmamaktadır.

Tam graf yapısında her düğüm diğer tüm düğümler ile bağlantılıdır.

Küçük sosyal gruplarda herkesin birbirini tanıdığı yapılar tam graf örneği olarak değerlendirilmektedir.

Dijkstra algoritması, graf veri yapılarında iki düğüm arasındaki en kısa yolu bulmak amacıyla kullanılan algoritmalardan biridir. Özellikle ağırlıklı graf yapılarında kullanılmaktadır.

Navigasyon sistemlerinde şehirler arasındaki en kısa rotanın hesaplanmasında Dijkstra algoritmasından yararlanılmaktadır.

Sosyal medya platformlarında kullanıcılar arasındaki arkadaşlık ve takip ilişkileri graf veri yapıları ile modellenmektedir.

Video ve içerik öneri sistemlerinde kullanıcıların ilgi alanları graf yapıları kullanılarak analiz edilmektedir.

Şehirler ve yollar graf veri yapıları ile temsil edilmektedir. En kısa yol hesaplamalarında graf algoritmaları kullanılmaktadır.

Bilgisayarlar ve ağ cihazları arasındaki bağlantılar graf veri yapıları yardımıyla gösterilmektedir.