У теорії графів псевдолі́с — це неорієнтований графРозглянуті тут неорієнтовані графи є мультиграфами або псевдографами, а не простими графами., у якому будь-яка зв'язна компонента має не більше одного циклу. Тобто це система вершин і ребер, що з'єднують пари вершин, така, що жодні два цикли не мають спільних вершин і не можуть бути пов'язаними шляхом. Псевдоде́рево — це зв'язний псевдоліс.
Назви взято за аналогією із деревами та лісами (дерево — це зв'язний граф без циклів, ліс — незв'язне об'єднання дерев). Габов і Тарджан приписують вивчення псевдолісів Данцігу в книзі 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) кроків. та ін. здійснили аналіз та обчислювальні статистичні дослідження.
Мартін, Одлижко і Вольфрам досліджували псевдоліси, що моделюють динаміку клітинних автоматів. Ці функціональні графи, які вони назвали діаграмами переходів станів, мають по одній вершині для кожної можливої конфігурації, в якій можуть перебувати комірки клітинного автомата, а дуги з'єднують кожну конфігурацію з конфігурацією, яка з неї отримується за правилами клітинного автомата. Зі структури цих діаграм можна отримати властивості автомата, такі як число компонентів, довжину скінченних циклів, глибину дерев, що з'єднують нескінченні стани цих циклів, або симетрії діаграми. Наприклад, будь-яка вершина без вхідної дуги відповідає едемському саду, а вершини з петлею відповідають натюрморту.
Інше раннє застосування функціональних графів — у ланцюжкахВ англійському варіанті — trains, що використовуються для вивчення систем трійок Штейнера. Ланцюжок системи трійок — це функціональний граф, що містить по вершині кожної можливої трійки символів. Кожна трійка pqr відображається функцією в stu, де pqs, prt і qru — трійки, що належать системі трійок і містять пари pq, pr і qr відповідно. Показано, що, попри громіздкість обчислення, ланцюжки є потужним інваріантом системи трійок.
Біциклічний матроїд