Теорема Фулкерсона–Чена–Ансти

Теорема Фулкерсона –Чена–Ансти является результатом в теории графов , разделе комбинаторики . Она обеспечивает один из двух известных подходов к решению проблемы реализации орграфа , то есть она дает необходимое и достаточное условие для пар неотрицательных целых чисел , чтобы быть парами входящей и исходящей степеней простого ориентированного графа ; последовательность, удовлетворяющая этим условиям, называется «диграфической». DR Fulkerson ^[1] (1960) получил характеристику, аналогичную классической теореме Эрдёша–Галлаи для графов, но в отличие от этого решения с экспоненциально большим количеством неравенств. В 1966 году Чен ^[2] улучшил этот результат, потребовав дополнительного ограничения, что целочисленные пары должны быть отсортированы в невозрастающем лексикографическом порядке, что приводит к n неравенствам. Anstee ^[3] (1982) заметил в другом контексте, что достаточно иметь . Berger ^[4] переосмыслил этот результат и дал прямое доказательство.${\displaystyle ((a_{1},b_{1}),\ldots ,(a_{n},b_{n}))}$${\displaystyle a_{1}\geq \cdots \geq a_{n}}$

Последовательность неотрицательных целых пар с является диграфической тогда и только тогда, когда и выполняется следующее неравенство для k, такого что :${\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)}$

Бергер доказал ^[4] , что достаточно рассмотреть -е неравенство такое, что при и для .${\displaystyle к}$${\displaystyle 1\leq k<n}$${\displaystyle а_{к}>а_{к+1}}$${\displaystyle к=н}$

Теорему также можно сформулировать в терминах матриц нуль-единица . Связь можно увидеть, если понять, что каждый ориентированный граф имеет матрицу смежности , где суммы столбцов и суммы строк соответствуют и . Обратите внимание, что диагональ матрицы содержит только нули. Существует связь с отношением мажорирование . Мы определяем последовательность с помощью . Последовательность также можно определить с помощью исправленной диаграммы Феррерса. Рассмотрим последовательности , и как -мерные векторы , и . Поскольку, применяя принцип двойного счета , теорема выше утверждает, что пара неотрицательных целочисленных последовательностей с невозрастанием является диграфической тогда и только тогда, когда вектор мажорирует .${\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 а}$${\displaystyle б}$${\displaystyle а^{*}}$${\displaystyle \sum _{i=1}^{k}a_{i}^{*}=\sum _{i=1}^{k}\min(b_{i},k-1)+\sum _{i=k+1}^{n}\min(b_{i},k)}$${\displaystyle (а,б)}$${\displaystyle а}$${\displaystyle а^{*}}$${\displaystyle а}$

Последовательность неотрицательных целых пар с является диграфической тогда и только тогда, когда и существует последовательность такая, что пара является диграфической и мажорирует . ^[5]${\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 с}$${\displaystyle (c,b)}$${\displaystyle с}$${\displaystyle а}$

Аналогичные теоремы описывают последовательности степеней простых графов, простых ориентированных графов с петлями и простых двудольных графов. Первая проблема характеризуется теоремой Эрдёша–Галлаи . Последние два случая, которые эквивалентны см. Бергер, ^[4], характеризуются теоремой Гейла–Райзера .

• Алгоритмы Клейтмана–Вана