Bu bölümde çizgeler üzerindeki iki temel yol türü inceleniyor:
- Euler Yolu: Çizgedeki her kenardan tam olarak bir kez geçen yol.
- Hamilton Yolu: Çizgedeki her düğümü tam olarak bir kez ziyaret eden yol.
İlk bakışta birbirine benzer görünen bu iki kavram aslında tamamen farklı zorluktadır. Bir çizgenin Euler yolu içerip içermediğini belirlemek ve varsa bulmak çok verimli biçimde yapılabilir. Hamilton yolu ise NP-hard bir problemdir; bunu verimli çözen bilinen bir algoritma yoktur.
Devamı...
Bu bölümde köklü ağaçların alt ağaçları ve yolları üzerinde yapılan sorguları çözme yöntemlerini inceliyoruz. Ele alınan sorgu türleri şunlardır:
- Bir düğümün $k$. atası hangi düğümdür?
- Bir alt ağaçtaki değerlerin toplamı kaçtır?
- İki düğüm arasındaki yolda bulunan değerlerin toplamı kaçtır?
- İki düğümün en yakın ortak atası hangisidir?
Devamı...
Yönlü bir çizgede kenarlar yalnızca tek yönlü geçilir. Bu nedenle çizge bağlı olsa bile her düğümden diğerine gidileceği garanti edilemez. Daha güçlü bir bağlanırlık kavramına ihtiyaç vardır.
Bir çizge, her düğümden diğer tüm düğümlere gidilebiliyorsa güçlü bağlanılmış (strongly connected) olarak adlandırılır. Güçlü bağlanılmamış bir çizgede ise bazı düğüm çiftleri arasında tek yönlü bir ulaşım bile mümkün olmayabilir.
Güçlü bağlanılmış parçalar (strongly connected components, SCC), çizgeyi olabildiğince büyük güçlü bağlanılmış bölümlere ayırır. Bu parçalar, orijinal çizgenin derin yapısını ortaya koyan asiklik bir bileşen çizgesi (component graph) oluşturur.
Devamı...
Bu bölümde yönlü çizgelerin iki türünden bahsedeceğiz:
- Asiklik Çizgeler (Acyclic Graphs / DAG): Çizgede hiçbir döngü yoktur; yani bir düğümden kendisine geri dönen bir yol mevcut değildir.
- Varis Çizgeleri (Successor Graphs): Her düğümden çıkan yalnızca 1 kenar vardır, yani her düğümün tam olarak bir ardılı vardır.
Her iki durumda da bu özellikler sayesinde çeşitli verimli algoritmalar tasarlanabilir.
Devamı...
Kapsayan ağaç (spanning tree), bir çizgenin bütün düğümlerini bağlı olacak şekilde birleştiren, çizgenin bazı kenarlarını içeren bir ağaçtır. Ağaçlardaki gibi, kapsayan ağaçlar da bağlı ve asikliktir. Genelde, kapsayan ağaç oluşturmanın birkaç yolu vardır.
Devamı...
Bir ağaç (tree), $n$ düğüm ve $n - 1$ kenardan oluşan bağlı ve asiklik (döngüsüz) bir çizgedir. Ağaçtan herhangi bir kenarı çıkarmak onu iki parçaya böler; herhangi bir kenar eklemek ise bir döngü oluşturur. Her iki düğüm arasında tam olarak bir yol bulunur.
Devamı...
Bir çizgede iki düğüm arasındaki en kısa yolu bulmak, pek çok pratik uygulamaya sahip temel bir problemdir. Klasik bir örnek, yol uzunlukları bilinen bir ağda iki şehir arasındaki en kısa rotayı hesaplamaktır. Ağırlıksız çizgelerde yol uzunluğu kenar sayısına eşit olduğundan BFS ile çözülebilir; bu bölümde ise ağırlıklı çizgeler için geliştirilmiş algoritmalara bakacağız.
Devamı...
Bu bölümde iki temel çizge dolaşma algoritması ele alınacaktır: derinlik öncelikli arama (DFS) ve genişlik öncelikli arama (BFS). Her ikisinin de bir başlangıç noktası vardır ve başlangıç düğümünden ulaşılabilen tüm düğümleri gezerler. İki algoritma arasındaki fark, düğümleri dolaşma sırasıdır.
Devamı...
Çoğu kodlama sorusu bir çizge problemi olarak modellenip uygun bir çizge algoritmasıyla çözülebilir. Tipik bir örnek, bir ülkedeki yolları ve şehirleri temsil eden ağdır. Bazen çizge sorunun içinde gizli olduğundan fark edilmesi güçleşir. Bu bölümde çizgelerle ilgili temel kavramları ele alıp algoritmalarda çizgeleri göstermenin farklı yollarını inceleyeceğiz.
Devamı...
Bilgisayar programlarındaki tüm veriler bit olarak yani 0 ve 1 sayıları biçiminde tutulur. Bu bölüm tam sayıların bit gösterimlerini açıklayıp bit operasyonlarının kullanıldığı örneklere değinecektir. Algoritma programlamasında bit manipülasyonunu kullanmanın pek çok farklı yolu vardır.
Devamı...