Псевдолесье
-
Определение псевдолесья
- Неориентированный граф с не более чем одним циклом в каждой связном компоненте
- Псевдодерево — связанный псевдолесье
-
История и применение
- Псевдолесья связаны с задачами сетевого потока и линейным программированием
- Используются в алгоритмических задачах и теории функций
-
Структура и свойства
- Псевдолесье имеет не более n ребер для n вершин
- 1-деревья имеют ровно n ребер
- Направленные псевдолесья имеют не более одной внешней ступени
-
Перечисление и характеристики
- Число простых 1-деревьев с n вершинами равно
- Число максимально направленных псевдолес на n вершинах равно nn
-
Графики функций
- Направленные псевдолесья и эндофункции эквивалентны
- Функциональные графы используются в криптографии и теории вычислительных чисел
-
Приложения и исследования
- Псевдолесья моделируют динамику клеточных автоматов
- Конягин и др. добились прогресса в графической статистике
- Мартин, Одлизко и Вольфрам исследуют диаграммы перехода состояний
-
Функциональные графы и поезда
- Вершины без входящего ребра соответствуют рисунку «Райский сад»
- Вершины с замкнутым контуром соответствуют рисунку «натюрморт»
- Поезда используются для изучения тройных систем Штайнера
-
Двухкруглый матроид
- Матроид — математическая структура с независимыми множествами
- Бикруглый матроид определяется по псевдолесам
- Наименьшие зависимые множества — велосипеды
-
Запрещенные несовершеннолетние
- Псевдолесы замкнуты относительно миноров
- Теорема Робертсона-Сеймура характеризует псевдолесы через запрещенные миноры
- Любой не-псевдолес содержит бабочку или ромб
-
Алгоритмы
- Сетевой симплексный алгоритм используется для задач о потоках
- Псевдолесья используются в задачах о минимальном охватывающем псевдолесье
- Псевдодревесность графа может быть вычислена за полиномиальное время
-
Случайные двудольные графы
- Случайный двудольный граф с высокой вероятностью является псевдолесом
- Псевдолесья важны в кукушкином хешировании и параллельных алгоритмах раскраски графов