Оглавление
- 1 Псевдолесье
- 1.1 Определение псевдолесья
- 1.2 История и применение
- 1.3 Структура и свойства
- 1.4 Перечисление и характеристики
- 1.5 Графики функций
- 1.6 Приложения и исследования
- 1.7 Функциональные графы и поезда
- 1.8 Двухкруглый матроид
- 1.9 Запрещенные несовершеннолетние
- 1.10 Алгоритмы
- 1.11 Случайные двудольные графы
- 1.12 Полный текст статьи:
- 2 Псевдолес – Arc.Ask3.Ru
Псевдолесье
-
Определение псевдолесья
- Неориентированный граф с не более чем одним циклом в каждой связном компоненте
- Псевдодерево – связанный псевдолесье
-
История и применение
- Псевдолесья связаны с задачами сетевого потока и линейным программированием
- Используются в алгоритмических задачах и теории функций
-
Структура и свойства
- Псевдолесье имеет не более n ребер для n вершин
- 1-деревья имеют ровно n ребер
- Направленные псевдолесья имеют не более одной внешней ступени
-
Перечисление и характеристики
- Число простых 1-деревьев с n вершинами равно
- Число максимально направленных псевдолес на n вершинах равно nn
-
Графики функций
- Направленные псевдолесья и эндофункции эквивалентны
- Функциональные графы используются в криптографии и теории вычислительных чисел
-
Приложения и исследования
- Псевдолесья моделируют динамику клеточных автоматов
- Конягин и др. добились прогресса в графической статистике
- Мартин, Одлизко и Вольфрам исследуют диаграммы перехода состояний
-
Функциональные графы и поезда
- Вершины без входящего ребра соответствуют рисунку “Райский сад”
- Вершины с замкнутым контуром соответствуют рисунку “натюрморт”
- Поезда используются для изучения тройных систем Штайнера
-
Двухкруглый матроид
- Матроид – математическая структура с независимыми множествами
- Бикруглый матроид определяется по псевдолесам
- Наименьшие зависимые множества – велосипеды
-
Запрещенные несовершеннолетние
- Псевдолесы замкнуты относительно миноров
- Теорема Робертсона-Сеймура характеризует псевдолесы через запрещенные миноры
- Любой не-псевдолес содержит бабочку или ромб
-
Алгоритмы
- Сетевой симплексный алгоритм используется для задач о потоках
- Псевдолесья используются в задачах о минимальном охватывающем псевдолесье
- Псевдодревесность графа может быть вычислена за полиномиальное время
-
Случайные двудольные графы
- Случайный двудольный граф с высокой вероятностью является псевдолесом
- Псевдолесья важны в кукушкином хешировании и параллельных алгоритмах раскраски графов