Twierdzenie Fulkersona – Chena – Anstee

Fulkersona -Chen-Anstee jest wynikiem teorii grafów , gałęzi kombinatoryki . Zapewnia jedno z dwóch znanych podejść do rozwiązania problemu realizacji digrafu , tj. podaje warunek konieczny i wystarczający dla par nieujemnych liczb całkowitych ${\ Displaystyle (( a_{1},b_{1}),\ldots ,(a_{n},b_{n}))}$ będą parami stopnia wejściowego i zewnętrznego prostego grafu skierowanego ; sekwencja spełniająca te warunki nazywana jest „digraficzną”. DR Fulkerson (1960) uzyskał charakterystykę analogiczną do klasycznego twierdzenia Erdősa-Gallai dla grafów, ale w przeciwieństwie do tego rozwiązania z wykładniczo wieloma nierównościami. W 1966 roku Chen poprawił ten wynik, żądając dodatkowego ograniczenia polegającego na tym, że pary liczb całkowitych muszą być sortowane w nierosnącym porządku leksykograficznym, co prowadzi do n nierówności. $)$ w innym że wystarczy Berger wymyślił ten wynik na nowo i podaje bezpośredni dowód.

Oświadczenie

Sekwencja $)}$${\ Displaystyle ((a_ {1}, b_ {1}), \ ldots, (a_ {n}, b_ {n}$${\ Displaystyle \ suma _ {i = 1} ^ {n} a_ {i} = \ suma _ {i = 1} ^ {n} b_ {i}} i zachodzi następująca nierówność dla k$ nieujemnych par liczb całkowitych z $n$ i taka , że ${\ Displaystyle 1 \ równoważnik k \ równoważnik n}$ :

${\ Displaystyle \ suma _ {i = 1} ^ { k}a_{i}\leq \sum _{i=1}^{k}\min(b_{i},k-1)+\sum _{i=k+1}^{n}\min( b_{i},k)}$

Mocniejsze wersje

$_ {k + 1}}$$\$ rozważyć , że $k$ i dla ${\ displaystyle k = n}$ .

Inne zapisy

Twierdzenie można również wyrazić za pomocą macierzy zero-jedynkowych . Połączenie można zobaczyć, jeśli zdamy sobie sprawę, że każdy wykres skierowany ma macierz sąsiedztwa , w której sumy kolumn i sumy wierszy odpowiadają $\ Displaystyle (a_ {1}, \ ldots, a_ {n$ i ${\ Displaystyle (b_ {1}, \ ldots, b_ {n})}$ . Zauważ, że przekątna macierzy zawiera tylko zera. Istnieje związek z majoryzacją relacji . Definiujemy sekwencję $\ Displaystyle (a_ {1} ^ {*}, \ ldots, a_ {n} ^ {*})}$${\ Displaystyle a_ {k} ^ {*}: = |\ {b_ {i} | i> k, b_ {i} \ geq k \} | + | \ {b_ {i} | i \ równoważnik k, b_ {i}\geq k-1\}|}$ k . Sekwencja $\ Displaystyle (a_ {1} ^ {*}, \ ldots, a_ {n} ^ {*})}$ może być również określona przez poprawiony diagram Ferrera. Rozważ sekwencje ${\ Displaystyle (a_ {1}, \ ldots, a_ {n})}$ ( $\ Displaystyle (b_ {1}, \ ldots b_ {n})}$ i ${\ Displaystyle (a_ {1} ^ {*}, \ ldots, a_ {n} ^ {*})}$ jak ${\ Displaystyle n}$ -wymiarowe wektory ${\ displaystyle a}$ , ${\ displaystyle b}$ i ${\ displaystyle a ^ {*}}$ . Ponieważ $\ Displaystyle \ suma _ {i = 1} ^{k}a_{i}^{*}=\suma _{i=1}^{k}\min(b_{i},k-1)+\suma _{i=k+1}^{ n} \ min (b_ {i}, k)}$ stosując zasadę podwójnego liczenia , powyższe twierdzenie stwierdza, że ​​para nieujemnych ciągów liczb całkowitych ${\ Displaystyle (a, b)}$ z nierosnącymi ${ \ displaystyle a}$ jest digraficzny wtedy i tylko wtedy, gdy wektor $jest$ niż $\ displaystyle a}$ {

Uogólnienie

Sekwencja $)}$${\ Displaystyle ((a_ {1}, b_ {1}), \ ldots, (a_ {n}, b_ {n}$${\ Displaystyle \ suma _ {i = 1} ^ {n} a_ {i} = \ suma _ {i = 1} ^ {n} b_ {i}} i istnieje sekwencja do$ nieujemnych par liczb całkowitych z $n$ i { $Displaystyle c}$$}$$,$$a$ para jest digraficzna i jest \

Charakterystyki dla podobnych problemów

Podobne twierdzenia opisują ciągi stopni prostych grafów, prostych grafów skierowanych z pętlami i prostych grafów dwudzielnych. Pierwszy problem charakteryzuje twierdzenie Erdősa-Gallai . Te dwa ostatnie przypadki, które są równoważne, patrz Berger, charakteryzują się twierdzeniem Gale-Rysera .

Zobacz też

• Algorytmy Kleitmana-Wanga