Псевдолес - Pseudoforest

1-лес (максимальный псевдолес), образованный тремя 1-деревьями

В теории графов , A pseudoforest представляет собой неориентированный граф , в котором каждая компонента связности имеет не более одного цикла . То есть это система вершин и ребер, соединяющих пары вершин, такая, что никакие два цикла последовательных ребер не имеют общих вершин друг с другом, и никакие два цикла не могут быть соединены друг с другом путем из последовательных ребер. Pseudotree является связным pseudoforest.

Названия оправданы по аналогии с более широко изучаемыми деревьями и лесами . (Дерево - это связный граф без циклов; лес - это непересекающееся объединение деревьев.) Габоу и Тарджан приписывают изучение псевдолеса книге Данцига 1963 года по линейному программированию , в которой псевдолеса возникают при решении некоторых задач сетевого потока . Псевдолеса также образуют теоретико-графические модели функций и встречаются в нескольких алгоритмических задачах. Псевдолеса - это разреженные графы - их количество ребер линейно ограничено в терминах их вершин (на самом деле, у них не более того же количества ребер, что и вершин), а их структура матроидов позволяет разложить несколько других семейств разреженных графов как союзы лесов и псевдолесов. Название « псевдолесье» пришло от Picard & Queyranne (1982) .

Определения и структура

Мы определяем неориентированный граф как набор вершин и ребер , у каждого ребра есть две вершины (которые могут совпадать) в качестве конечных точек. То есть мы допускаем несколько ребер (ребра с одной и той же парой конечных точек) и петель (ребра, две конечные точки которых являются одной и той же вершиной). Подграф графа называется граф , образованный с помощью любых подмножеств его вершин и ребер таким образом, чтобы каждое ребро в краевом подмножестве имеет оба конца в вершине подмножестве. Компонента связности неориентированного графа подграф , состоящий из вершин и ребер , которые могут быть достигнуты следующими ребра из одной заданной исходной вершины. Граф является связным, если каждая вершина или ребро достижимы из любой другой вершины или ребра. Цикл в неориентированном графе является связным подграфом , в котором каждая вершина падает ровно два ребер или является петлей.

21 унициклический граф с не более чем шестью вершинами

Псевдолес - это неориентированный граф, в котором каждый компонент связности содержит не более одного цикла. Эквивалентно, это неориентированный граф, в котором каждая связная компонента имеет не больше ребер, чем вершин. Компоненты, у которых нет циклов, являются просто деревьями , а компоненты, в которых есть один цикл, называются 1-деревьями или унициклическими графами . То есть 1-дерево - это связный граф, содержащий ровно один цикл. Псевдолесье с одним компонентом связности (обычно называемым псевдодеревом , хотя некоторые авторы определяют псевдодерево как 1-дерево) является либо деревом, либо 1-деревом; в общем, у псевдолеса может быть несколько связанных компонентов, если все они являются деревьями или 1-деревьями.

Если удалить из 1-дерева одно из ребер в его цикле, в результате получится дерево. Если обратить этот процесс вспять, если дерево дополнить, соединив любые две его вершины новым ребром, результатом будет 1-дерево; путь в дереве, соединяющий две конечные точки добавленного ребра, вместе с самим добавленным ребром образуют уникальный цикл 1-дерева. Если увеличить 1-дерево, добавив ребро, которое соединяет одну из его вершин с вновь добавленной вершиной, результатом снова будет 1-дерево с еще одной вершиной; альтернативный метод построения 1-деревьев состоит в том, чтобы начать с одного цикла, а затем повторить эту операцию увеличения любое количество раз. Ребра любого 1-дерева можно уникальным образом разделить на два подграфа, один из которых является циклом, а другой - лесом, так что каждое дерево леса содержит ровно одну вершину цикла.

Также были изучены некоторые более специфические типы псевдолесов.

1-лес , который иногда называют максимальным pseudoforest , является pseudoforest , к которому не больше края не могут быть добавлены , не вызывая какой - то компонент графа , чтобы содержать несколько циклов. Если псевдолесье содержит дерево в качестве одного из своих компонентов, это не может быть 1-лесом, поскольку можно добавить либо ребро, соединяющее две вершины в этом дереве, образуя единый цикл, либо ребро, соединяющее это дерево с каким-либо другим компонентом. Таким образом, 1-леса - это именно те псевдолеса, в которых каждый компонент является 1-деревом.

В затягивающем pseudoforests неориентированного графа G являются pseudoforest подграфами из G , которые имеют все вершины G . Такой псевдолесье может не иметь ребер, поскольку, например, подграф, который имеет все вершины G и не имеет ребер, является псевдолесом (компонентами которого являются деревья, состоящие из одной вершины).

В максимальном pseudoforests из G являются pseudoforest подграфов G , которые не содержится в любой большую pseudoforest из G . Максимальный псевдолес в G всегда является покрывающим псевдолесом, но не наоборот. Если G не имеет компонентов связности, которые являются деревьями, то его максимальные псевдолеса являются 1-лесами, но если G действительно имеет компонент дерева, его максимальные псевдолеса не являются 1-лесами. Заявлено точно, в любом графе G его максимальные pseudoforests состоят из каждого компонента дерева G , вместе с одним или более непересекающихся 1-деревьев , покрывающих остальные вершины G .

Направленные псевдолеса

Варианты этих определений также используются для ориентированных графов . Подобно неориентированному графу, ориентированный граф состоит из вершин и ребер, но каждое ребро направлено от одной из своих конечных точек к другой конечной точке. Направлено pseudoforest представляет собой ориентированный граф , в котором каждая вершина имеет не более одного исходящего края; то есть имеет исходящую степень не более единицы. Направлено 1-лес - наиболее часто называемый функциональный граф (см ниже ), иногда максимальное направлено pseudoforest - это ориентированный граф , в котором каждая вершина имеет ровно один полустепень. Если D является направленным псевдолесом, неориентированный граф, образованный удалением направления от каждого края D, является неориентированным псевдолесом.

Количество ребер

У каждого псевдолеса на множестве из n вершин не более n ребер, и у каждого максимального псевдолеса на множестве из n вершин ровно n ребер. С другой стороны , если граф G обладает свойством , что для любого подмножества ˙s его вершин, число ребер в индуцированном подграфе из S самых большего числа вершин в S , то G является pseudoforest. 1-деревья можно определить как связные графы с одинаковым количеством вершин и ребер.

Переходя от отдельных графов к семействам графов, если семейство графов обладает тем свойством, что каждый подграф графа в семействе также входит в семейство, и каждый граф в семействе имеет не более чем столько же ребер, сколько вершин, то семейство содержит только псевдолеса. Например, каждый подграф трека (граф, нарисованный так, что каждая пара ребер имеет одну точку пересечения) также является треском, поэтому гипотеза Конвея о том, что у каждого трека не больше, чем вершин, может быть переформулирована как утверждение, что каждая пара ребер имеет одну точку пересечения. Thrackle - это псевдолесь. Более точная характеристика состоит в том, что если гипотеза верна, то треки - это в точности псевдолеса без четырехвершинного цикла и не более одного нечетного цикла.

Стрейну и Теран обобщают условия разреженности, определяющие псевдолеса: они определяют граф как ( k , l )-разреженный, если каждый непустой подграф с n вершинами имеет не более kn  -  l ребер, и ( k , l ) -жатый, если он ( k , l ) -редкими и имеет ровно kn  -  l ребер. Таким образом, псевдолеса - это (1,0) -разреженные графы, а максимальные псевдолеса - это (1,0) -уплотненные графы. Несколько других важных семейств графов могут быть определены из других значений k и l , и, когда l  ≤  k, ( k , l )-разреженные графы могут быть охарактеризованы как графы, образованные как непересекающееся по ребрам объединение l лесов и k  -  л. псевдолеса.

Почти каждый достаточно разреженный случайный граф является псевдолесным. То есть, если c - константа с 0 < c <1/2, а P _c ( n ) - вероятность того, что равномерно случайный выбор среди n -вершинных графов с cn ребрами приведет к псевдолесу, то P _c ( n ) стремится к единице в пределе при больших n . Однако при c > 1/2 почти каждый случайный граф с cn ребрами имеет большую компоненту, которая не является унициклической.

Перечисление

Граф является простым, если в нем нет петель и нескольких ребер с одинаковыми конечными точками. Количество простых 1-деревьев с n помеченными вершинами равно

${\ displaystyle n \ sum _ {k = 1} ^ {n} {\ frac {(-1) ^ {k-1}} {k}} \ sum _ {n_ {1} + \ cdots + n_ {k } = n} {\ frac {n!} {n_ {1}! \ cdots n_ {k}!}} {\ binom {{\ binom {n_ {1}} {2}} + \ cdots + {\ binom {n_ {k}} {2}}} {n}}.}$

Значения n до 300 можно найти в последовательности OEIS :  A057500 в Он-лайн энциклопедии целочисленных последовательностей .

Количество максимальных направленных псевдолесов на n вершинах, позволяющих зацикливаться, равно n ⁿ , потому что для каждой вершины существует n возможных конечных точек для исходящего ребра. Андре Джойал использовал этот факт , чтобы обеспечить взаимно однозначное доказательство по формуле Кэли , что число неориентированных деревьев на п узлов п ^{п  - 2} , найдя взаимно однозначное соответствие между максимальными и направлены pseudoforests неориентированных деревьев с двумя отмеченными узлами. Если петли не разрешены, количество максимальных направленных псевдолесов будет равно ( n  - 1) ⁿ .

Графики функций

Функция из набора {0,1,2,3,4,5,6,7,8} к себе и соответствующий функциональный граф

Направленные псевдолеса и эндофункции в некотором смысле математически эквивалентны. Любая функция ƒ из множества X к себе (то есть, эндоморфизм из X ) можно интерпретировать как определяющий направленный pseudoforest , который имеет ребро из х в у всякий раз , когда ƒ ( х ) = у . Получающийся в результате направленный псевдолесье максимален и может включать петли, когда для некоторого значения x ( x ) = x . В качестве альтернативы, если исключить самостоятельные петли, получится немаксимальный псевдолес. В другом направлении любой максимальный направленный псевдолес определяет функцию ƒ такую, что ƒ ( x ) является целью края, выходящего из x , и любой немаксимальный направленный псевдолес можно сделать максимальным, добавив петли и затем преобразовав в функцию таким же образом. По этой причине максимальные направленные псевдолеса иногда называют функциональными графами . Просмотр функции как функционального графа обеспечивает удобный язык для описания свойств, которые не так легко описать с теоретико-функциональной точки зрения; этот метод особенно применим к задачам, включающим повторяющиеся функции , которые соответствуют путям в функциональных графах.

Обнаружение цикла , задача прохождения пути в функциональном графе для поиска цикла в нем, имеет приложения в криптографии и вычислительной теории чисел , как часть алгоритма ро Полларда для целочисленной факторизации и как метод поиска коллизий в криптографических хэш-функциях . В этих приложениях ожидается, что ƒ будет вести себя случайным образом; Флажолет и Одлыжко изучают теоретико-графические свойства функциональных графов, возникающих из случайно выбранных отображений. В частности, форма парадокса дня рождения подразумевает, что в случайном функциональном графе с n вершинами путь, начинающийся из случайно выбранной вершины, обычно возвращается сам по себе, образуя цикл в пределах O ( √ n ) шагов. Конягин и др. добились аналитического и вычислительного прогресса по статистике графов.

Мартин, Одлыжко и Вольфрам исследуют псевдолеса, моделирующие динамику клеточных автоматов . Эти функциональные графы, которые они называют диаграммами переходов состояний , имеют по одной вершине для каждой возможной конфигурации, в которой может находиться ансамбль ячеек автомата, и ребро, соединяющее каждую конфигурацию с конфигурацией, которая следует за ней в соответствии с правилом автомата. Из структуры этих диаграмм можно вывести свойства автомата, такие как количество компонентов, длина предельных циклов, глубина деревьев, соединяющих неограничивающие состояния с этими циклами, или симметрии диаграммы. Например, любая вершина без входящего ребра соответствует образцу Эдемского сада, а вершина с петлей соответствует образцу натюрморта .

Еще одно раннее применение функциональных графов - поезда, используемые для изучения систем троек Штейнера . Цепочка тройной системы - это функциональный граф, имеющий вершину для каждой возможной тройки символов; каждая тройка PQR отображаются посредством ƒ к STU , где Pqs , PRT и QRU являются тройками , которые принадлежат к тройной системе и содержат пары PQ , пр и дг соответственно. Было показано, что поезда являются мощным инвариантом тройных систем, хотя их несколько сложно вычислить.

Двукруглый матроид

Матроидом представляет собой математическую структуру , в которой определенные наборы элементов определяются как независимая , таким образом, чтобы удовлетворить независимые множества свойств по образцу свойств линейной независимости в векторном пространстве . Одним из стандартных примеров матроида является графический матроид, в котором независимые множества - это множества ребер в лесах графа; Матроидная структура лесов важна в алгоритмах вычисления минимального остовного дерева графа. Аналогичным образом мы можем определить матроидов по псевдолесам.

Для любого графа G = ( V , E ), мы можем определить матроид по краям G , в которой множество ребер не зависит тогда и только тогда , когда он образует pseudoforest; Этот матроидом известен как двоякокруговая матроида (или велосипед матроида ) из G . Наименьшие зависимые множества для этого матроида - это минимальные связные подграфы G, которые имеют более одного цикла, и эти подграфы иногда называют велосипедами. Существует три возможных типа велосипеда: тета-граф имеет две вершины, которые соединены тремя внутренне непересекающимися путями, граф в виде восьмерки состоит из двух циклов, разделяющих одну вершину, а граф наручников образован двумя непересекающимися циклами, соединенными путем. . Граф является псевдолесом тогда и только тогда, когда он не содержит велосипед в качестве подграфа.

Запрещенные несовершеннолетние

Граф бабочки (слева) и граф ромба (справа), запрещенные миноры для псевдолесов

Образование второстепенного псевдолеса путем сжатия одних его краев и удаления других дает еще один псевдолес. Следовательно, семейство псевдолесов замкнуто относительно миноров, и из теоремы Робертсона – Сеймура следует, что псевдолеса можно охарактеризовать в терминах конечного набора запрещенных миноров , аналогично теореме Вагнера, характеризующей плоские графы как графы, не имеющие полного графа K _5, ни полный двудольный граф K _{3,3 в} качестве миноров. Как обсуждалось выше, любой граф, не являющийся псевдолесом, содержит в качестве подграфа наручник, фигуру 8 или тета-граф; любой граф наручников или фигура 8 может быть сжат, чтобы сформировать граф бабочки (рисунок 8 с пятью вершинами), и любой граф тета может быть сжат, чтобы сформировать граф ромба (граф тета с четырьмя вершинами), так что любой не псевдолес содержит либо бабочка или алмаз в качестве второстепенного, и это единственные второстепенные минимальные графы, не относящиеся к псевдолесу. Таким образом, граф является псевдолесом тогда и только тогда, когда в нем нет бабочки или ромба в качестве второстепенных. Если запретить только ромб, но не бабочку, результирующее более крупное семейство графов будет состоять из графов кактусов и непересекающихся объединений нескольких графов кактусов.

Проще говоря, если рассматривать мультиграфы с петлями , есть только один запрещенный минор, вершина с двумя петлями.

Алгоритмы

Раннее алгоритмическое использование псевдолесов включает в себя сетевой симплекс- алгоритм и его применение к обобщенным задачам потока, моделирующим преобразование между товарами разных типов. В этих задачах в качестве входных данных используется потоковая сеть, в которой вершины моделируют каждый товар, а ребра моделируют допустимые преобразования между одним товаром и другим. Каждое ребро помечено мощностью (сколько товара может быть преобразовано в единицу времени), множителем потока (коэффициент конверсии между товарами) и стоимостью (сколько убытков или, в случае отрицательного значения, прибыли на единицу продукции). конверсия). Задача состоит в том, чтобы определить, какое количество каждого товара необходимо преобразовать через каждую границу потоковой сети, чтобы минимизировать затраты или максимизировать прибыль, соблюдая при этом ограничения мощности и не позволяя товарам любого типа накапливаться неиспользованными. Задачи этого типа можно сформулировать как линейную программу и решить с помощью симплексного алгоритма . Промежуточные решения, возникающие из этого алгоритма, а также возможное оптимальное решение, имеют особую структуру: каждое ребро входной сети либо не используется, либо используется на полную мощность, за исключением подмножества ребер, образующих охватывающий псевдолес входная сеть, для которой объемы потока могут находиться между нулем и полной пропускной способностью. В этом приложении унициклические графы также иногда называют расширенными деревьями, а максимальные псевдолеса также иногда называют расширенными лесами .

Задача минимального остовного псевдолеса включает в себя поиск остовного псевдолеса минимального веса в более крупном графе G, взвешенном по ребрам . Из-за матроидной структуры псевдолесов максимальные псевдолеса с минимальным весом могут быть найдены с помощью жадных алгоритмов, аналогичных алгоритмам для задачи минимального остовного дерева . Однако в этом случае Габоу и Тарьян нашли более эффективный подход с линейным временем.

Pseudoarboricity графа G определяется по аналогии с arboricity как минимальное количество pseudoforests , в которую ее края могут быть разделены; эквивалентно, это минимум k такой, что G является ( k , 0)-разреженным, или минимум k такой, что ребра G могут быть ориентированы для образования ориентированного графа с исходящей степенью не выше k . Из-за матроидной структуры псевдолесов псевдолесов может быть вычислен за полиномиальное время.

Случайным образом двудольный граф с п вершинами на каждой стороне его двудольности, так и с сп края выбран независимо друг от друга случайным образом из каждых из п ² возможных пар вершин, является pseudoforest с высокой вероятностью , когда с является константой строго меньше единицы. Этот факт играет ключевую роль в анализе хеширования с кукушкой , структуры данных для поиска пар ключ-значение путем просмотра одной из двух хеш-таблиц в местах, определенных ключом: можно сформировать график, «граф с кукушкой», чьи вершины соответствуют местоположениям хэш-таблицы и чьи ребра связывают два местоположения, в которых может быть найден один из ключей, и алгоритм хеширования с кукушкой успешно находит местоположения для всех своих ключей тогда и только тогда, когда граф кукушки является псевдолесом.

Pseudoforests также играют ключевую роль в параллельных алгоритмов для раскраски графов и связанных с ними проблем.

Примечания

использованная литература

внешние ссылки

• Вайсштейн, Эрик В. , «Унициклический граф» , MathWorld