Graf Teorisi II

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.

graf2

Ş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.

graf3

Ş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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.