Псевдолес

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

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

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

Определения и структура [ править ]

Мы определяем неориентированный граф как набор вершин и ребер , у каждого ребра есть две вершины (которые могут совпадать) в качестве конечных точек. То есть мы допускаем несколько ребер (ребра с одной и той же парой конечных точек) и петель (ребра, две конечные точки которых являются одной и той же вершиной). ^[1] подграф графа называется граф , образованный с помощью любых подмножеств его вершин и ребер таким образом, чтобы каждое ребро в краевом подмножестве имеет оба конца в вершине подмножестве. Компонента связности неориентированного графа подграф , состоящий из вершин и ребер , которые могут быть достигнуты следующими ребра из одной заданной исходной вершины. Граф является связным, если каждая вершина или ребро достижимы из любой другой вершины или ребра. Ацикл в неориентированном графе - это связный подграф, в котором каждая вершина инцидентна ровно двум ребрам, или является петлей. ^[4]

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

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

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

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

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 - это ориентированный граф , в котором каждая вершина имеет ровно один полустепень. ^[8] Если Dявляется направленным псевдолесом, неориентированный граф, образованный удалением направления от каждого края D, является неориентированным псевдолесом.

Количество ребер [ править ]

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

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

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

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

Перечисление [ править ]

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

${\ 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 неориентированных деревьев с двумя отмеченными узлами. ^[14] Если петли не разрешены, количество максимальных направленных псевдолесов будет равно ( n  - 1) ⁿ .

Графики функций [ править ]

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

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

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

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

Двукруглый матроид [ править ]

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

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

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

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

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

Алгоритмы [ править ]

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

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

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

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

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

Заметки [ править ]

Ссылки [ править ]

Внешние ссылки [ править ]

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