Örneklerle Veri Yapısındaki Grafik Türleri
Sarah Chen
Grafik, köşelerden ve kenarlardan oluşan doğrusal olmayan bir veri yapısıdır. Köşeler bilgi veya verileri içerir ve kenarlar, köşe çifti arasında bir bağlantı görevi görür.
Grafikler, düğümlerin ve kenarların konumuna bağlı olarak birden fazla türde olabilir. İşte bazı önemli Grafik türleri:
Yönlendirilmiş grafik
Yönlendirilmiş Grafiğin kenarları yön anlamına gelen okları içerir. Ok, kenarın nereye işaret ettiğini veya nerede bittiğini belirler.
İşte Yönlendirilmiş Grafiğin bir örneği.
- A noktasından D noktasına gidebiliriz.
- Ancak kenarlar A'dan D'ye gittiğinden D düğümünden A düğümüne gidemeyiz.
- Grafiğin ağırlıkları olmadığından, A noktasından D noktasına seyahat etmek, D'den F'ye seyahat etmekle aynı maliyete sahip olacaktır.
Yönsüz Grafik
Yönlendirilmemiş Grafik, işaretçileri olmayan kenarlar içerir. Bu, iki köşe arasında tam tersi şekilde seyahat edebileceğimiz anlamına gelir.
İşte yönlendirilmemiş Grafiğin basit bir örneği.
Yukarıdaki Grafikte,
- A'dan B'ye gidebiliriz
- B'den A'ya da gidebiliriz
- Kenarlar yön içermez.
Bu, sonlu sayıda köşe ve kenara sahip, ağırlıksız, yönlendirilmemiş bir grafik örneğidir.
Ağırlıklı Grafik
Kenarlarında ağırlık veya maliyet bulunan grafiğe ağırlıklı grafik denir. Sayısal değer genellikle bir tepe noktasından diğer tepe noktasına taşınma maliyetini temsil eder. Hem Yönlendirilmiş hem de Yönlendirilmemiş Grafiğin kenarlarında ağırlıklar bulunabilir.
Burada ağırlıklı bir grafik (Yönlendirilmiş) örneği verilmiştir.
- A'dan B'ye bir kenar var ve ağırlık 5, bu da A'dan B'ye gitmenin bize 5'e mal olacağı anlamına geliyor.
- A noktasından B'ye doğru, ancak bu Grafikte B'nin A üzerinde doğrudan bir kenarı yoktur. Yani B'den A'ya gidemeyiz.
- Ancak A'dan F'ye gitmek istersek birden fazla yol vardır. Yollar ADF, ABF'dir. ADF'nin maliyeti (10+11) veya 21'dir.
- Burada ABF yolunun maliyeti (5+15) veya 20 olacaktır. Burada yoldaki her bir kenarın ağırlığını ekliyoruz.
Aşağıda ağırlıkları olan Yönlendirilmemiş Grafik örneği verilmiştir:
Burada kenarın ağırlığı vardır ancak yönü yoktur. Yani, A noktasından D noktasına seyahat etmenin 10 dolara mal olacağı ve bunun tersinin de geçerli olacağı anlamına gelir.
Çift Yönlü Grafik
Çift yönlü ve yönsüz grafların ortak bir özelliği vardır. Yani
- Genel olarak, yönlendirilmemiş Grafiğin iki köşe arasında bir kenarı olabilir.
Örneğin:
- Burada A'dan D'ye veya D'den A'ya gitmek 10 dolara mal olacak.
- Çift Yönlü Grafikte iki köşe arasında iki kenara sahip olabiliriz.
İşte bir örnek:
A'dan D'ye gitmek bize 17'ye, D'den A'ya gitmek ise 12'ye mal olacak. Yani yönsüz bir grafikse iki farklı ağırlık atayamayız.
Sonsuz Grafik
Grafik sonsuz sayıda kenar ve düğüm içerecektir. Bir grafik Sonsuzsa ve aynı zamanda bağlantılı bir grafikse, o zaman sonsuz sayıda kenar da içerecektir. Burada uzatılmış kenarlar, bu düğümlere kenarlar aracılığıyla daha fazla kenarın bağlanabileceği anlamına gelir.
İşte sonsuz Grafiğin bir örneği:
Boş Grafik
Boş Grafik yalnızca düğümleri veya köşeleri içerir ancak kenarları yoktur. V'nin köşeler ve E'nin kenarlar olduğu bir G = (V, E) Grafiği verilirse, E kenar sayısı sıfırsa bu boş olacaktır.
İşte bir Boş Grafik örneği:
Önemsiz Grafik
Kenarları olmayan yalnızca bir köşe veya düğüm mevcutsa, bir grafik veri yapısı önemsiz kabul edilir.
İşte Önemsiz Grafiğin bir örneği:
Çoklu Grafik
İki köşe arasında birden fazla kenar mevcut olduğunda veya köşede bir döngü bulunduğunda, bir grafiğe çoklu grafik denir. Grafik Veri Yapısındaki “Döngü” terimi, aynı düğüme veya tepe noktasına işaret eden kenar anlamına gelir. Multigraph yönlendirilmiş veya yönlendirilmemiş olabilir.
İşte bir Çoklu Grafik örneği:
B'den A'ya iki kenar var. Üstelik E köşesinin kendi kendine döngüsü var. Yukarıdaki Grafik, kenarlarında ağırlık olmayan yönlü bir grafiktir.
Grafiği Tamamla
Her köşenin diğer tüm köşelerle birlikte yönlendirilmiş veya yönlendirilmemiş kenarları varsa bir grafik tamamlanır.
Toplam V sayıda köşe olduğunu ve her köşenin tam olarak V-1 kenarlarına sahip olduğunu varsayalım. Daha sonra bu Grafiğe Tam Grafik adı verilecektir. Bu Graph türünde her köşe diğer tüm köşelere kenarlar aracılığıyla bağlanır.
İşte beş köşeli Tam Grafiğin bir örneği:
Resimde toplam düğüm sayısının beş olduğunu ve tüm düğümlerin tam olarak dört kenarı olduğunu görebilirsiniz.
Bağlı Grafik
Bir düğümden veya tepe noktasından başlarsak ve başlangıç düğümünden tüm düğümleri hareket ettirirsek, Grafik Bağlantılı grafik olarak adlandırılır. Bunun için her düğüm çifti veya köşe arasında en az bir kenar bulunmalıdır.
Aşağıda bir Bağlantılı Grafik örneği verilmiştir:
Yukarıdaki “tam grafik örneği” Grafiğinin bazı açıklamaları:
- C ve F arasında kenar olmadığını varsayarsak, A'dan G'ye gidemeyiz. Ancak C'den F'ye olan kenar, belirli bir düğümden herhangi bir düğüme gitmemizi sağlar.
- Tam bir Grafik, Bağlantılı bir Grafiktir çünkü verilen Grafikteki bir düğümden başka herhangi bir düğüme geçebiliriz.
Döngüsel Grafik
Grafikte bir veya daha fazla döngü mevcutsa, grafiğin döngüsel olduğu söylenir.
İşte Döngüsel Grafiğin bir örneği:
Burada A, B ve C köşeleri bir döngü oluşturur.
Bir grafiğin içinde birden fazla döngü bulunabilir.
Yönlendirilmiş Asiklik Grafik (DAG)
Bir grafiğin içinde döngü yoksa, Grafiğe Yönlendirilmiş Döngüsel Olmayan Grafik veya DAG adı verilir. DAG şunları yaparken önemlidir: Topolojik Sıralama veya infaz emrini bulmak. DAG ayrıca planlama sistemleri oluşturmak veya kaynak bağımlılığını taramak vb. için de önemlidir. Ancak yukarıdaki Grafik, içinde herhangi bir döngü içermez.
Yönlendirilmiş Döngüsel Olmayan Grafiğin (DAG) basit bir örneğini burada bulabilirsiniz:
Döngü Grafiği
Döngü Grafiği döngüsel Grafik ile aynı değildir. Döngü Grafiğinde, her düğümün tam olarak birbirine bağlı iki kenarı olacaktır, bu da her düğümün tam olarak iki dereceye sahip olacağı anlamına gelir.
İşte bir Döngü Grafiği örneği:
İki Parçalı Grafik
Bu tür Grafikler köşelerin iki kümeye atandığı özel Grafik türleridir.
İki Parçalı Grafik şu kurala uymalıdır:
- İki köşe kümesi farklı olmalıdır; bu, tüm köşelerin iki gruba veya kümeye bölünmesi gerektiği anlamına gelir.
- Aynı küme Köşeler herhangi bir kenar oluşturmamalıdır.
Euler Grafiği
Tüm köşelerin çift sayılı dereceleri varsa, grafik veri yapıları bir Euler Grafiği olarak kabul edilir. Köşe derecesi terimi, belirli bir köşeyi işaret eden veya belirli bir köşeden dışarı bakan kenarların sayısı anlamına gelir.
İşte bir Euler grafiği örneği:
Tüm köşelerin eşit dereceleri vardır. A, D, E ve H köşelerinin iki derecesi vardır. Burada C düğümünün dört derecesi vardır ve bu da çifttir.
Hamilton Grafiği
Hamilton Graph, aynı düğümü tekrar ziyaret etmeden veya aynı kenarı kullanmadan, belirli bir köşedeki tüm köşeleri ziyaret edebileceğiniz bir Bağlantı Grafiğidir. Bu tür Bağlantılı Grafikler “Hamilton Grafiği” olarak bilinir. Verilen Grafiğin Hamilton Grafiği olup olmadığını doğrulamak için ziyaret ettiğiniz yol Hamilton Yolu olarak bilinir.
İşte Hamilton'un basit bir grafik örneği:
Bu görüntüde, yukarıdaki Grafikteki herhangi bir düğümün tüm köşelerini ziyaret edebiliriz. Yollardan biri olabilir ADCHBE. Bir Hamilton Döngüsü bulmak da mümkündür. Hamilton Döngüsü aynı tepe noktasında başlar ve biter. Yani Hamilton Döngüsü şu şekilde olacaktır: ADCHBEA.
