Haziran 1006

Bipartite Graph

Bipartite graph veya bigraph olarak bilinen bu graf, kendi aralarında bağımsız (bağlantı olmayan) sadece karşısındaki kümedeki düğümlerle bağlantısı olan 2 düğüm kümesinden oluşur. Graflar genelde karşımıza bu şekilde çıkmazlar. Daha karmaşıklardır. Onları bu hale getirmek uğraştırır. Bir grafın bipartite olup olmadığını öğrenmek için başka bir yöntem vardır: Kendimize bir kök (başlangıç) noktası seçeriz ve bu düğümü Mavi boyarız. Bu düğümden çıkan her kenarında sonunda yer alan düğümleri Kırmızı boyarız. Kırmızı düğümlerden ıkan her kenarın sonundaki düğümü de Mavi boyarız. Tüm renklendirme işlemi bittiğinde her kenarın her iki tarafındaki düğümlerin renkleri farklı ise graf Bipartite graph özelliğini taşır. Ancak bir tane bile uçları aynı renkte kenar olması durumunda graf bipartite değildir. En çok kullanıldığı alan eşleme problemleridir (Matching Problems). Aynı zamanda şifreli şekilde gelen verilerin çözülmesinde de kullanılabilir. Tags: , , , | Categories: Algoritma