Graf teorisinde düğümleri her kenar iki kümede de birer bitiş ucuna sahip olacak şekilde iki ayrı kümeye ayrıla

İki parçalı graf

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.

İ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

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.

$U$ ve $V$ 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).

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 $G=(U,V,E)$ şeklinde gösterilir. U ve V düğümlerin oluşturduğu parça kümelerini gösterirken, $E$ 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 $(U,V,E)$ gösterimi, bir uygulamada önemli olabilecek belirli bir 'iki parçayı' göstermekte faydalı olabilir. Eğer $|U|=|V|$ ise, yani U ve V kümeleri eşit sayıda elemana sahip iseler, $G$ grafı, dengeli iki parçalı graf olarak adlandırılabilir. 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

Bu alt başlığın genişletilmesi gerekiyor. Sayfayı düzenleyerek yardımcı olabilirsiniz.

Özellikler

Bu alt başlığın genişletilmesi gerekiyor. Sayfayı düzenleyerek yardımcı olabilirsiniz.

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.
Bir graf ancak ve ancak kromatik sayısı iki ve ikiden az ise, iki parçalıdır.
Bir grafın spektrumu ancak ve ancak graf iki parçalı ise simetriktir.

König kuramı ve mükemmel graflar

Bu alt başlığın genişletilmesi gerekiyor. Sayfayı düzenleyerek yardımcı olabilirsiniz.

Derece

Bu alt başlığın genişletilmesi gerekiyor. Sayfayı düzenleyerek yardımcı olabilirsiniz.

Hipergraflar ve yönlü graflarla olan ilişki

Bu alt başlığın genişletilmesi gerekiyor. Sayfayı düzenleyerek yardımcı olabilirsiniz.

Algoritmalar

Bu alt başlığın genişletilmesi gerekiyor. Sayfayı düzenleyerek yardımcı olabilirsiniz.

İki parçalılık testi

Bu alt başlığın genişletilmesi gerekiyor. Sayfayı düzenleyerek yardımcı olabilirsiniz.

(Odd cycle transversal)

Bu alt başlığın genişletilmesi gerekiyor. Sayfayı düzenleyerek yardımcı olabilirsiniz.

Eşleşme

Bu alt başlığın genişletilmesi gerekiyor. Sayfayı düzenleyerek yardımcı olabilirsiniz.

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 bunun örnekleridir.

Bu alt başlığın genişletilmesi gerekiyor. Sayfayı düzenleyerek yardımcı olabilirsiniz.

Kaynakça

^ Diestel, Reinard (2005). . Springer. ISBN . 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 .
^ ^a ^b ^c Asratian, Denley & Häggkvist (1998), p. 7.
^ (2012), Mathematics: A Discrete Introduction (3.3isbn = 9780840049421 bas.), Cengage Learning, s. 363, 9 Kasım 2020 tarihinde kaynağından , 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 , 9 Kasım 2020 tarihinde kaynağından , 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 , erişim tarihi: 10 Ağustos 2015
^ Moon, Todd K. (2005), Error Correction Coding: Mathematical Methods and Algorithms, John Wiley & Sons, ISBN , 8 Haziran 2019 tarihinde kaynağından , erişim tarihi: 18 Ocak 2022 .

wikipedia, wiki, viki, vikipedia, oku, kitap, kütüphane, kütübhane, ara, ara bul, bul, herşey, ne arasanız burada,hikayeler, makale, kitaplar, öğren, wiki, bilgi, tarih, yukle, izle, telefon için, turk, türk, türkçe, turkce, nasıl yapılır, ne demek, nasıl, yapmak, yapılır, indir, ücretsiz, ücretsiz indir, bedava, bedava indir, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, resim, müzik, şarkı, film, film, oyun, oyunlar, mobil, cep telefonu, telefon, android, ios, apple, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, pc, web, computer, bilgisayar

Graf teorisinde dugumleri her kenar iki kumede de birer bitis ucuna sahip olacak sekilde iki ayri kumeye ayrilabilen graflara iki parcali graf adi verilir Iki parcali graf ornegim 5 ve n 3 elemanli parca kumelerinden olusan tam iki parcali graf ornegi Daha matematiksel bir ifade ile Dugumleri U ve V seklinde iki ayrik ve birbirinden bagimsiz kumeye ayrilabilen ve her bir kenari U kumesindeki bir dugumu V kumesindeki bir dugume baglayan graflara iki parcali graf adi verilir Burada U ve V kumeleri genellikle parca kumeleri partite sets olarak ifade edilir Bir baska tanimla Tek sayida kapali bolge cycle icermeyen herhangi bir graf iki parcali bir graf olarak adlandirilir U displaystyle U ve V displaystyle V kumeleri bir grafin renklendirilmesi olarak da dusunulebilir Bu durumda U kumesinin tum elemanlarini maviye V kumesinin tum elemanlarini yesile boyadigimizi dusunursek bu graftaki her bir kenarin yayin bagintinin iki ucundaki dugumlerin farkli renklerde olacagini soyleyebiliriz graf renklendirme problemi Bunun tersi de gecerlidir iki parcali olmayan bir grafta boyle bir renklendirme mumkun degildir Ucgen seklinde bir graf dusunursek muhakkak uc kenardan birisinin iki ucundaki dugumler ayni renkte olacaktir Iki parcali graflar genellikle G U V E displaystyle G U V E seklinde gosterilir U ve V dugumlerin olusturdugu parca kumelerini gosterirken E displaystyle E grafta yer alan kenarlar kumesini gosterir Eger iki parcali graf bagli connected degilse birden fazla iki parcaya sahip olabilir Bu durumda U V E displaystyle U V E gosterimi bir uygulamada onemli olabilecek belirli bir iki parcayi gostermekte faydali olabilir Eger U V displaystyle U V ise yani U ve V kumeleri esit sayida elemana sahip iseler G displaystyle G grafi dengeli iki parcali graf olarak adlandirilabilir Eger iki parcanin tek tarafindan ki tum dugumlerin derecesi ayni ise G grafi biregular olarak adlandirilir OrneklerBu alt basligin genisletilmesi gerekiyor Sayfayi duzenleyerek yardimci olabilirsiniz OzelliklerBu alt basligin genisletilmesi gerekiyor Sayfayi duzenleyerek yardimci olabilirsiniz Tanimlama Iki parcali graflar birden fazla sekilde tanimlanabilir Bir graf ancak ve ancak tek sayida kapali alan icermiyorsa iki parcalidir Bir graf ancak ve ancak kromatik sayisi iki ve ikiden az ise iki parcalidir Bir grafin spektrumu ancak ve ancak graf iki parcali ise simetriktir Konig kurami ve mukemmel graflar Bu alt basligin genisletilmesi gerekiyor Sayfayi duzenleyerek yardimci olabilirsiniz Derece Bu alt basligin genisletilmesi gerekiyor Sayfayi duzenleyerek yardimci olabilirsiniz Hipergraflar ve yonlu graflarla olan iliski Bu alt basligin genisletilmesi gerekiyor Sayfayi duzenleyerek yardimci olabilirsiniz AlgoritmalarBu alt basligin genisletilmesi gerekiyor Sayfayi duzenleyerek yardimci olabilirsiniz Iki parcalilik testi Bu alt basligin genisletilmesi gerekiyor Sayfayi duzenleyerek yardimci olabilirsiniz Odd cycle transversal Bu alt basligin genisletilmesi gerekiyor Sayfayi duzenleyerek yardimci olabilirsiniz Eslesme Bu alt basligin genisletilmesi gerekiyor Sayfayi duzenleyerek yardimci olabilirsiniz Ek uygulama ornekleriIki parcali cizgeler kodlama teorisinde ozellikle alinan bir kod sozcugunun cozulmesinde kullanilir Carpan cizgesi ve bunun ornekleridir Bu alt basligin genisletilmesi gerekiyor Sayfayi duzenleyerek yardimci olabilirsiniz Kaynakca Diestel Reinard 2005 Springer ISBN 978 3 642 14278 9 9 Nisan 2011 tarihinde kaynagindan arsivlendi Erisim tarihi 10 Agustos 2015 Asratian Armen S Denley Tristan M J Haggkvist Roland 1998 Bipartite Graphs and their Applications Cambridge Tracts in Mathematics 131 Cambridge University Press ISBN 9780521593458 a b c Asratian Denley amp Haggkvist 1998 p 7 2012 Mathematics A Discrete Introduction 3 3isbn 9780840049421 bas Cengage Learning s 363 9 Kasim 2020 tarihinde kaynagindan erisim tarihi 10 Agustos 2015 Chartrand Gary Zhang Ping 2008 Chromatic Graph Theory Discrete Mathematics And Its Applications 53 CRC Press s 223 ISBN 9781584888000 9 Kasim 2020 tarihinde kaynagindan erisim tarihi 10 Agustos 2015 Asratian Denley amp Haggkvist 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 kaynagindan erisim tarihi 10 Agustos 2015 Moon Todd K 2005 Error Correction Coding Mathematical Methods and Algorithms John Wiley amp Sons ISBN 9780471648000 8 Haziran 2019 tarihinde kaynagindan erisim tarihi 18 Ocak 2022

Yayın tarihi: Haziran 19, 2024, 22:41 pm