İki parçalı graf

İki parçalı graf örneği
m=5 ve n=3 elemanlı parça kümelerinden oluşan tam iki parçalı graf örneği
Makale serilerinden
Ağ bilimi
Internet_map_1024.jpg
Teori
Ağ türleri
Graflar
Özellikler
Türler
Modeller
Topoloji
Dinamikler

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;

Düğümleri U ve V şeklinde iki ayrık ve birbirinden bağımsız kümeye ayrılabilen ve her bir kenarı U kümesindeki bir düğümü V kümesindeki bir düğüme bağlayan graflara iki parçalı graf adı verilir. Burada U ve V kümeleri, genellikle parça kümeleri (partite sets) olarak ifade edilir.
Bir başka tanımla: Tek sayıda kapalı bölge (cycle) içermeyen herhangi bir graf, iki parçalı bir graf olarak adlandırılır.[1][2]

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).[3][4]  

Bunun tersi de geçerlidir. iki parçalı olmayan bir grafta, böyle bir renklendirme mümkün değildir. Üçgen şeklinde bir graf düşünürsek, muhakkak üç kenardan birisinin iki ucundaki düğümler aynı renkte olacaktır. 

İ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;[5] 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.[3] Eğer iki parçanın tek tarafından ki tüm düğümlerin derecesi aynı ise, G grafı (biregular) olarak adlandırılır.

Örnekler

Özellikler

Tanımlama

İki parçalı graflar birden fazla şekilde tanımlanabilir
  • Bir graf ancak ve ancak, tek sayıda kapalı alan içermiyorsa, iki parçalıdır.[6]
  • Bir graf ancak ve ancak kromatik sayısı iki ve ikiden az ise, iki parçalıdır.[3]
  • Bir grafın spektrumu ancak ve ancak graf iki parçalı ise simetriktir.[7]

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

Kaynakça

  1. ^ Diestel, Reinard (2005). Graph Theory, Grad. Texts in Math. Springer. ISBN 978-3-642-14278-9. 9 Nisan 2011 tarihinde kaynağından arşivlendi. Erişim tarihi: 10 Ağustos 2015. 
  2. ^ Asratian, Armen S.; Denley, Tristan M. J.; Häggkvist, Roland (1998), Bipartite Graphs and their Applications, Cambridge Tracts in Mathematics, 131, Cambridge University Press, ISBN 9780521593458 .
  3. ^ a b c Asratian, Denley & Häggkvist (1998), p. 7.
  4. ^ Scheinerman, Edward R. (2012), Mathematics: A Discrete Introduction (3.3isbn = 9780840049421 bas.), Cengage Learning, s. 363, 9 Kasım 2020 tarihinde kaynağından arşivlendi, erişim tarihi: 10 Ağustos 2015 
  5. ^ Chartrand, Gary; Zhang, Ping (2008), Chromatic Graph Theory, Discrete Mathematics And Its Applications, 53, CRC Press, s. 223, ISBN 9781584888000, 9 Kasım 2020 tarihinde kaynağından arşivlendi, erişim tarihi: 10 Ağustos 2015 .
  6. ^ Asratian, Denley & Häggkvist (1998), Theorem 2.1.3, p. 8.
  7. ^ Biggs, Norman (1994), Algebraic Graph Theory, Cambridge Mathematical Library (2.2isbn = 9780521458979 bas.), Cambridge University Press, s. 53, 18 Mart 2015 tarihinde kaynağından arşivlendi, erişim tarihi: 10 Ağustos 2015 
  8. ^ Moon, Todd K. (2005), Error Correction Coding: Mathematical Methods and Algorithms, John Wiley & Sons, ISBN 9780471648000, 8 Haziran 2019 tarihinde kaynağından arşivlendi, erişim tarihi: 18 Ocak 2022 .