küçükresim|İki parçalı graf örneği küçükresim|m=5 ve n=3 elemanlı parça kümelerinden oluşan tam iki parçalı graf örneği Graf teorisinde, düğümleri her kenar iki kümede de birer bitiş ucuna sahip olacak şekilde iki ayrı kümeye ayrılabilen graflara iki parçalı graf adı verilir. Daha matematiksel bir ifade ile; ve kümeleri, bir grafın renklendirilmesi olarak da düşünülebilir. Bu durumda, U kümesinin tüm elemanlarını maviye, V kümesinin tüm elemanlarını yeşile boyadığımızı düşünürsek, bu graftaki her bir kenarın(yayın, bağıntının) iki ucundaki düğümlerin farklı renklerde olacağını söyleyebiliriz (graf renklendirme problemi). İki parçalı graflar genellikle şeklinde gösterilir. U ve V düğümlerin oluşturduğu parça kümelerini gösterirken, grafta yer alan kenarlar kümesini gösterir. Eğer iki parçalı graf bağlı(connected) değilse, birden fazla iki parçaya sahip olabilir ; Bu durumda gösterimi, bir uygulamada önemli olabilecek belirli bir 'iki parçayı' göstermekte faydalı olabilir. Eğer ise, yani U ve V kümeleri eşit sayıda elemana sahip iseler, grafı, dengeli iki parçalı graf olarak adlandırılabilir. Eğer iki parçanın tek tarafından ki tüm düğümlerin si aynı ise, G grafı olarak adlandırılır. Örnekler Özellikler Tanımlama Bir graf ancak ve ancak, tek sayıda kapalı alan içermiyorsa, iki parçalıdır. Bir graf ancak ve ancak kromatik sayısı iki ve ikiden az ise, iki parçalıdır. Bir grafın ancak ve ancak graf iki parçalı ise simetriktir. König kuramı ve mükemmel graflar Derece Hipergraflar ve yönlü graflarla olan ilişki Algoritmalar İki parçalılık testi (Odd cycle transversal) Eşleşme Ek uygulama örnekleri İki parçalı çizgeler kodlama teorisinde, özellikle alınan bir kod sözcüğünün çözülmesinde kullanılır. Çarpan çizgesi ve Tanner çizgesi bunun örnekleridir. Kaynakça Kategori
arite Kategori:Çizge teorisi
arite Kategori:Çizge teorisi