Sınırlı Derin Öncelikli Arama (Depth-Limited Search) Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerinde kullanılan arama algoritmalarından birisidir. Bu algoritma esas olarak derin öncelikli arama (depth first search DFS) ile aynı çalışmaktadır ancak tek farkı arama işlemi sırasında özellikle dairelere (cycles) takılma ihtimaline karşı sınır önlemi alınmış olmasıdır. Örneğin aşağıdaki şekli ele alalım: Yukarıdaki şekil […]
Category: graf teorisi (graph theory, çizge kuramı)
Arama Algoritmaları (Search Algorithms)
Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerinde, çeşitli veri yapılarının (data structures) üzerinde bir bilginin aranması sırasına kullanılan algoritmaların genel ismidir. Örneğin bir dosyada bir kelimenin aranması, bir ağaç yapısında (tree) bir düğümün (node) aranması veya bir dizi (array) üzerinde bir verinin aranması gibi durumlar bu algoritmaların çalışma alanlarına girer. Yapısal olarak arama algoritmalarını iki […]
Sabit Maliyet Araması (Uniform Cost Search)
Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerinde arama algoritmaları için kullanılan bir terimdir. Algoritma ağırlıklı graflar (weighted graphs) üzerinde çalışmaktadır. Ağaçlar da bir graf örneği olduğu için algoritmanın ağaçlar üzerinde çalışması da mümkündür. Algoritma basitçe aşağıdaki şekilde tanımlanabilir: Kök düğümden başla (root node) En düşük maliyetli komşuya git Şayet aranan düğüm bulunduysa bit, bulunmadıysa 2. […]
Prüfer Dizilimi (Prüfer Sequence)
Yazan : Şadi Evren ŞEKER Bilgisayar bilimleri de dahil olmak üzere pek çok bilim ve mühendislik alanının ortak çalışma konularından birisi olan graf teorisindeki (graph theory) bir hesaplama veya gösterim algoritmasıdır. Ağaç (tree) yapısındaki graflar için yani dairesel olmayan graflar (acyclic graphs) için kullanılabilir. Daha basit bir ifade ile şeklin (graph) yaprakları (leaf) bulunmalıdır. Prüfer […]
Kirchoff Teoremi (Kirchoff Theorem)
Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerinin de arasında bulunduğu pek çok bilim ve mühendislik alanında kullanılan graf teorisinde kullanılan bir teoremdir. Bu teorem kirchoff matrisi veya laplas matrisi (laplacian matrix) ismi verilen matrisler ile birlikte kullanıldığında bir grafta bulunan asgari tarama ağacı (minimum spanning tree) sayısını verir. Bilindiği (veya ilgili yazıdan okunabileceği) üzere laplas […]
Laplas Matrisi (Laplacian Matrix)
Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerinin de içinde bulunduğu pekçok bilim ve mühendislik alanında kullanılan graf teorisi (graph theory) açısından önemli bir matristir. Laplas matrisinin özelliği her düğümün derecesini (node order) ve diğer düğümlerle olan komşuluk ilişkisini (adjacency list) tutmasıdır. Laplas matrisine giriş matrisi (admittance matrix) veya Kirchhoff matirisi ( Kirchhoff matrix ) isimleri […]
Düğüm Derecesi (Order of Node)
Yazan : Şadi Evren ŞEKER Graf teorisinde (graph theory) bir grafın temel unsurlarından olan düğümlerin (nodes) giren veya çıkan kenar (edge) sayısını verir. Tanım olarak yönsüz graflar (undirected graphs) ve yönlü graflar (directed graphs) için iki ayrı tanım yapılabilir. Yönsüz graflarda bir düğümün derecesi Yönsüz graflarda bir düğümün derecesi, doğrudan düğüme bağlı komşu düğüm sayısına […]
Denkşekillilik (Isomorphism)
Yazan : Şadi Evren ŞEKER İki şeklin birbirinden farklı ancak denk olması durumudur. Bilgisayar bilimleri de dahil olmak üzere pek çok bilim ve mühendislik alanında kullanılan graf teorisine (graph theory) göre iki şekil birbirinden farklı çizilmiş ancak işlev ve değer olarak aynı olabilir. Tanım ve örnek Örneğin aşağıdaki iki şekli ele alalım: Yukarıda verilen graftaki […]
Öyler Yolu (Eulerian Path)
Yazan : Şadi Evren ŞEKER Bilgisayar mühendisliği de dahil olmak üzere pekçok bilim ve mühendislik alanında kullanılan graf teorisindeki özel bir yol (path) şeklidir. Bu yolun özelliği her kenardan (edge) bir kere (en az ve en çok) geçen yolu bulmaktır. İçerik Teorinin tarihi çıkışı Teorinin tanımı Öyler yollarının özellikleri Bir graftaki farklı öyler yollarının […]
Markof Modeli (Markov Model)
Yazan : Şadi Evren ŞEKER Bilgisayar bilimleri de dahil olmak üzere pekçok bilim ve mühendislik alanında kullanılan markof modelleri aslında graf teorisinin (graph theory) bir uygulamasıdır. Basitçe düğümleri (nodes) durumlardan oluşan ve bu durumlar arasında istatistiksel geçişi modelleyen kenarları (edges) bulunan graflardır. Markof modellerine (markof zinciri (markov chain) ismi de kullanılmaktadır) göre bir durum belirli […]