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

Теорема Фулкерсона -Чена-Ансти — результат теории графов , раздела комбинаторики . Он обеспечивает один из двух известных подходов к решению задачи реализации орграфа , т.е. дает необходимое и достаточное условие для пар целых неотрицательных чисел. $((a_{1},b_{1}),\ldots ,(a_{n},b_{n}))$ быть входящей и исходящей степени парами простого ориентированного графа ; последовательность, подчиняющаяся этим условиям, называется «диграфической». Д-р Фулкерсон (1960) получили характеристику, аналогичную классической теореме Эрдеша – Галлаи для графов, но в отличие от этого решения с экспоненциально большим количеством неравенств. В 1966 году Чен улучшил этот результат, потребовав дополнительного ограничения, согласно которому пары целых чисел должны быть отсортированы в невозрастающем лексикографическом порядке, что приводит к n неравенствам. Ансти (1982) в другом контексте отметили, что достаточно иметь $a_{1}\geq \cdots \geq a_{n}$. Бергер заново изобрел этот результат и дал прямое доказательство.

Заявление

Последовательность $((a_{1},b_{1}),\ldots ,(a_{n},b_{n}))$ пар неотрицательных целых чисел с $a_{1}\geq \cdots \geq a_{n}$ является диграфическим тогда и только тогда, когда $\sum _{i=1}^{n}a_{i}=\sum _{i=1}^{n}b_{i}$ и для такого k , что $1\leq k\leq n$:

$\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)$

Более сильные версии

Бергер доказал что достаточно рассмотреть $k$неравенство такое, что $1\leq k<n$ с $a_{k}>a_{k+1}$ и для $k=n$.

Другие обозначения

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

Обобщение

Последовательность $((a_{1},b_{1}),\ldots ,(a_{n},b_{n}))$ пар неотрицательных целых чисел с $a_{1}\geq \cdots \geq a_{n}$ является диграфическим тогда и только тогда, когда $\sum _{i=1}^{n}a_{i}=\sum _{i=1}^{n}b_{i}$ и существует последовательность $c$ такой, что пара $(c,b)$ является диграфическим и $c$ мажорирует $a$.

Характеристики подобных проблем

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

См. также

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