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 [...]

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 [...]

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 sayısı [...]

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 [...]

Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerinin önemli konularından olan algoritma analizi sırasında sıkça bahsi geçen bir algoritmadır. Algoritmanın ana amacı belirli bir graf üzerinde bir başlangıçtan(source) bir bitiş düğümüne (sink, end, target)  en kısa yoldan (shortest path) ulaşmaktır. Bu özelliğinden dolayı, maksimum akış (maximum flow) problemleri olarak bilinen, ve örneğin bir dağıtım şebekesinde bir [...]

Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerinde çeşitli amaçlar için kullanılan eşleştirme problemlerinin genel ismidir. Genellikle bir arz ile bir talebin eşleştirilmesi şeklinde olur. Örneğin bilgisayarın kaynaklarının, bu kaynakları talep eden işlemler ile eşleştirilmesi gibi. Ya da gerçek hayattan bir çalışanın uygun iş ile eşleştirilmesi veya evlilik problemleri veya iş akış diyagramları (işin doğru kaynak [...]

Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerinde özellikle birbiri ile eş zamanda çalışan işlerin (concurrent jobs) modellenmesi ve çözülmesinde kullanılan özel grafiklerdir. Bu graflara Yer / Geçiş Ağları (Place / Transition Networks veya P/T Nets) ismi de verilir. İçerik 1. Örnek Petri Ağları 2. Dairesel Petri Ağları 3. Paralel Petri Ağları 4. Koşullu Petri Ağları [...]

Yazan : Şadi Evren ŞEKER İçerik 1. İki parçalı graflara örnekler 2. İki parçalı grafın test edilmesi 3. İki parçalı grafların kullanım alanları 4. İki parçalı grafların özellikleri Bilgisayar bilimlerinde veri modellemede sıkça kullanılan grafların (graph) özel bir durumudur. Buna göre bir graf’ı oluşturan düğümleri iki farklı kümeye ayırabiliyorsak ve bu iki kümenin elemanlarından küme [...]

Yazan : Şadi Evren ŞEKER Bilgisayar mühendisliğinde, yapay zeka konusunda kullanılan bir karar ağacı türüdür. Aslında minimax ağaçları bilgisayar bilimlerine işletme bilimindeki oyun teorisinden (game theory) girmiştir. Temel olarak sıfır toplamlı bir oyunda (zero sum game), yani birisinin kaybının başka birisinin kazancı olduğu (veya tam tersi) oyunlarda karar vermek için kullanılışlıdırlar. Örneğin çoğu masa oyunu [...]

Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerinde özlelikle graf teorisinde (graph theory) kullanılan ve bir döngüyü (cycle) algılamaya yarayan algoritmadır. (cycle detection). Basitçe tavşan ve kaplumbağa algoritmasından (hare and tortoise algoritm) esinlenmiştir. Floyd algoritması olarak da isimlendirilen tavşan ve kaplumbağa algoritmasından farklı olarak tavşan, kaplumbağanın iki misli değil 2 üzeri adımla hareket etmektedir. Yani kaplumbağa, [...]

Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerinde veriyi modellemek için kullanılan graflarda bir döngü (cycle) olup olmadığını algılamaya yaramak için kullanılan algoritmadır. Floyd Döngü Yakalama Algoritması (Floyd’s Cycle Detection Algorithm) olarak da geçen bu algoritmaya göre bir yol üzerinde hareket eden iki farklı hızdaki gösterici (pointer) aynı değeri gösterebiliyorsa burada bir döngü bulunuyor demektir. Tosbağa [...]

Yazan : Şadi Evren ŞEKER Graf teorisinde (graph theory) bir ağacın içerisinden bir kısmınkesilmesine dayalı işlemdir. Bir ağaç (tree) yada bir graf( graph) kesildiğinde tek bir kesilme ile iki parçaya ayrıldığı kabul edilir. Bir kesitin boyutu kestiği kenar (edge) sayısı kadardır. Örneğin aşağıdaki kesitin boyutu 3′dür. grafın ağırlıklı olması durumunda (weighted graph), kesitin boyutu, kestiği [...]

Yazan : Şadi Evren ŞEKER Bir grafikteki her düğümün (node) komşularının listesine verilen isimdir. Örneğin aşağıdaki listeyi ele alalım: Bu grafikte hangi düğümün hangi düğümlerle komşu olduğunu tutan birer liste çıkarılması mümkündür. Örneğin A düğümünün komşuluk listesi (adjacency list) {B,C,D} olurken D düğümünün komşuluk listesi : {A,C} olmaktadır. Bu durum yukarıdaki her düğüm için aşağıdaki [...]

Yazan : Şadi Evren ŞEKER İçerik 1. B-Ağacının Tanımı 2. Örnek B-Ağacı 3. B-Ağacında Arama 4. B-Ağacına Ekleme 5. B-Ağacından Silme İsminin nereden geldiği (B harfinin) tartışmalı olduğu bu ağaç yapısındaki amaç arama zamanını kısaltmaktır. Buna göre ağacın her düğümünde belirli sayıda anahtar veya kayıt tutularak arama işleminin hızlandırılması öngörülmüştür. Arama hızının artmasına karşılık silme [...]

Yazan : Şadi Evren ŞEKER Dikişli ağaçlar, ikili ağaçların özel bir halidir. Bilindiği üzere ikili ağaçların son elamanı olan yapraklarda (leaf) bulunan üyeleri sol ve sağ çocuğu olarak boş (null) değer gösterirler. Dikişli ağaçlar ise bunun aksine ağaç içerisinde kimin yerine ikame edecekse bu düğümü gösterir. Örneğin aşağıdaki ağacı ele alalım: Yukarıdaki ikili ağaçta sonda [...]

Yazan: Şadi Evren ŞEKER Klik yapısının tersi olarak düşünülebilir. Basitçe bir grafta birbiri ile doğrudan bağlantısı olmayan düğümlerin oluşturduğu alt graftır. Yukarıdaki tasvirde iki adet graf verilmiştir. Üstte bütün graf görülmekte altta ise bu grafın bir alt grafı görülmketedir. Dikkat edilirse sadece altta bulunan {A,E,F} düğümleri alındığında aşağıdaki graf elde edilir ve bu grafta bulunan [...]

Yazan : Şadi Evren ŞEKER Graf teorisinde her iki düğümü birbirine bir kenar ile bağlanmış alt graflara verilen isimdir. Örneğin aşağıdaki grafikte bir klik kırmızı çizgiler ile işaretlenmiştir. Buna göre {A,B,C,D} alt grafı bir kliktir. Sosyal bilimlerde de aynı kelime(klik) bir toplumun en alt birimine verilen isimdir. Bunun sebebi doğrudan bağlantısı olan ve komşuluğu bulunan [...]

Yazan : Şadi Evren ŞEKER Bir graf üzerindeki her düğümün “k” kadar komşusu bulunması durumuna k-düzenli graf denilir. Örneğin aşağıdaki graf 2-düzenli bir graftır çünkü her düğümün derecesi 2′dir. 209 views

Yazan: Şadi Evren ŞEKER Bir grafta bulunan bütün düğümleri diğer bütün düğümlere bağlayan birer kenar bulunuyorsa bu grafa güçlü bağlı graf adı verilir. 262 views

Yazan: Şadi Evren ŞEKER Bir graftaki bir döngünün başlangıç ve bitiş düğümleri olan düğümü dışındaki bütün düğümlerin, bu döngü içerisinde sadece bir kere geçmesi durumunda bu döngüye basit döngü adı verilir. 205 views

Yazan: Şadi Evren ŞEKER Bir graftaki bütün düğümleri diğer bütün düğümlere bağlayan bir yol bulunuyorsa bu graflara bağlı graf denilir. 266 views

Yazan: Şadi Evren ŞEKER Graf teorisinde bir düğümden başlayıp aynı düğümde biten yola döngü adı verilir Örneğin yukarıdaki grafta A düğümünden başlayarak gene bu düğümde biten {A,C,D}  döngüsü tasvir edilmiştir. 233 views

Yazan: Şadi Evren ŞEKER Bir grafikte bulunan düğüm ve kenarlardan sadece bir kısmını içeren grafa verilen isimdir. Her altgraf da bir graftır. Ayrıca grafın kendisi de altgraflarından bir tanesidir. Örneğin yukarıdaki şekilde bir graf ve bir alt grafı yanyana gösterilmiştir. 226 views

Yazan: Şadi Evren ŞEKER Bir graf üzerinde bir veya daha fazla düğümden ve kenardan geçen rotaya verilen isimdir. Örneğin aşağıdaki graf üzerinde bir yol gösterilmiştir. Yolların yazılışı ise geçtikleri düğümlerin sırasıyla yazılması ile elde edilir. Örneğin yukarıdaki yolu {A,C,D} olarak göstermek mümkündür. 255 views

Yazan : Şadi Evren ŞEKER Bir grafın kenarlarının yön belirtmesi durumunda bu grafa yönlü graf adı verilir. Bir kenar iki düğümü birleştirmektedir. Yönlü bir kenar ise bir düğümden diğer düğüme gidilebilen yönü göstermektedir. Bu kenarın gösterdiği yönün tersine doğru da hareket edilebilmesi durumunda bu ikinci bir kenar ile ifade edilir. Yukarıda A ile B düğümleri [...]