Fulkerson-Chen-Anstee teoremi - Fulkerson–Chen–Anstee theorem

Fulkerson-Chen-Anstee teoremi sonuçtur grafik teorisi bir dalı kombinatorik. Sorunu çözmek için bilinen iki yaklaşımdan birini sağlar. digraph gerçekleme problemi yani, negatif olmayan çiftler için gerekli ve yeterli bir koşul sağlar. tamsayılar olmak itiraz etmek -üstünlük çiftleri basit yönlü grafik; bu koşullara uyan bir diziye "digraphic" denir. D. R. Fulkerson [1] (1960), klasik ile benzer bir karakterizasyon elde etti. Erdős – Gallai teoremi grafikler için, ancak üssel olarak birçok eşitsizlikle bu çözümün aksine. 1966'da Chen [2] bu sonuç, tamsayı çiftlerinin n eşitsizliğe yol açacak şekilde artmayan sözlüksel sırayla sıralanması gerektiğine dair ek kısıtlama talep etti. Anstee [3] (1982), farklı bir bağlamda, sahip olmanın yeterli olduğunu gözlemlemiştir. . Berger [4] bu sonucu yeniden icat etti ve doğrudan bir kanıt veriyor.

Beyan

Bir dizi Negatif olmayan tamsayı çifti dijitaldir ancak ve ancak ve aşağıdaki eşitsizlik için geçerlidir k öyle ki :

Daha güçlü versiyonlar

Berger kanıtladı[4] düşünmenin yeterli olduğunu Eşitsizlik öyle ki ile ve için .

Diğer gösterimler

Teorem, sıfır-bir cinsinden de ifade edilebilir matrisler. Bağlantı her birinin farkına varırsa görülebilir. Yönlendirilmiş grafik var bitişik matris burada sütun toplamları ve satır toplamları karşılık gelir ve . Matrisin köşegeninin yalnızca sıfır içerdiğine dikkat edin. İlişkiye bir bağlantı var heybet. Bir dizi tanımlıyoruz ile . Sıra bir ile de belirlenebilir düzeltilmiş Ferrers diyagramı. Sıraları düşünün , ve gibi boyutlu vektörler , ve . Dan beri ilkesini uygulayarak çift ​​sayma yukarıdaki teorem, bir çift negatif olmayan tamsayı dizisinin artmayan digraphic ancak ve ancak vektör Majorizes .

Genelleme

Bir dizi Negatif olmayan tam sayı çifti dijitaldir ancak ve ancak ve bir dizi var öyle ki çift dijitaldir ve Majorizes .[5]

Benzer sorunlar için karakterizasyonlar

Benzer teoremler, basit grafiklerin derece dizilerini, döngülü basit yönlendirilmiş grafikleri ve basit iki parçalı grafikleri tanımlar. İlk problem şu şekilde karakterize edilir: Erdős – Gallai teoremi. Eşdeğer olan son iki durum, bkz.Berger,[4] ile karakterizedir Gale – Ryser teoremi.

Ayrıca bakınız

Referanslar

  1. ^ D.R. Fulkerson: Sıfır izli sıfır bir matrisler. İçinde: Pacific J. Math. No. 12, 1960, s. 831–836
  2. ^ Wai-Kai Chen: Bir (p,s) -düzenlenen derecelerle grafik. İçinde: Franklin Enstitüsü Dergisi 6, 1966, s. 406–422
  3. ^ Richard Anstee: Belirli bir matrisi kapsayan bir (0,1) -matris sınıfının özellikleri. İçinde: Yapabilmek. J. Math., 1982, s. 438–453
  4. ^ a b c Annabell Berger: Digrafik Dizilerin Karakterizasyonu Üzerine Bir Not İçinde: Ayrık Matematik, 2014, s. 38–41
  5. ^ Annabell Berger: Derece dizileri için gerçekleştirme sayısı ile majorizasyon arasındaki bağlantı İçinde: arXiv1212.5443, 2012