Перегляд вихідного коду сторінки Псевдоліс

[[Файл:Pseudoforest.svg|міні|1-ліс (максимальний псевдоліс), утворений трьома 1-деревами]]
У [[Теорія графів|теорії графів]] '''псевдолі́с'''&nbsp;— це [[Граф (математика)|неорієнтований граф]]<ref name="multigraph">Розглянуті тут неорієнтовані графи є [[Мультиграф|мультиграфами]] або псевдографами, а не [[Простий граф|простими графами]].</ref>, у якому будь-яка [[Компонента зв'язності графа|зв'язна компонента]] має не більше одного [[Цикл (теорія графів)|циклу]]. Тобто це система [[Вершина (теорія графів)|вершин]] і [[Словник термінів теорії графів|ребер]], що з'єднують пари вершин, така, що жодні два цикли не мають спільних вершин і не можуть бути пов'язаними [[Шлях (теорія графів)|шляхом]]. '''Псевдоде́рево'''&nbsp;— це зв'язний псевдоліс.

Назви взято за аналогією із [[Дерево (теорія графів)|деревами]] та [[Ліс (теорія графів)|лісами]] (дерево&nbsp;— це [[зв'язний граф]] без циклів, ліс&nbsp;— незв'язне об'єднання дерев). Габов і [[Роберт Андре Тарджан|Тарджан]]{{Sfn|Gabow, Tarjan|1988}} приписують вивчення псевдолісів Данцігу в книзі 1963 року з [[Лінійне програмування|лінійного програмування]], в якій псевдоліси з'являються в розв'язуванні деяких задач [[Потокова мережа|транспортних потоків]]{{Sfn|Dantzig|1963}}. Псевдоліси також утворюють теоретичні графові моделі функцій і з'являються в деяких [[алгоритм]]ічних задачах. Псевдоліси є [[Щільний граф|розрідженими графами]]&nbsp;— вони мають дуже мале число ребер відносно вершин, і їхня структура [[матроїд]]ів дозволяє деякі інші сімейства розріджених графів розкласти на об'єднання лісів і псевдолісів. Назва «псевдоліс» прийшла зі статті Пікара та Кейрана{{Sfn|Picard, Queyranne|1982}}.

== Визначення та структура ==
Визначимо неорієнтований граф як множину [[Вершина (теорія графів)|вершин]] і [[Словник термінів теорії графів|ребер]], таких, що кожне ребро містить дві вершини (які, можливо, збігаються) як кінцеві точки. Тобто дозволено кратні ребра (ребра з тими ж кінцевими вершинами) і петлі (ребра, кінцеві вершини яких збігаються)<ref name="multigraph"/>. [[Словник термінів теорії графів|Підграф]] графа ц е граф, утворений підмножиною вершин і ребер, такий, що будь-яке ребро в цій підмножині має кінцеві вершини в підмножині вершин.
[[Компонента зв'язності графа|Зв'язна компонента]] неорієнтованого графа&nbsp;— це підграф, що складається з вершин і ребер, які можна досягти, рухаючись по ребрах, виходячи з однієї стартової вершини. Граф зв'язний, якщо будь-якої вершини або ребра можна досягти, рухаючись із будь-якої іншої вершини або ребра. [[Цикл (теорія графів)|Цикл]] у неорієнтованому графі&nbsp;— це зв'язний підграф, у якому будь-яка вершина має рівно два ребра або є петлею.
[[Файл:The21.GIF|міні|21 граф з одним циклом і максимум шістьма вершинами]]
'''Псевдоліс'''&nbsp;— це неорієнтований граф, у якому кожна зв'язна компонента містить максимум один цикл<ref>Це визначення, наприклад, використовують Габов і Вестерман ({{Harvtxt|Gabow, Westermann|1992}}).</ref>. Еквівалентно, це неорієнтований граф, у якому в кожній зв'язній компоненті ребер не більше, ніж вершин<ref>Це визначення використовують Габов і Тарджан ({{Harvtxt|Gabow, Tarjan|1988}}).</ref>. Компоненти, що не мають циклів&nbsp;— це просто [[Дерево (теорія графів)|дерева]], а компоненти, що мають єдиний цикл, називають '''1-деревами''' або '''одноцикловими графами'''. Тобто 1-дерево&nbsp;— це зв'язний граф, що містить рівно один цикл. Псевдоліс із єдиною зв'язною компонентою (зазвичай званий '''псевдодеревом''', хоча деякі автори визначають псевдодерево як 1-дерево) є або деревом, або 1-деревом. У загальному випадку псевдоліс може містити кілька зв'язних компонент, всі з яких є деревами або 1-деревами.

Якщо видалити з 1-дерева одне з ребер циклу, отримаємо дерево. І навпаки, якщо додати в дерево нове ребро, що з'єднує будь-які дві вершини, отримаємо 1-дерево. Шлях у дереві, що з'єднує дві кінцеві точки доданої дуги, разом з самою доданою дугою, утворює єдиний цикл 1-дерева. Якщо додати в 1-дерево ребро, що з'єднує одну з вершин дерева з новоствореною вершиною, результатом знову буде 1-дерево зі ще однією вершиною. Інший метод побудови 1-дерев починається з одиничного циклу, і до 1-дерева послідовно довільне число разів додаються вершини. Ребра будь-якого 1-дерева можна розділити єдиним чином на два підграфи, один з яких&nbsp;— цикл, а другий&nbsp;— ліс, при цьому кожне дерево лісу містить рівно одну вершину циклу<ref>Див., наприклад, доведення леми 4 в статті Алвареза, Блеса і Серна ({{Harvtxt|Àlvarez et al|2002}}).</ref>.

Вивчаються також кілька вужчих типів псевдолісів.

: '''1-ліс''', званий іноді '''максимальним псевдолісом'''&nbsp;— це ліс, до якого не можна додати ребра, не утворивши графа з більш ніж одним циклом. Якщо однією з компонент псевдолісу є дерево, він не може бути 1-лісом, оскільки можна додати до цієї компоненти ребро з утворенням циклу в ній або додати ребро, яке приєднає дерево до іншої компоненти. Таким чином, 1-ліси&nbsp;— це точно псевдоліси, в яких будь-яка компонента є 1-деревом.

: '''Кістяковий псевдоліс''' неорієнтованого графа ''G''&nbsp;— це [[Словник термінів теорії графів|кістяковий підграф]], що є псевдолісом, тобто, псевдоліс графа ''G'', що містить всі вершини графа ''G''. Такі псевдоліси не зобов'язані мати будь-яких ребер, оскільки, наприклад, порожній підграф (тобто такий, що містить усі вершини графа ''G'' і не має ребер) є псевдолісом (і його компонентами є дерева, кожне з яких складається з єдиної вершини).

: '''Максимальні псевдоліси''' графа ''G''&nbsp;— це підграфи графа ''G'', що є псевдолісами, які не містяться в жодному більшому псевдолісі, що міститься в ''G''. Максимальний псевдоліс графа ''G'' завжди є кістяковим псевдодеревом, але обернене хибне. Якщо ''G'' не має зв'язних компонент, що є деревами, то його максимальні псевдоліси є 1-лісами, але у випадку, коли граф ''G'' містить дерево як компоненту, його максимальні псевдоліси не будуть 1-лісами. Точніше, в будь-якому графі ''G'' його максимальні псевдоліси складаються з усіх лісів графа ''G'' разом з одним або більше 1-деревом, що покриває решту вершин графа ''G''.

== Орієнтовані псевдоліси ==
Версії цих визначень використовуються також для [[Орієнтований граф|орієнтованих графів]]. Подібно до неорієнтованих графів орієнтовані графи складаються з вершин і ребер, але кожне ребро має напрямок (орієнтоване ребро зазвичай називають дугою). '''Орієнтований псевдоліс'''&nbsp;— це орієнтований граф, у якому кожна вершина має максимум одну вихідну дугу. Тобто граф має [[Дерево (теорія графів)|степінь виходу]], що не перевищує одиниці. '''Орієнтований 1-ліс''', часто званий '''функціональним графом''' (див. [[Псевдоліс#Графи функцій|нижче]]), а іноді&nbsp;— '''максимальним орієнтованим псевдолісом'''&nbsp;— це орієнтований граф, у якому степінь виходу кожної з вершин дорівнює одиниці<ref>Крускал, Рудольф і Снір ({{Harvtxt|Kruskal et al|1990}}) замість цього використовують обернене визначення, в якому кожна вершина має вхідний степінь одиниця. Отримані графи, які вони називають одноцикловими, є [[Транспонований граф|транспонованими графами]] графів, розглянутих у цій статті.</ref>. Якщо ''D''&nbsp;— орієнтований псевдоліс, неорієнтований граф, утворений видаленням напрямків з ребер графа ''D'', є неорієнтованим псевдолісом.

== Число ребер ==
Будь-який псевдоліс на множині з ''n'' вершин має максимум ''n'' ребер, а будь-який максимальний псевдоліс на множині з ''n'' вершин має рівно ''n'' вершин. І навпаки, якщо граф ''G'' має властивість, що для будь-якої підмножини ''S'' вершин графа число ребер у [[Породжений підграф|породженому підграфі]] графа ''S'' не перевищує числа вершин графа ''S'', то ''G'' є псевдолісом. 1-дерева можна визначити як зв'язні графи з однаковим числом вершин і ребер{{Sfn|Gabow, Tarjan|1988}}.

Для сімейств графів, якщо сімейство графів має властивість, що будь-який підграф графа в сімействі входить у те ж сімейство і кожен граф у сімействі має не більше ребер, ніж вершин, то сімейство містить тільки псевдоліси. Наприклад, будь-який підграф [[трекл]]а (граф, [[Візуалізація графів|намальований]] так, що будь-яка пара ребер має одну точку перетину) є також треклом, так що [[Трекл#Гіпотеза Конвея|гіпотезу Конвея]], що будь-який трекл має не більше ребер, ніж вершин, можна переформулювати, що кожен трекл є псевдолісом. Точніше, якщо гіпотеза істинна, то трекли&nbsp;— це точно псевдоліси без циклів з чотирма вершинами і максимум одним циклом з непарним числом вершин{{Sfn|Woodall|1969}}{{Sfn|Lovász et al|1997}}.

[[Ілеана Штрейну|Штрейну]] і Теран{{Sfn|Streinu, Theran|2009}} узагальнили властивості [[Щільний граф|розрідженості]] у визначенні псевдолісів&nbsp;— вони визначають граф як (''k'',''l'')-розріджений, якщо будь-будь-який непорожній підграф із ''n'' вершинами має максимум ''kn''&nbsp;−&nbsp;''l'' ребер, і (''k'',''l'')-щільним, якщо він (''k'',''l'')-розріджений і має рівно ''kn''&nbsp;−&nbsp;''l'' ребро. Таким чином, псевдоліси&nbsp;— це (1, 0)-розріджені графи, а максимальні псевдоліси&nbsp;— це (1, 0)-щільні графи. Деякі інші важливі сімейства графів можна визначити для інших значень ''k'' і ''l'', і якщо ''l''&nbsp;≤&nbsp;''k'', (''k'',''l'')-розріджені графи можна описати як графи, утворені об'єднанням ''l'' лісів без спільних ребер і ''k''&nbsp;−&nbsp;''l'' псевдолісів{{Sfn|Whiteley|1988}}.

Майже будь-який досить розріджений [[випадковий граф]] є псевдолісом<ref name="rg">Болобаш ({{Harvtxt|Bollobás|1985}}). Див., зокрема, наслідок 24, на стор.120, про межу числа вершин, що належать одноцикловим компонентам у випадковому графі, і наслідок 19, стор.113, про межу числа різних помічених одноциклових графів.</ref>. Тобто, якщо ''c''&nbsp;— стала (0 < ''c'' < 1/2) і P<sub>''c''</sub>(''n'')&nbsp;— ймовірність, що вибраний випадково серед графів з ''n'' вершинами і ''cn'' ребрами граф є псевдолісом, то P<sub>''c''</sub>(''n'') прямує до одиниці в границі при зростанні ''n''. Однак для ''c'' > 1/2 майже будь-який випадковий граф з ''cn'' ребрами має велику компоненту, яка не є одноцикловою.

== Перерахування ==
Граф є ''простим'', якщо в ньому немає петель і кратних ребер. Число простих 1-дерев з ''n'' позначеними вершинами дорівнює<ref>{{Harvtxt|Riddell|1951}}; див. {{OEIS2C|A057500}} в [[Енциклопедія послідовностей цілих чисел|Енциклопедії послідовностей цілих чисел]].</ref>

: <math>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}.</math>

Значення для ''n'' аж до 18 можна знайти в послідовності {{OEIS2C|A057500}} [[Енциклопедія послідовностей цілих чисел|Енциклопедії цілочисельних послідовностей]].

Число максимальних орієнтованих псевдолісів із ''n'' вершинами, в яких дозволено петлі, дорівнює ''n<sup>n</sup>'', оскільки для будь-якої вершини є ''n'' можливих скінченних вершин вихідних дуг. {{Не перекладено|Андре Жуаяль||en|André Joyal}} використав цей факт для [[Бієктивне доведення|бієктивного доведення]]<ref>Про метод бієктивного доведення можна почитати в статті Вершика ({{Harvtxt|Вершик|1986}})</ref> [[Формула Келі|формули Келі]], що число неорієнтованих дерев на ''n'' вершинах дорівнює ''n''<sup>''n''&nbsp;−&nbsp;2</sup>, шляхом знаходження біекції між максимальними орієнтованими псевдолісами і неорієнтованими деревами з двома різними вершинами{{Sfn|Aigner, Ziegler|1998}}. Якщо допускаються петлі, число максимальних орієнтованих псевдолісів дорівнює (''n''&nbsp;−&nbsp;1)<sup>''n''</sup>.

== Функціональні графи ==
[[Файл:Functional_graph.svg|міні|Функція на множині {0,1,2,3,4,5,6,7,8} на себе та відповідний функціональний граф]]
Орієнтовані псевдоліси та відображення в собе в певному сенсі математично еквівалентні. Будь-яке відображення на множині ''X'' на себе (тобто [[ендоморфізм]] на ''X'') можна інтерпретувати як визначення орієнтованого псевдолісу, який має дугу з ''x'' в ''y'', коли ƒ(''x'') = ''y''. Отриманий орієнтований псевдоліс максимальний і може включати [[Петля (теорія графів)|петлі]], якщо для деяких ''x'' ƒ(''x'') = ''x''. Виключення петель призводить до немаксимальних псевдолісів. І навпаки, будь-який максимальний орієнтований псевдоліс визначає відображення ƒ, для якого ƒ(''x'') дорівнює кінцевій вершині дуги, що виходить з ''x'' і будь-який немаксимальний орієнтований псевдоліс можна зробити максимальним, додавши петлі і конвертувавши у функцію тим самим способом. Тому максимальні орієнтовані псевдоліси іноді називають '''функціональними графами'''{{Sfn|Gabow, Tarjan|1988}}. Подання функції як функціонального графа дає зручну мову опису властивостей, які непросто описати з погляду теорії функцій. Така техніка особливо корисна для задач, що використовують [[Ітерована функція|ітеровані функції]], які відповідають [[Шлях (граф)|шляхам]] у теорії графів.

[[Виявлення циклу|Пошук циклів]], задача простежування шляхів у функціональному графі для знаходження в ньому циклу, застосовується в [[Криптографія|криптографії]] та [[Алгоритмічна теорія чисел|обчислювальній теорії чисел]] як частина [[P-алгоритм Поларда|ро-алгоритму Поларда]] для [[Факторизація цілих чисел|факторизації цілих чисел]] і як метод знаходження конфліктів у [[Криптографічна геш-функція|криптографічних геш-функціях]]. У цих застосуваннях передбачається, що ƒ випадкова. {{Не перекладено|Філіп Флажоле|Флажоле|en|Philippe Flajolet}} та {{Не перекладено|Андрю Одлижко|Одлижко|en|Andrew Odlyzko}}{{Sfn|Flajolet, Odlyzko|1990}} вивчали властивості функціональних графів, отриманих із випадкових відображень. Зокрема, з одного з варіантів [[Парадокс днів народження|парадоксу днів народження]] випливає, що у випадковому функціональному графі з ''n'' вершинами шлях, що починається з випадково вибраної вершини, зазвичай зациклюється після O(''√n'') кроків. {{Нп|Конягін Сергій Володимирович|Конягін|ru|Конягин, Сергей Владимирович}} та ін. здійснили аналіз та обчислювальні статистичні дослідження{{Sfn|Konyagin et al|2016}}.

Мартін, Одлижко і [[Стівен Вольфрам|Вольфрам]]{{Sfn|Martin, Odlyzko, Wolfram|1984}} досліджували псевдоліси, що моделюють динаміку [[Клітинний автомат|клітинних автоматів]]. Ці функціональні графи, які вони назвали ''діаграмами переходів станів'', мають по одній вершині для кожної можливої конфігурації, в якій можуть перебувати комірки клітинного автомата, а дуги з'єднують кожну конфігурацію з конфігурацією, яка з неї отримується за правилами клітинного автомата. Зі структури цих діаграм можна отримати властивості автомата, такі як число компонентів, довжину скінченних циклів, глибину дерев, що з'єднують нескінченні стани цих циклів, або симетрії діаграми. Наприклад, будь-яка вершина без вхідної дуги відповідає [[Едемський сад (клітинний автомат)|едемському саду]], а вершини з петлею відповідають [[Натюрморт (конфігурація клітинного автомата)|натюрморту]].

Інше раннє застосування функціональних графів&nbsp;— у ''ланцюжках''<ref>В англійському варіанті&nbsp;— trains</ref>, що використовуються для вивчення [[Система Штейнера|систем трійок Штейнера]]{{Sfn|White|1913}}{{Sfn|Colbourn, Colbourn, Rosenbaum|1982}}{{Sfn|Stinson|1983}}. Ланцюжок системи трійок&nbsp;— це функціональний граф, що містить по вершині кожної можливої трійки символів. Кожна трійка ''pqr'' відображається функцією в ''stu'', де ''pqs'', ''prt'' і ''qru''&nbsp;— трійки, що належать системі трійок і містять пари ''pq'', ''pr'' і ''qr'' відповідно. Показано, що, попри громіздкість обчислення, ланцюжки є потужним інваріантом системи трійок.

== Біциклічний матроїд ==
[[Матроїд]]&nbsp;— це математична структура, в якій деякі множини елементів визначаються як незалежні, у тому сенсі, що незалежні множини задовольняють властивостям, які моделюють властивості [[Лінійно незалежні вектори|лінійної незалежності]] у [[Векторний простір|векторному просторі]]. Одним зі стандартних прикладів матроїдів є {{Не перекладено|графовий матроїд||en|graphic matroid}}, у якому незалежні множини&nbsp;— це множини ребер у лісах графа. Матроїдна структура лісів важлива для алгоритмів обчислення [[Мінімальне кістякове дерево|мінімального кістякового дерева]] графа. Аналогічним можна визначити матроїди для псевдолісів.

Для будь-якого графа ''G'' = (''V'',''E'') можна визначити матроїд на ребрах графа ''G'', в якому множина ребер незалежна [[тоді й лише тоді]], коли ця множина утворює псевдоліс. Цей матроїд відомий як '''{{Не перекладено|біциклічний матроїд||en|bicircular matroid}}''' графа ''G''{{Sfn|Simoes-Pereira|1972}}{{Sfn|Matthews|1977}}. Мінімальні залежні множини для цього матроїда&nbsp;— це мінімальні зв'язні підграфи графа ''G'', що мають більше одного циклу, і ці підграфи іноді називаються біциклами. Існує три можливих типи біциклів&nbsp;— [[Словник термінів теорії графів#тета|граф «тета»]], дві вершини якого, з'єднані трьома шляхами, які не мають внутрішніх спільних точок; «вісімка», що складається з двох циклів, які мають одну спільну вершину, і «наручники», утворені з двох циклів, що не мають спільних вершин, з'єднаних шляхом<ref>{{Cite web|url=http://www.math.binghamton.edu/zaslav/Bsg/glossary.html|title=Glossary of Signed and Gain Graphs and Allied Areas|accessdate=2016-10-23|archivedate=2016-03-03|archiveurl=https://web.archive.org/web/20160303175909/http://www.math.binghamton.edu/zaslav/Bsg/glossary.html|deadurl=no}}</ref>. Граф є псевдолісом тоді й лише тоді, коли він не містить біциклу як підграфа{{Sfn|Streinu, Theran|2009}}.

== Заборонені мінори ==
[[Файл:Butterfly_and_diamond_graphs.svg|міні| [[Метелик (теорія графів)|«Метелик»]] (ліворуч) та [[Алмаз (теорія графів)|«алмаз»]] (праворуч), заборонені [[Мінор графа|мінори]] псевдолісів]]
Утворення [[Мінор графа|мінору]] псевдолісу стягуванням деяких ребер та видаленням деяких інших ребер утворює новий псевдоліс. Таким чином, сімейство псевдолісів [[Замикання (математика)|замкнуте]] за мінорами, а з [[Теорема Робертсона — Сеймура|теореми Робертсона&nbsp;— Сеймура]] тоді випливає, що псевдоліси можна описати в термінах скінченного набору [[Характеризація забороненими графами|заборонених мінорів]], аналогічно [[Теорема Вагнера|теоремі Вагнера]] про опис [[Планарний граф|планарних графів]] як графів, які не мають мінорами ні [[Повний двочастковий граф|повного]] [[Повний граф|графа]] ''K''<sub>5</sub>, ні [[Повний двочастковий граф|повного двочасткового графа]] ''K''<sub>3,3</sub>. Як обговорювалося раніше, будь-який граф, який не є псевдолісом, містить як підграф «наручники», «вісімку» або «тету». Будь-які «наручники» і «вісімки» можна стягнути до ''[[Метелик (теорія графів)|«метелика»]]'' («вісімка» з п'ятьма вершинами), а будь-яку «тету» можна стягнути до «''[[Алмаз (теорія графів)|алмазу]]''» («тета» із чотирма вершинами)<ref>Див. цю термінологію в [http://www.graphclasses.org/smallgraphs.html списку малих графів]( {{Webarchive|url=http://archive.wikiwix.com/cache/20121118113238/http://www.graphclasses.org/smallgraphs.html |date=18 листопада 2012 }}) на сайті [http://www.graphclasses.org/ Information System on Graph Class Inclusions]( {{Webarchive|url=https://web.archive.org/web/20190205084239/http://www.graphclasses.org/ |date=5 лютого 2019 }}). Однак, назва ''метелик'' может стосуватися іншого сімейства графів, пов'язаних із [[Граф гіперкуба|гіперкубами]].</ref>, Так що будь-який граф, що не є псевдолісом, містить як мінор «метелика» або «алмаз», і тільки ці графи є мінімальними графами, що не належать до сімейства псевдолісів. Якщо заборонити лише «алмаз», але не «метелика», отримаємо ширше сімейство графів, що складається з [[Кактус (теорія графів)|«кактусів»]] та розрізненого об'єднання набору «кактусів»{{Sfn|El-Mallah, Colbourn|1988}}.

Якщо розглядати [[мультиграф]]и з [[Петля (теорія графів)|петлями]], є лише один заборонений мінор&nbsp;— вершина з двома петлями.

== Алгоритми ==
Раннє алгоритмічне застосування псевдолісів використовувало алгоритм ''мережевого симплекса'' та його застосування до узагальненої задачі про потоки в мережах для моделювання перетворень [[Товар|продуктів]] з одного типу в інший{{Sfn|Dantzig|1963}}{{Sfn|Ahuja, Magnanti, Orlin|1993}}. У цих задачах задається [[Потокова мережа|транспортна мережа]], де вершини моделюють кожен продукт, а ребра моделюють допустимість перетворення з одного продукту на інший. Кожне ребро маркується ''пропускною спроможністю'' (кількість продукту, яку можна перетворити за одиницю часу), ''потоком'' (швидкістю перетворення між продуктами) та ''ціною'' (скільки втрачаємо при перетворенні на одиницю продукту). Задача полягає у визначенні, скільки кожного продукту потрібно перетворити на кожній дузі транспортної мережі з метою мінімізувати ціну або максимізувати дохід, не порушуючи обмежень і не дозволяючи будь-якому типу продукту залишитися невикористаним. Цей тип задач можна сформулювати як [[Лінійне програмування|задачу лінійного програмування]] та розв'язати за допомогою [[симплекс-метод]]у. Проміжні розв'язки, одержувані з цього алгоритму, як і кінцевий оптимальний розв'язок, мають спеціальні структури&nbsp;— кожна дуга транспортної мережі або не використовується, або використовує максимальне значення пропускної спроможності, за винятком підмножини дуг, що утворюють кістяк псевдолісу транспортної мережі, і на цій підмножині дуг потік може набувати значення від нуля до максимальної пропускної здатності. У цьому застосуванні одноциклові графи іноді називають також ''доповненими деревами'', а максимальні псевдоліси&nbsp;— ''доповненими лісами''{{Sfn|Ahuja, Magnanti, Orlin|1993}}.

''Завдання про мінімальний кістяковий псевдоліс'' використовує перебування кістякового псевдолісу мінімальної ваги у більшому графі ''G'' з вагами. Внаслідок матроїдної структури псевдолісів максимальні псевдоліса з мінімальною вагою можна знайти за допомогою [[Жадібний алгоритм|жадібних алгоритмів]] подібно до задачі знаходження [[Мінімальне кістякове дерево|мінімального кістякового дерева]]. Однак Габов і [[Роберт Андре Тарджан|Тарджан]] знайшли для цього випадку ефективніший підхід з лінійним часом{{Sfn|Gabow, Tarjan|1988}}.

'''Псевдодеревність''' графа ''G'' визначається за аналогією з [[деревність|деревністю]] як найменше число псевдолісів, на які можна розділити ребра. Еквівалентно, це найменше число ''k'', таке, що граф ''G'' є (''k'', 0)-розрідженим, або найменше число ''k'', таке що ребрам графа ''G'' можна задати напрямки, так що отриманий орієнтований граф матиме степінь результату, що не перевищує ''k''. Внаслідок матроїдної структури псевдолісів псевдодеревність можна обчислити за поліноміальний час<ref>{{Harvtxt|Gabow, Westermann|1992}}. Див. також швидкі схеми апроксимації Ковалика ({{Harvtxt|Kowalik|2006}}).</ref>.

[[Випадковий граф|Випадковий]] [[двочастковий граф]] із ''n'' вершинами на кожній його частці з ''cn'' ребрами, вибраними випадково і незалежно для кожної пари ''n''<sup>2</sup> можливих пар вершин з великою ймовірністю є псевдолісом за постійного ''c'' строго меншого від одиниці. Цей факт відіграє ключову роль в аналізі [[Зозулине хешування|зозулиного гешування]], структурі даних для пошуку пар ключ-значення переглядом однієї з двох геш-таблиць на місці, що визначається ключем,&nbsp;— можна сформувати «парний граф», вершини якого відповідають положенню в геш-таблицях, а ребра пов'язують два розташування, в яких один із ключів можна знайти. Парне гешування знаходить усі ключі тоді й лише тоді, коли парний граф є псевдолісом{{Sfn|Kutzelnigg|2006}}.

Псевдоліси відіграють також ключову роль у [[Паралельний алгоритм|паралельних алгоритмах]] [[розфарбовування графів]] і пов'язаних задач{{Sfn|Goldberg, Plotkin, Shannon|1988}}{{Sfn|Kruskal et al|1990}}.

== Примітки ==
{{примітки|2}}

== Література ==
{{Refbegin|2}}
* {{Книга
|автор = Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin
|ref = Ahuja, Magnanti, Orlin
|заголовок = Network Flows: Theory, Algorithms and Applications
|видавництво = Prentice Hall
|рік = 1993
|ISBN = 0-13-617549-X
}}
* {{Книга
|автор = Martin Aigner, Günter M. Ziegler
|ref = Aigner, Ziegler
|сторінки = 141–146
|видавництво = [[Springer-Verlag]]
|заголовок = [[Proofs from THE BOOK]]
|рік = 1998
}}
* {{Книга
|автор = Carme Àlvarez, Maria Blesa, Maria Serna
|ref = Àlvarez et al
|заголовок = Proc. 14th ACM [[Symposium on Parallel Algorithms and Architectures]]
|рік = 2002
|сторінки = 183–197
|doi = 10.1145/564870.564903
}}
* {{Книга
|автор = Béla Bollobás
|ref = Bollobás
|заголовок = Random Graphs
|видавництво = Academic Press
|рік = 1985
}}
* {{Стаття|author=Marlene J. Colbourn, Charles J. Colbourn, Wilf L. Rosenbaum|ref=Colbourn, Colbourn, Rosenbaum|title=Trains: an invariant for Steiner triple systems|видання={{не переведено 5|Ars Combinatoria (журнал)|Ars Combinatoria||Ars Combinatoria (journal)}}|том=13|рік=1982|pages=149–162}}
* {{Книга
|автор = G. B. Dantzig
|ref = Dantzig
|заголовок = Linear Programming and Extensions
|видавництво = Princeton University Press
|рік = 1963
}}
* {{Стаття|author=Ehab El-Mallah, Charles J. Colbourn|ref=El-Mallah, Colbourn|title=The complexity of some edge deletion problems|видання=IEEE Transactions on Circuits and Systems|том=35|issue=3|рік=1988|pages=354–362|doi=10.1109/31.1748}}
* {{Книга
|автор = P. Flajolet, A. Odlyzko
|ref = Flajolet, Odlyzko
|видавництво = Springer-Verlag
|серія = Lecture Notes in Computer Science
|заголовок = Advances in Cryptology – EUROCRYPT '89: [[Workshop on the Theory and Application of Cryptographic Techniques]]
|том = 434
|сторінки = 329–354
|рік = 1990
}}
* {{Стаття|author=H. N. Gabow, R. E. Tarjan|ref=Gabow, Tarjan|title=A linear-time algorithm for finding a minimum spanning pseudoforest|видання=Information Processing Letters|том=27|рік=1988|issue=5|pages=259–263|doi=10.1016/0020-0190(88)90089-0}}.
* {{Стаття|author=H. N. Gabow, H. H. Westermann|ref=Gabow, Westermann|title=Forests, frames, and games: Algorithms for matroid sums and applications|видання=Algorithmica|том=7|issue=1|рік=1992|pages=465–497|doi=10.1007/BF01758774}}
* {{Стаття|author=A. V. Goldberg, S. A. Plotkin, G. E. Shannon|ref=Goldberg, Plotkin, Shannon|title=Parallel symmetry-breaking in sparse graphs|видання=[[SIAM Journal on Discrete Mathematics]]|том=1|issue=4|рік=1988|pages=434–446|doi=10.1137/0401044}}
* {{Стаття|author=Sergei Konyagin, Florian Luca, Bernard Mans, Luke Mathieson, Igor E. Shparlinski|ref=Konyagin et al|title=Functional Graphs of Polynomials over Finite Fields|рік=2016|том=116|видання=Journal of Combinatorial Theory|серія=B}}
* {{Книга
|автор = Ł. Kowalik
|ref = Kowalik
|видавництво = Springer-Verlag
|відповідальний = Tetsuo Asano
|серія = Lecture Notes in Computer Science
|том = 4288
|заголовок = Proceedings of the International Symposium on Algorithms and Computation
|рік = 2006
|сторінки = 557–566
|doi = 10.1007/11940128
}}
* {{Стаття|author=Clyde P. Kruskal, Larry Rudolph, Marc Snir|ref=Kruskal et al|title=Efficient parallel algorithms for graph problems|видання=Algorithmica|рік=1990|том=5|issue=1|pages=43–64|doi=10.1007/BF01840376}}
* {{Стаття|author=Jean-Claude Picard, Maurice Queyranne|ref=Picard, Queyranne|doi=10.1002/net.3230120206|видання=Networks|pages=141–159|title=A network flow solution to some nonlinear 0–1 programming problems, with applications to graph theory|url=https://archive.org/details/sim_networks_summer-1982_12_2/page/141|том=12|рік=1982}}
* {{Книга
|автор = Reinhard Kutzelnigg
|ref = Kutzelnigg
|посилання = http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/viewFile/590/1710
|заголовок = Fourth Colloquium on Mathematics and Computer Science
|серія = Discrete Mathematics and Theoretical Computer Science
|рік = 2006
|том = AG
|сторінки = 403–406
}}
* {{Стаття|author=L. Lovász, J. Pach, M. Szegedy|ref=Lovász et al|title=On Conway's thrackle conjecture|видання=[[Discrete and Computational Geometry]]|том=18|issue=4|рік=1997|pages=369–376|doi=10.1007/PL00009322}}
* {{Стаття|author=O. Martin, A. M. Odlyzko, S. Wolfram|ref=Martin, Odlyzko, Wolfram|title=Algebraic properties of cellular automata|видання=Communications in Mathematical Physics|том=93|issue=2|рік=1984|pages=219–258|doi=10.1007/BF01223745|url=http://www.stephenwolfram.com/publications/articles/mathematics/84-properties/|bibcode=1984CMaPh..93..219M}}
* {{Стаття|author=L. R. Matthews|ref=Matthews|title=Bicircular matroids|видання=The Quarterly Journal of Mathematics. Oxford. Second Series|том=28|рік=1977|issue=110|pages=213–227|doi=10.1093/qmath/28.2.213}}
* {{Книга
|автор = R. J. Riddell
|ref = Riddell
|заголовок = Contributions to the Theory of Condensation
|серія = Ph.D. thesis
|видавництво = University of Michigan
|місце = Ann Arbor
|рік = 1951
|bibcode = 1951PhDT........20R
}}.
* {{Стаття|author=J. M. S. Simoes-Pereira|ref=Simoes-Pereira|title=On subgraphs as matroid cells|видання=[[Mathematische Zeitschrift]]|том=127|рік=1972|issue=4|pages=315–322|doi=10.1007/BF01111390}}.
* {{Стаття|author=D. R. Stinson|ref=Stinson|title=A comparison of two invariants for Steiner triple systems: fragments and trains|видання=Ars Combinatoria|том=16|рік=1983|pages=69–76}}.
* {{Стаття|doi=10.1007/s00373-008-0834-4|title=Sparsity-certifying Graph Decompositions|рік=2009|author=I. Streinu, L. Theran|ref=Streinu, Theran|видання=[[Graphs and Combinatorics]]|том=25|issue=2|pages=219}}
* {{Стаття|author=H. S. White|ref=White|title=Triple-systems as transformations, and their paths among triads|видання=[[Transactions of the American Mathematical Society]]|рік=1913|том=14|issue=1|pages=6–13|doi=10.2307/1988765|publisher=American Mathematical Society}}
* {{Стаття|author=W. Whiteley|ref=Whiteley|title=The union of matroids and the rigidity of frameworks|видання=[[SIAM Journal on Discrete Mathematics]]|том=1|issue=2|pages=237–255|рік=1988|doi=10.1137/0401025}}
* {{Книга
|автор = D. R. Woodall
|ref = Woodall
|заголовок = Combinatorial Mathematics and Its Applications
|відповідальний = D. J. A. Welsh
|видавництво = Academic Press
|рік = 1969
|сторінки = 335–348
}}.
* {{Стаття|author=А. М. Вершик|ref=Вершик|title=Биективное доказательство тождества Якоби и перестройки диаграмм Юнга|видання=Зап. научн. сем. ЛОМИ|рік=1986|том=155|pages=3–6}}
{{Refend}}

== Посилання ==
* {{MathWorld|author=Weisstein, Eric W.|urlname=UnicyclicGraph|title=Одноцикловий граф}}
{{Бібліоінформація}}

[[Категорія:Дерева (теорія графів)]]
[[Категорія:Види графів]]
[[Категорія:Теорія матроїдів]]
[[Категорія:1963 у науці]]