Bir önceki yazımda graflara giriş yaptık. Bu yazımda çift parçalı graflardan bahsedeceğim.

İki Parçalı Graflar (Bipartite Graphs)

Bir graf’ı oluşturan düğümleri iki farklı kümeye ayırabiliyorsak ve bu iki kümenin elemanlarından küme içerisindeki bir elemana gidilmiyorsa. Yani bütün kenarlar (edges) kümeler arasındaki elemanlar arasındaysa, bu graflara iki parçalı graf (bipartite graph) ismi verilir.

Şekil-1

G grafının noktalar kümesi matematikte V(G) olarak gösterilir. Şekil-1’deki örnekte V(G)={A,B,C,D,E}.  G grafının kenarları ise şunlardır : E(G)={{A, B}, {A, D}, {A, E}, {B, C}, {B, D}, {B, E}, {C, D}, {D, E}}. Şimdi artık G çizgesini (V(G), E(G)) ikilisi olarak gösterebiliriz.

X ve Y iki küme olsun. V(G)=X∪Y ve X∩Y=∅ şeklinde V(G)’yi iki ayrı kümede toplayabiliyorsak G grafı iki parçalı graftır deriz.

Örneğin yukarıdaki graf iki gruba ayrılmıyor ayırabilsek bile kendi içinde ilişki oluyor. Yani iki parçalı değildir.

Şekil-2

Örneğin Şekil-2’deki graf iki parçalı bir graftır çünkü görüldüğü gibi 2 ayrı kümeye ayırabildik ve küme  içerisindeki köşeler ilişkili değil ancak diğer kümedeki köşelerle ilişkilidir.