В теории графов псевдолесом называется неориентированный граф [1] , в котором каждая компонента связности имеет не более одного цикла . То есть это система вершин и ребер , соединяющая пары вершин, такая, что никакие два цикла последовательных ребер не имеют общей вершины друг с другом, и никакие два цикла не могут быть соединены друг с другом путем последовательных ребер. Псевдодерево — это связный псевдолес.
Названия обоснованы аналогией с наиболее часто изучаемыми деревьями и лесами . (Дерево — это связный граф без циклов; лес — это непересекающееся объединение деревьев.) Габоу и Тарьян [2] приписывают изучение псевдолесов книге Данцига 1963 года по линейному программированию , в которой псевдолеса возникают при решении некоторых сетевых задач. проблемы с потоком . [3] Псевдолеса также образуют модели функций на основе теории графов и встречаются в ряде алгоритмических задач. Псевдолеса представляют собой разреженные графы – их количество ребер линейно ограничено с точки зрения количества вершин (на самом деле у них не более столько же ребер, сколько и вершин) – а их матроидная структура позволяет разложить несколько других семейств разреженных графов. как союзы лесов и псевдолесов. Название «псевдолес» взято из работы Picard & Queyranne (1982).
Мы определяем неориентированный граф как набор вершин и ребер , в котором каждое ребро имеет две вершины (которые могут совпадать) в качестве конечных точек. То есть мы допускаем наличие нескольких ребер (ребер с одной и той же парой конечных точек) и петель (ребер, две конечные точки которых являются одной и той же вершиной). [1] Подграф графа — это граф, образованный любыми подмножествами его вершин и ребер, такими, что каждое ребро в подмножестве ребер имеет обе конечные точки в подмножестве вершин . Компонент связности неориентированного графа — это подграф, состоящий из вершин и ребер, до которых можно добраться, пройдя по ребрам из одной заданной начальной вершины. Граф связный, если каждая вершина или ребро достижимы из любой другой вершины или ребра. Цикл в неориентированном графе — это связный подграф , в котором каждая вершина инцидентна ровно двум ребрам, или является петлей. [4]
Псевдолес — это неориентированный граф, в котором каждая компонента связности содержит не более одного цикла. [5] Эквивалентно, это неориентированный граф, в котором каждый связный компонент имеет не больше ребер, чем вершин. [6] Компоненты, не имеющие циклов, являются просто деревьями , а компоненты, содержащие один цикл, называются 1-деревьями или унициклическими графами . То есть 1-дерево — это связный граф, содержащий ровно один цикл. Псевдолес с одним связным компонентом (обычно называемый псевдодеревом , хотя некоторые авторы определяют псевдодерево как 1-дерево) является либо деревом, либо 1-деревом; Как правило, псевдолес может иметь несколько связных компонентов, если все они являются деревьями или 1-деревьями.
Если удалить из 1-дерева одно из ребер в его цикле, результатом будет дерево. Обратив этот процесс, если кто-то дополняет дерево, соединяя любые две его вершины новым ребром, результатом будет 1-дерево; путь в дереве, соединяющий две конечные точки добавленного ребра, вместе с самим добавленным ребром образуют уникальный цикл 1-дерева. Если кто-то дополняет 1-дерево, добавляя ребро, которое соединяет одну из его вершин с вновь добавленной вершиной, результатом снова будет 1-дерево с еще одной вершиной; альтернативный метод построения 1-деревьев — начать с одного цикла, а затем повторить эту операцию увеличения любое количество раз. Ребра любого 1-дерева можно единственным образом разбить на два подграфа, один из которых является циклом, а другой - лесом, так что каждое дерево леса содержит ровно одну вершину цикла. [7]
Изучены также некоторые более конкретные типы псевдолесов.
Версии этих определений также используются для ориентированных графов . Как и неориентированный граф, ориентированный граф состоит из вершин и ребер, но каждое ребро направлено от одной из его конечных точек к другой конечной точке. Ориентированный псевдолес — это ориентированный граф, в котором каждая вершина имеет не более одного исходящего ребра; то есть имеет выходную степень не более одной. Ориентированный 1-лес , чаще всего называемый функциональным графом (см. ниже), иногда максимальным направленным псевдолесом , представляет собой ориентированный граф, в котором каждая вершина имеет исходящую степень ровно одну. [8] Если D — ориентированный псевдолес, неориентированный граф, образованный удалением направления из каждого ребра D , является неориентированным псевдолесом.
Каждый псевдолес на множестве из n вершин имеет не более n ребер, а каждый максимальный псевдолес на множестве из n вершин имеет ровно n ребер. И наоборот, если граф G обладает свойством, что для каждого подмножества S его вершин количество ребер в индуцированном подграфе S не превышает количества вершин в S , то G является псевдолесом. 1-деревья можно определить как связные графы с одинаковым количеством вершин и ребер. [2]
При переходе от отдельных графов к семействам графов, если семейство графов обладает свойством, что каждый подграф графа в семействе также входит в семейство, и каждый граф в семействе имеет не более чем столько же ребер, сколько и вершин, то семейство содержит только псевдолеса. Например, каждый подграф трекла ( граф, нарисованный так, что каждая пара ребер имеет одну точку пересечения) также является треклом, поэтому гипотезу Конвея о том, что каждый трекл имеет не более чем столько же ребер, сколько и вершин, можно переформулировать следующим образом: Тракл — это псевдолес. Более точная характеристика состоит в том, что, если гипотеза верна, то треклы - это в точности псевдолеса без четырехвершинного цикла и не более чем с одним нечетным циклом. [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 − л псевдолеса. [11]
Почти каждый достаточно разреженный случайный граф является псевдолесом. [12] То есть, если c — константа с 0 < c < 1/2, а P c ( n ) — вероятность того, что равномерный случайный выбор среди графов с n -вершинами с cn ребрами приведет к образованию псевдолеса, то P c ( n ) стремится к единице в пределе при больших n . Однако при c > 1/2 почти каждый случайный граф с cn ребрами имеет большую компоненту, не являющуюся одноциклической.
Граф является простым , если в нем нет петель и кратных ребер с одинаковыми концами. Число простых 1-деревьев с n помеченными вершинами равно [13]
Значения для n до 300 можно найти в последовательности OEIS : A057500 Электронной энциклопедии целочисленных последовательностей .
Число максимальных направленных псевдолесов на n вершинах, допускающих самоциклы, равно n n , поскольку для каждой вершины существует n возможных конечных точек исходящего ребра. Андре Жойал использовал этот факт, чтобы обеспечить взаимно однозначное доказательство формулы Кэли о том, что количество неориентированных деревьев на n узлах равно n n - 2 , путем нахождения биекции между максимальными направленными псевдолесами и неориентированными деревьями с двумя выделенными узлами. [14] Если самоциклы не разрешены, количество максимальных направленных псевдолесов вместо этого равно ( n − 1) n .
Направленные псевдолеса и эндофункции в некотором смысле математически эквивалентны. Любую функцию ƒ из множества X в себя (то есть эндоморфизм X ) можно интерпретировать как определение направленного псевдолеса, который имеет ребро от x до y всякий раз , когда ƒ( x ) = y . Результирующий направленный псевдолес является максимальным и может включать в себя циклы всякий раз, когда некоторое значение x имеет ƒ( x ) = x . В качестве альтернативы, исключение самоциклов приводит к немаксимальному псевдолесу. В другом направлении любой максимальный направленный псевдолес определяет функцию ƒ такую, что ƒ( x ) является целью ребра, исходящего из x , а любой немаксимальный направленный псевдолес можно сделать максимальным, добавив циклы и затем преобразуя в функцию таким же образом. По этой причине максимальные направленные псевдолеса иногда называют функциональными графами . [2] Представление функции в виде функционального графа обеспечивает удобный язык для описания свойств, которые не так легко описать с точки зрения теории функций; этот метод особенно применим к задачам, связанным с повторяющимися функциями , которые соответствуют путям в функциональных графах.
Обнаружение цикла , задача следования по пути в функциональном графе, чтобы найти в нем цикл, имеет приложения в криптографии и вычислительной теории чисел , как часть ро-алгоритма Полларда для факторизации целых чисел и как метод поиска коллизий в криптографических хэш-функциях . Ожидается, что в этих приложениях ƒ будет вести себя случайным образом; Флажоле и Одлизко [15] изучают теоретико-графовые свойства функциональных графов, возникающих в результате случайно выбранных отображений. В частности, форма парадокса дня рождения подразумевает, что в случайном функциональном графе с n вершинами путь, начинающийся со случайно выбранной вершины, обычно зацикливается на самом себе, образуя цикл за O( √ n ) шагов. Конягин и др. добились аналитического и вычислительного прогресса в графовой статистике. [16]
Мартин, Одлизко и Вольфрам [17] исследуют псевдолеса, моделирующие динамику клеточных автоматов . Эти функциональные графы, которые они называют диаграммами переходов состояний , имеют по одной вершине для каждой возможной конфигурации, в которой может находиться ансамбль ячеек автомата, и ребро, соединяющее каждую конфигурацию с следующей за ней конфигурацией согласно правилу автомата. Из структуры этих диаграмм можно вывести свойства автомата, такие как количество компонентов, длина предельных циклов, глубина деревьев, соединяющих непредельные состояния с этими циклами, или симметрия диаграммы. Например, любая вершина без входящего края соответствует узору «Райский сад» , а вершина с замкнутым контуром соответствует узору натюрморта .
Еще одним ранним применением функциональных графов являются поезда, используемые для изучения систем троек Штейнера . [18] Последовательность тройной системы представляет собой функциональный граф, имеющий вершину для каждой возможной тройки символов; каждая тройка pqr отображается с помощью ƒ в stu , где pqs , prt и qru — тройки, принадлежащие системе троек и содержащие пары pq , pr и qr соответственно. Было показано, что поезда являются мощным инвариантом тройных систем, хотя и несколько громоздки для вычислений.
Матроид — это математическая структура , в которой определенные наборы элементов определены как независимые таким образом, что независимые наборы удовлетворяют свойствам, смоделированным после свойств линейной независимости в векторном пространстве . Одним из стандартных примеров матроида является графический матроид, в котором независимыми множествами являются множества ребер в лесах графа; матроидная структура лесов важна в алгоритмах вычисления минимального остовного дерева графа. Аналогично мы можем определить матроидов из псевдолесов.
Для любого графа G = ( V , E ) мы можем определить матроид на ребрах G , в котором набор ребер независим тогда и только тогда, когда он образует псевдолес; этот матроид известен как бициркулярный матроид (или велосипедный матроид ) группы G. [19] [20] Наименьшими зависимыми множествами для этого матроида являются минимальные связные подграфы G , имеющие более одного цикла, и эти подграфы иногда называют велосипедами. Существует три возможных типа велосипеда: тета-граф имеет две вершины, которые соединены тремя внутренне непересекающимися путями, граф в форме восьмерки состоит из двух циклов, разделяющих одну вершину, и граф наручников состоит из двух непересекающихся циклов, соединенных путем. . [21] Граф является псевдолесом тогда и только тогда, когда он не содержит велосипед в качестве подграфа. [10]
Формирование второстепенного псевдолеса путем сжатия некоторых его краев и удаления других приводит к созданию другого псевдолеса. Следовательно, семейство псевдолесов замкнуто относительно миноров, а из теоремы Робертсона-Сеймура следует, что псевдолеса можно охарактеризовать в терминах конечного набора запрещенных миноров , аналогично теореме Вагнера , характеризующей плоские графы как графы, не имеющие ни полного графа K 5 , ни полный двудольный граф K 3,3 как миноры. Как обсуждалось выше, любой граф, не являющийся псевдолесом, содержит в качестве подграфа наручник, цифру 8 или тэта-граф; любой граф наручников или граф в форме восьмерки можно сжать в граф-бабочку (пятивершинная фигура 8), а любой тэта-граф можно сжать в ромбовидный граф (тета-граф из четырех вершин), [22] поэтому любой непсевдолесной граф содержит либо бабочку, либо ромб в качестве минора, и это единственные минор-минимальные графы, не являющиеся псевдолесами. Таким образом, граф является псевдолесом тогда и только тогда, когда в нем нет ни бабочки, ни ромба в качестве минора. Если запретить только ромб, но не бабочку, в результате получится более крупное семейство графов, состоящее из графов-кактусов и непересекающихся объединений нескольких графов-кактусов. [23]
Проще говоря, если рассматривать мультиграфы с петельками , то существует только один запрещенный минор — вершина с двумя петлями.
Раннее алгоритмическое использование псевдолесов включает сетевой симплексный алгоритм и его применение к задачам обобщенного потока, моделирующим преобразование между товарами разных типов. [3] [24] В этих задачах в качестве входных данных дается потоковая сеть , в которой вершины моделируют каждый товар, а ребра моделируют допустимые преобразования между одним товаром и другим. Каждое ребро отмечено мощностью ( какая часть товара может быть преобразована в единицу времени), множителем потока (коэффициент конверсии между товарами) и стоимостью (сколько потерь или, если оно отрицательное, прибыли понесено на единицу продукции). конверсия). Задача состоит в том, чтобы определить, какое количество каждого товара необходимо конвертировать через каждое ребро сети потоков, чтобы минимизировать затраты или максимизировать прибыль, соблюдая при этом ограничения мощности и не позволяя товарам любого типа накапливаться неиспользованными. Задачу такого типа можно сформулировать в виде линейной программы и решить с помощью симплексного алгоритма . Промежуточные решения, возникающие в результате этого алгоритма, а также окончательное оптимальное решение имеют особую структуру: каждое ребро во входной сети либо не используется, либо используется на полную мощность, за исключением подмножества ребер, образующих охватывающий псевдолес из входная сеть, для которой объемы потоков могут находиться в диапазоне от нуля до полной мощности. В этом приложении унициклические графы также иногда называют дополненными деревьями , а максимальные псевдолеса также иногда называют дополненными лесами . [24]
Задача минимального остовного псевдолеса включает в себя поиск остовного псевдолеса минимального веса в большем взвешенном по ребрам графе G . Из-за матроидной структуры псевдолесов максимальные псевдолеса с минимальным весом могут быть найдены с помощью жадных алгоритмов, аналогичных алгоритмам для задачи минимального остовного дерева . Однако в этом случае Габоу и Тарьян нашли более эффективный подход с использованием линейного времени. [2]
Псевдодревесность графа G определяется по аналогии с древесностью как минимальное число псевдолесов, на которые можно разбить его ребра ; эквивалентно, это минимум k такой, что G является ( k ,0)-разреженным, или минимальный k такой, что ребра G могут быть ориентированы так, чтобы сформировать ориентированный граф с исходящей степенью не более k . Благодаря матроидной структуре псевдолесов псевдодревесность может быть вычислена за полиномиальное время. [25]
Случайный двудольный граф с n вершинами на каждой стороне его двудольного деления и cn ребер, выбранных независимо случайным образом из каждой из n 2 возможных пар вершин, с высокой вероятностью является псевдолесом, если c — константа строго меньше единицы. Этот факт играет ключевую роль в анализе хеширования с кукушкой — структуры данных для поиска пар ключ-значение путем просмотра в одной из двух хеш-таблиц мест, определенных по ключу: можно сформировать граф, «граф с кукушкой», чьи вершины соответствуют местоположениям хеш-таблицы, а ребра соединяют два местоположения, в которых может быть найден один из ключей, и алгоритм хеширования кукушки успешно находит местоположения для всех своих ключей тогда и только тогда, когда граф кукушки является псевдолесом. [26]
Псевдолеса также играют ключевую роль в параллельных алгоритмах раскраски графов и связанных с ними задачах. [27]
