В теории графов псевдолес — это неориентированный графНеориентированные графы, рассматриваемые здесь, являются мультиграфами или псевдографами, а не простыми графами., в котором любая связная компонента имеет максимум один цикл. То есть это система вершин и рёбер, соединяющих пары вершин, такая, что никакие два цикла не имеют общих вершин и не могут быть связаны путём. Псевдодерево — это связный псевдолес.
Названия взяты по аналогии с общеизвестными деревьями и лесами (дерево — это связный граф без циклов, лес — объединение несвязных деревьев). Габов и Тарьян приписывают изучение псевдолесов книге 1963 Данцига по линейному программированию, в которой псевдолеса появляются в решении некоторых задач транспортных потоков. Псевдолеса также образуют теоретические графовые модели функций и появляются в некоторых алгоритмических задачах. Псевдолеса являются разреженными графами – они имеют очень малое число рёбер по отношению к числу вершин, и их структура матроидов позволяет разложить некоторые другие семейства редких графов на объединение лесов и псевдолесов. Название "псевдолес" пришло из статьи Пикарда и Керанна.
Определения и структура Мы определяем неориентированный граф как множество вершин и рёбер, таких, что каждое ребро содержит две вершины (возможно, совпадающие) в качестве конечных точек. То есть разрешаются кратные рёбра (рёбра с теми же конечными вершинами) и петли (рёбра, конечные вершины которых совпадают). Подграф графа — это граф, образованный подмножеством вершин и рёбер, такой, что любое ребро в этом подмножестве имеет конечные вершины в подмножестве вершин. Связная компонента неориентированного графа — это подграф, состоящий из вершин и рёбер, которые можно достичь, следуя по рёбрам, исходя из одной стартовой вершины. Граф связан, если любой вершины или ребра можно достичь, следуя из любой другой вершины или ребра. Цикл в неориентированном графе — это связный подграф, в котором любая вершина инцидентна в точности двум рёбрам или является петлёй.
Псевдолес — это неориентированный граф, в котором каждая связная компонента содержит максимум один циклЭто определение, например, использует Габов и Вестерман ().. Эквивалентно, это неориентированный граф, в котором у каждой связной компоненты рёбер не больше, чем вершинЭто определение используют Габов и Тарьян ().. Компоненты, не имеющие циклов — это просто деревья, а компоненты, имеющие единственный цикл, называются 1-деревьями или одноцикловыми графами. То есть 1-дерево — это связный граф, содержащий в точности один цикл. Псевдолес с единственной связной компонентой (обычно называемый псевдодеревом, хотя некоторые авторы определяют псевдодерево как 1-дерево) является либо деревом, либо 1-деревом. В общем случае псевдолес может содержать несколько связных компонент, все из которых являются деревьями или 1-деревьями.
Если удалить из 1-дерева одно из рёбер цикла, в результате получаем дерево. В обратную сторону, если добавить в дерево новое ребро, соединяющее любые две вершины, получим 1-дерево. Путь в дереве, соединяющий две конечные точки добавляемой дуги, вместе с самой добавляемой дугой, образует единственный цикл 1-дерева. Если добавить в 1-дерево ребро, соединяющее одну из вершин дерева с вновь образуемой вершиной, в результате опять получим 1-дерево с ещё одной вершиной. Другой метод построения 1-деревьев начинается с единичного цикла, и к 1-дереву последовательно добавляются вершины произвольное число раз. Рёбра любого 1-дерева можно разделить единственным образом на два подграфа, один из которых — цикл, а второй — лес, при этом каждое дерево леса содержит в точности одну вершину циклаСм., например, доказательство леммы 4 в статье Алвареза, Блеса и Серна ()..
Изучаются также несколько более узкие типы псевдолесов. 1-лес, называемый иногда максимальным псевдолесом, — это лес, к которому нельзя добавить ребро без образования графа с более чем одним циклом. Если псевдолес содержит дерево в качестве одной из компоненты, он не может быть 1-лесом, поскольку можно добавить к этой компоненте ребро с образованием цикла в этой компоненте или добавить ребро, которое присоединит дерево к другой компоненте. Таким образом, 1-леса — это в точности псевдолеса, в которых любая компонента является 1-деревом.
Остовный псевдолес неориентированного графа G — это остовный подграф, являющийся псевдолесом, т. е. псевдолес графа G, содержащий все вершины графа G. Такие псевдолеса не обязаны иметь какие-либо рёбра, поскольку, например, пустой подграф (т. е. содержащий все вершины графа G и не имеющий каких-либо рёбер) является псевдолесом (и его компонентами являются деревья, каждое из которых состоит из единственной вершины).
Максимальные псевдолеса графа G — это подграфы графа G, являющиеся псевдолесами, которые не содержатся в никаком большем псевдолесе, содержащемся в G. Максимальный псевдолес графа G всегда является остовным псевдодеревом, но обратное неверно. Если G не имеет связных компонент, являющихся деревьями, то его максимальные псевдолеса являются 1-лесами, но в случае, когда граф G содержит дерево в качестве компоненты, его максимальные псевдолеса не будут 1-лесами. Говоря точнее, в любом графе G его максимальные псевдолеса состоят из всех лесов графа G вместе с одним или более 1-деревом, покрывающим оставшиеся вершины графа G.
Ориентированные псевдолеса
Версии этих определений используются также для ориентированных графов. Подобно неориентированным графам ориентированные графы состоят из вершин и рёбер, но каждое ребро имеет направление (ориентированное ребро обычно называется дугой). Ориентированный псевдолес — это ориентированный граф, в которой каждая вершина имеет максимум одну исходящую дугу. То есть граф имеет степень исхода, не превосходящую единицы. Ориентированный 1-лес, часто называемый функциональным графом (см ниже), а иногда — максимальным ориентированным псевдолесом, — это ориентированный граф, в котором каждая вершина имеет исходящую степень в точности равную единицеКруска, Рудольф и Снир () вместо этого используют обратное определение, в котором каждая вершина имеет входящую степень единица. Результирующие графы, которые они называют одноцикловыми, являются транспонированными графами графов, рассматриваемых в данной статье . Если D — ориентированный псевдолес, неориентированный граф, образованный удалением направлений из рёбер графа D, является неориентированным псевдолесом.
Число рёбер Любой псевдолес на множестве из n вершин имеет максимум n рёбер, а любой максимальный псевдолес на множестве из n вершин имеет в точности n вершин. В обратную сторону, если граф G имеет свойство, что для любого подмножества S вершин графа число рёбер в порождённом подграфе графа S не превосходит числа вершин графа S, то G является псевдолесом. 1-деревья могут быть определены как связные графы с одинаковым числом вершин и рёбер.
Для семейств графов, если семейство графов имеет свойство, что любой подграф графа в семействе входит в то же семейство и каждый граф в семействе имеет не больше рёбер, чем вершин, то семейство содержит только псевдолеса. Например, любой подграф трекла (граф, нарисованный таким образом, что любая пара рёбер имеет одну точку пересечения) является также треклом, так что гипотезу Конвея, что любой трекл имеет не больше рёбер, чем вершин, можно переформулировать, что каждый трекл является псевдолесом. Точнее, если гипотеза верна, то треклы — это в точности псевдолеса без циклов с четырьмя вершинами и максимум одним циклом с нечётным числом вершин.
Стрейну и Теран обобщили свойства разреженности в определении псевдолесов — он определяют граф как (k,l)-разреженный, если любой непустой подграф с n вершинами имеет максимум kn − l рёбер, и (k,l)-плотным, если он (k,l)-разрежен и имеет в точности kn − l рёбер. Таким образом, псевдолеса — это (1, 0)-разреженные графы, а максимальные псевдолеса — это (1, 0)-плотные графы. Некоторые другие важные семейства графов можно определить для других значений k и l, и если l ≤ k, (k,l)-разреженные графы можно описать как графы, образованные объединением l лесов без общих рёбер и k − l псевдолесов.
Почти любой достаточно редкий случайный граф является псевдолесомБолобаш (). См., в частности, следствие 24, на стр.120, о границе числа вершин, принадлежащих одноцикловым компонентам в случайном графе, и следствие 19, стр.113, о границе числа различных помеченных одноцикловых графов.. То есть, если c является константой (0 < c < 1/2) и Pc(n) — вероятность, что выбранный случайно среди графов с n вершинами и cn рёбрами граф является псевдолесом, то Pc(n) стремится к единице в пределе при росте n. Однако для c > 1/2 почти любой случайный граф с cn рёбрами имеет большую компоненту, не являющуюся одноцикловой.
Перечисление
Граф является простым, если в нём нет петель и кратных рёбер. Число простых 1-деревьев с n помеченными вершинами равно; см. в энциклопедии целочисленных последовательностей.
Значения для n вплоть до 18 можно найти в последовательности Энциклопедии целочисленных последовательностей.
Число максимальных ориентированных псевдолесов с n вершинами, в которых разрешены петли, равно nn, поскольку для любой вершины имеется n возможных конечных вершин исходящих дуг. использовал этот факт для биективного доказательстваО методе биективного доказательства можно почитать в статье Вершика () формулы Кэли, что число неориентированных деревьев на n вершинах равно nn − 2, путём нахождения биекции между максимальными ориентированными псевдолесами и неориентированными деревьями с двумя различными вершинами. Если допускаются петли, число максимальных ориентированных псевдолесов равно (n − 1)n.
Графы функций
Ориентированные псевдолеса и отображения в себя в некотором смысле математически эквивалентны. Любое отображение ƒ на множестве X на себя (то есть эндоморфизм на X) можно интерпретировать как определение ориентированного псевдолеса, который имеет дугу из x в y, когда ƒ(x) = y. Полученный ориентированный псевдолес максимален и может включать петли, если для некоторых x ƒ(x) = x. Исключение петель приводит к немаксимальным псевдолесам. В обратном направлении любой максимальный ориентированный псевдолес определяет отображение ƒ, для которой ƒ(x) равно конечной вершине дуги, исходящей из x, и любой немаксимальный ориентированный псевдолес можно сделать максимальным путём добавления петель и конвертирования в функцию тем же способом. По этой причине максимальные ориентированные псевдолеса иногда называются функциональными графами. Представление функции в виде функционального графа даёт удобный язык описания свойств, которые непросто описать с точки зрения теории функций. Такая техника особенно полезна для задач, использующих итерированные функции, которые соответствуют путям в теории графов.
Поиск циклов, задача прослеживания путей в функциональном графе для нахождения в нём цикла, имеет приложения в криптографии и как часть ро-алгоритма Полларда для факторизации целых чисел и как метод нахождения конфликтов в криптографических хеш-функциях. В этих приложениях предполагается, что ƒ случайна. и изучали свойства функциональных графов, полученных из случайных отображений. В частности, из одного из вариантов парадокса дней рождения следует, что в случайном функциональном графе с n вершинами путь, начинающийся со случайно выбранной вершины, обычно зацикливается после O(√n) шагов. Конягин и др. осуществили анализ и вычислительные статистические исследования.