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

Теорема Фулкерсона –Чена–Ансти является результатом в теории графов , разделе комбинаторики . Она обеспечивает один из двух известных подходов к решению проблемы реализации орграфа , то есть она дает необходимое и достаточное условие для пар неотрицательных целых чисел , чтобы быть парами входящей и исходящей степеней простого ориентированного графа ; последовательность, удовлетворяющая этим условиям, называется «диграфической». 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 k}$ ${\displaystyle 1\leq k<n}$ ${\displaystyle a_{k}>a_{k+1}}$ ${\displaystyle k=n}$

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

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

Обобщение

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

Характеристики для схожих проблем

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

Смотрите также

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

Ссылки

1. DR Fulkerson: Матрицы нуль-единица с нулевым следом. В: Pacific J. Math. № 12, 1960, стр. 831–836
2. Вай-Кай Чен: О реализации ( p , s )-орграфа с заданными степенями. В: Журнал Института Франклина № 6, 1966, стр. 406–422
3. Ричард Ансти: Свойства класса (0,1)-матриц, покрывающих заданную матрицу. В: Can. J. Math. , 1982, стр. 438–453
4. Аннабель Бергер: Заметка о характеристике диграфических последовательностей В: Дискретная математика , 2014, стр. 38–41
5. Аннабель Бергер: Связь между числом реализаций для степенных последовательностей и мажорированием В: arXiv1212.5443 , 2012