Teorema de Fulkerson-Chen-Anstee - Fulkerson–Chen–Anstee theorem

O teorema de Fulkerson-Chen-Anstee é um resultado da teoria dos grafos , um ramo da combinatória . Ele fornece uma de duas abordagens conhecidas resolvendo o problema d�rafo realização , ou seja, que dá uma condição necessária e suficiente para pares de não negativos inteiros para ser o indegree - outdegree pares de uma simples dirigido gráfico ; uma seqüência que obedece a essas condições é chamada de "digital". DR Fulkerson (1960) obteve uma caracterização análoga ao teorema clássico de Erdős-Gallai${\ displaystyle ((a_ {1}, b_ {1}), \ ldots, (a_ {n}, b_ {n}))}$para gráficos, mas em contraste com esta solução com muitas desigualdades exponencialmente. Em 1966, Chen melhorou esse resultado ao exigir a restrição adicional de que os pares inteiros devem ser classificados em ordem lexicográfica não crescente, levando a n desigualdades. Anstee (1982) observou em um contexto diferente que é suficiente ter . Berger reinventou esse resultado e dá uma prova direta. ${\ displaystyle a_ {1} \ geq \ cdots \ geq a_ {n}}$

Demonstração

Uma sequência de pares inteiros não negativos com é digital se, e somente se, e a seguinte desigualdade é válida para k, de modo que : ${\ displaystyle ((a_ {1}, b_ {1}), \ ldots, (a_ {n}, b_ {n}))}$${\ displaystyle a_ {1} \ geq \ cdots \ geq a_ {n}}$${\ displaystyle \ sum _ {i = 1} ^ {n} a_ {i} = \ sum _ {i = 1} ^ {n} b_ {i}}$${\ displaystyle 1 \ leq k \ leq n}$

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

Versões mais fortes

Berger provou que basta considerar a desigualdade com e para . ${\ displaystyle k}$${\ displaystyle 1 \ leq k <n}$${\ displaystyle a_ {k}> a_ {k + 1}}$${\ displaystyle k = n}$

Outras notações

O teorema também pode ser expresso em termos de matrizes zero-um . A conexão pode ser vista se percebermos que cada grafo direcionado possui uma matriz de adjacência onde as somas das colunas e das linhas correspondem a e . Observe que a diagonal da matriz contém apenas zeros. Há uma conexão com a majorização da relação . Definimos uma sequência com . A sequência também pode ser determinada por um diagrama de Ferrers corrigido . Considere sequências , e como vectores de dimensão , e . Visto que, ao aplicar o princípio da contagem dupla , o teorema acima afirma que um par de sequências inteiras não negativas com não - crescente é digital se e somente se o vetor se torna maior . ${\ displaystyle (a_ {1}, \ ldots, a_ {n})}$${\ displaystyle (b_ {1}, \ ldots, b_ {n})}$${\ displaystyle (a_ {1} ^ {*}, \ ldots, a_ {n} ^ {*})}$${\ displaystyle a_ {k} ^ {*}: = | \ {b_ {i} | i> k, b_ {i} \ geq k \} | + | \ {b_ {i} | i \ leq k, b_ {i} \ geq k-1 \} |}$${\ displaystyle (a_ {1} ^ {*}, \ ldots, a_ {n} ^ {*})}$${\ displaystyle (a_ {1}, \ ldots, a_ {n})}$${\ displaystyle (b_ {1}, \ ldots, b_ {n})}$${\ displaystyle (a_ {1} ^ {*}, \ ldots, a_ {n} ^ {*})}$${\ displaystyle n}$${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle a ^ {*}}$${\ displaystyle \ sum _ {i = 1} ^ {k} a_ {i} ^ {*} = \ sum _ {i = 1} ^ {k} \ min (b_ {i}, k-1) + \ soma _ {i = k + 1} ^ {n} \ min (b_ {i}, k)}$${\ displaystyle (a, b)}$${\ displaystyle a}$${\ displaystyle a ^ {*}}$${\ displaystyle a}$

Generalização

Uma sequência de pares de inteiros não negativos com é digital se e somente se e existe uma sequência tal que o par é digital e se torna maior . ${\ displaystyle ((a_ {1}, b_ {1}), \ ldots, (a_ {n}, b_ {n}))}$${\ displaystyle a_ {1} \ geq \ cdots \ geq a_ {n}}$${\ displaystyle \ sum _ {i = 1} ^ {n} a_ {i} = \ sum _ {i = 1} ^ {n} b_ {i}}$${\ displaystyle c}$${\ displaystyle (c, b)}$${\ displaystyle c}$${\ displaystyle a}$

Caracterizações para problemas semelhantes

Teoremas semelhantes descrevem as sequências de graus de gráficos simples, gráficos direcionados simples com loops e gráficos bipartidos simples. O primeiro problema é caracterizado pelo teorema Erdős – Gallai . Os dois últimos casos, que são equivalentes, ver Berger, são caracterizados pelo teorema de Gale-Ryser .

Veja também

• Algoritmos de Kleitman-Wang

Referências