Örneklerle Veri Yapısındaki Grafik Türleri
Sarah Chen
⚡ Akıllı Özet
Veri yapılarındaki grafikler, yapılarına göre yönlü, yönsüz, ağırlıklı, döngülü, döngüsüz, tam, bağlantılı, iki parçalı, Euler ve Hamilton grafikleri gibi ailelere sınıflandırılan, doğrusal olmayan köşe ve kenar koleksiyonlarıdır.
Grafik, köşelerden ve kenarlardan oluşan doğrusal olmayan bir veri yapısıdır. Köşeler bilgi veya veriyi içerirken, kenarlar bir çift köşe arasında bağlantı görevi görür.
Düğümlerin ve kenarların konumuna bağlı olarak grafiklerin birden fazla türü olabilir. İşte bazı önemli grafik türleri:
Yönlendirilmiş grafik
Yönlendirilmiş Grafiğin kenarları, yönü belirten oklar içerir. Ok, kenarın nereye doğru yöneldiğini veya nerede bittiğini belirler. İşte yönlendirilmiş grafiğe bir örnek.
Yönlendirilmiş grafik
- A noktasından D noktasına gidebiliriz.
- Ancak, kenar A'dan D'ye doğru yöneldiği için 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ş bir grafik, işaretçi içermeyen kenarlar içerir. Bu, iki köşe arasında ters yönde seyahat edebileceğimiz anlamına gelir. İşte yönlendirilmemiş bir grafiğin basit bir örneği.
Yönsüz Grafik
Yukarıdaki Grafikte,
- A noktasından B noktasına gidebiliriz.
- B noktasından A noktasına da geçebiliriz.
- Kenarlar yön içermez.
Bu, sonlu sayıda köşeye ve ağırlığı olmayan kenarlara sahip yönsüz bir grafın örneğidir.
Ağırlıklı Grafik
Kenarlarında ağırlık veya maliyet bulunan bir grafiğe ağırlıklı grafik denir. Sayısal değer genellikle bir köşeden diğerine hareket maliyetini temsil eder. Hem yönlü hem de yönsüz grafiklerin kenarlarında ağırlıklar olabilir. İşte ağırlıklı bir grafiğe (yönlü) örnek.
Ağırlıklı Yönlendirilmiş Grafik
- A'dan B'ye bir kenar var ve ağırlığı 5, yani A'dan B'ye gitmek bize 5'e mal olacak.
- A noktası B noktasını işaret ediyor, ancak bu grafikte B noktasının A noktası üzerinde doğrudan bir kenarı yok. Bu nedenle, B noktasından A noktasına gidemeyiz.
- Ancak, A'dan F'ye gitmek istiyorsak, birden fazla yol var. Bu yollar ADF ve ABF'dir. ADF'nin maliyeti (10+11) veya 21 olacaktır.
- Burada, ABF yolu (5+15) veya 20'ye mal olacak. Burada yoldaki her kenarın ağırlığını ekliyoruz.
İşte ağırlıkları olan yönsüz bir graf örneği:
Ağırlıklı Yönlendirilmemiş Grafik
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 grafiklerin ortak bir özelliği vardır. Bu özellik şöyledir:
- Genel olarak, yönsüz bir grafikte iki köşe arasında yalnızca bir kenar bulunabilir.
Ö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:
Çift Yönlü Grafik
A'dan D'ye seyahatin maliyeti 17, D'den A'ya seyahatin maliyeti ise 12'dir. Dolayısıyla, yönsüz bir grafikte iki farklı ağırlık atayamayız.
Sonsuz Grafik
Bir grafik sonsuz sayıda kenar ve düğüm içerecektir. Eğer bir grafik sonsuz ve aynı zamanda bağlantılı bir grafik ise, sonsuz sayıda kenar da içerecektir. Burada, genişletilmiş kenarlar, bu düğümlere daha fazla kenarın bağlanabileceği anlamına gelir. İşte sonsuz bir grafın örneği:
Sonsuz Grafik
Boş Grafik
Boş bir grafik, yalnızca düğümler veya köşeler içerir, kenarları yoktur. Eğer V köşeleri ve E kenarları temsil ediyorsa, G = (V, E) grafiği boş grafik olur; eğer kenar sayısı E sıfır ise. İşte boş bir grafiğe örnek:
Boş Grafik
Önemsiz Grafik
Bir grafik veri yapısı, yalnızca bir köşe veya düğüm içeriyorsa ve kenarları yoksa, önemsiz (trivial) olarak kabul edilir. İşte önemsiz bir grafiğe örnek:
Çoklu Grafik
Bir graf, iki köşe arasında birden fazla kenar bulunduğunda veya bir köşenin bir döngüye sahip olması durumunda çoklu graf olarak adlandırılır. Grafik Veri Yapılarında "Döngü" terimi, aynı düğüme veya köşeye işaret eden bir kenarı ifade eder. Çoklu graf yönlü veya yönsüz olabilir. İşte bir Çoklu Graf örneği:
B'den A'ya iki kenar vardır. Ayrıca, E düğümü kendi kendine döngüye sahiptir. Yukarıdaki grafik, kenarlarında ağırlık bulunmayan yönlü bir grafiktir.
Grafiği Tamamla
Bir graf, her köşesinin diğer tüm köşelerle yönlü veya yönsüz kenarları varsa tam graf olarak adlandırılır. Toplam V sayıda köşe olduğunu ve her köşenin tam olarak V-1 kenarı olduğunu varsayalım. Bu graf, tam graf olarak adlandırılır. Bu tür graflarda, her köşe kenarlar aracılığıyla diğer tüm köşelere bağlıdır. İşte beş köşeli bir tam graf örneği:
Resimde de görebileceğiniz gibi, toplam düğüm sayısı beştir ve tüm düğümlerin tam olarak dört kenarı vardır.
Bağlı Grafik
Bir graf, bir düğümden veya köşeden başlayıp o düğümden tüm düğümlere gidebiliyorsak, bağlantılı graf olarak adlandırılır. Bunun için, her düğüm veya köşe çifti arasında en az bir kenar bulunmalıdır. İşte bağlantılı bir graf örneği:
Yukarıdaki bağlantılı grafiğe dair bazı açıklamalar aşağıdadır:
- 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
Bir grafikte bir veya daha fazla döngü bulunuyorsa, bu grafiğe döngüsel grafik denir. İşte döngüsel bir grafiğe örnek:
Burada A, B ve C köşeleri bir döngü oluşturuyor. Bir grafikte birden fazla döngü bulunabilir.
Yönlendirilmiş Asiklik Grafik (DAG)
Bir grafın içinde döngü yoksa, bu graf Yönlendirilmiş Döngüsüz Grafik (DAG) olarak adlandırılır. DAG, hesaplamalar yapılırken önemlidir. Topolojik Sıralama veya yürütme sırasını bulmak için. Yönlendirilmiş Döngüsüz Grafik (DAG), zamanlama sistemleri oluşturmak veya kaynakların bağımlılığını taramak vb. için de önemlidir. Ancak yukarıdaki Grafik içinde herhangi bir döngü bulunmamaktadır. İşte basit bir Yönlendirilmiş Döngüsüz Grafik (DAG) örneği:
Döngü Grafiği
Döngü grafiği, döngüsel grafikle aynı şey değildir. Döngü grafiğinde, her düğümün tam olarak iki kenarı bağlıdır, yani her düğümün tam olarak iki derecesi vardır. İşte bir döngü grafiği örneği:
İki Parçalı Grafik
Bu tür Grafikler İki parçalı grafikler, köşelerin iki kümeye atandığı özel grafik türleridir. İki parçalı bir grafik şu kurala uymalıdır:
- Köşe noktalarının iki kümesi birbirinden farklı olmalıdır; yani tüm köşe noktaları iki gruba veya kümeye ayrılmalıdır.
- Aynı kümedeki köşeler hiçbir kenar oluşturmamalıdır.
Euler Grafiği
Bir grafik veri yapısı, tüm köşelerin çift sayıda dereceye sahip olması durumunda Euler grafiği olarak kabul edilir. Köşe derecesi terimi, belirli bir köşeye giden veya o köşeden çıkan kenarların sayısını ifade eder. İşte bir Euler grafiği örneği:
Tüm köşelerin dereceleri çifttir. A, D, E ve H köşelerinin dereceleri ikidir. Burada C düğümünün derecesi dörttür, bu da çifttir.
Hamilton Grafiği
Hamilton grafı, belirli bir düğümden başlayarak aynı düğümü tekrar ziyaret etmeden veya aynı kenarı kullanmadan tüm düğümleri ziyaret edebileceğiniz bağlantılı bir grafiktir. Bu tür bağlantılı grafiklere "Hamilton grafı" denir. Verilen grafın Hamilton grafı olup olmadığını doğrulamak için ziyaret ettiğiniz yola Hamilton yolu denir. İşte basit bir Hamilton grafı örneği:
Bu görüntüde, yukarıdaki Grafikteki herhangi bir düğümün tüm köşelerini ziyaret edebiliriz. Yollardan biri olabilir ADCHBEAyrıca bir Hamilton döngüsü bulmak da mümkündür. Bir Hamilton döngüsü aynı tepe noktasında başlar ve biter. Dolayısıyla, Hamilton döngüsü şu şekilde olacaktır: ADCHBA.
