İki parçalı graf
Vikipedi, özgür ansiklopedi
| Makale serilerinden |
| Ağ bilimi |
|---|
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).[3][4]
İ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[değiştir | kaynağı değiştir]
 | Bu alt başlığın geliştirilmesi gerekiyor. |
Özellikler[değiştir | kaynağı değiştir]
| Bu alt başlığın geliştirilmesi gerekiyor. |
Tanımlama[değiştir | kaynağı değiştir]
- 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[değiştir | kaynağı değiştir]
| Bu alt başlığın geliştirilmesi gerekiyor. |
Derece[değiştir | kaynağı değiştir]
| Bu alt başlığın geliştirilmesi gerekiyor. |
Hipergraflar ve yönlü graflarla olan ilişki[değiştir | kaynağı değiştir]
| Bu alt başlığın geliştirilmesi gerekiyor. |
Algoritmalar[değiştir | kaynağı değiştir]
| Bu alt başlığın geliştirilmesi gerekiyor. |
İki parçalılık testi[değiştir | kaynağı değiştir]
| Bu alt başlığın geliştirilmesi gerekiyor. |
(Odd cycle transversal)[değiştir | kaynağı değiştir]
| Bu alt başlığın geliştirilmesi gerekiyor. |
Eşleşme[değiştir | kaynağı değiştir]
| Bu alt başlığın geliştirilmesi gerekiyor. |
Ek uygulama örnekleri[değiştir | kaynağı değiştir]
İ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]
| Bu alt başlığın geliştirilmesi gerekiyor. |
Kaynakça[değiştir | kaynağı değiştir]
- ^ 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.
- ^ 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.
- ^ a b c Asratian, Denley & Häggkvist (1998), p. 7.
- ^ 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
- ^ 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.
- ^ Asratian, Denley & Häggkvist (1998), Theorem 2.1.3, p. 8.
- ^ 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
- ^ 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.