Псевдоліс

У теорії графів псевдолі́с — це неорієнтований граф, у якому будь-яка зв'язна компонента має не більше одного циклу. Тобто це система вершин і ребер, що з'єднують пари вершин, така, що жодні два цикли не мають спільних вершин і не можуть бути пов'язаними шляхом. Псевдоде́рево — це зв'язний псевдоліс.

1-ліс (максимальний псевдоліс), утворений трьома 1-деревами

Назви взято за аналогією із деревами та лісами (дерево — це зв'язний граф без циклів, ліс — незв'язне об'єднання дерев). Габов і Тарджан приписують вивчення псевдолісів Данцігу в книзі 1963 року з лінійного програмування, в якій псевдоліси з'являються в розв'язуванні деяких задач транспортних потоків. Псевдоліси також утворюють теоретичні графові моделі функцій і з'являються в деяких алгоритмічних задачах. Псевдоліси є розрідженими графами — вони мають дуже мале число ребер відносно вершин, і їхня структура матроїдів дозволяє деякі інші сімейства розріджених графів розкласти на об'єднання лісів і псевдолісів. Назва «псевдоліс» прийшла зі статті Пікара та Кейрана.

Визначення та структура

Визначимо неорієнтований граф як множину вершин і ребер, таких, що кожне ребро містить дві вершини (які, можливо, збігаються) як кінцеві точки. Тобто дозволено кратні ребра (ребра з тими ж кінцевими вершинами) і петлі (ребра, кінцеві вершини яких збігаються). Підграф графа ц е граф, утворений підмножиною вершин і ребер, такий, що будь-яке ребро в цій підмножині має кінцеві вершини в підмножині вершин. Зв'язна компонента неорієнтованого графа — це підграф, що складається з вершин і ребер, які можна досягти, рухаючись по ребрах, виходячи з однієї стартової вершини. Граф зв'язний, якщо будь-якої вершини або ребра можна досягти, рухаючись із будь-якої іншої вершини або ребра. Цикл у неорієнтованому графі — це зв'язний підграф, у якому будь-яка вершина має рівно два ребра або є петлею.

21 граф з одним циклом і максимум шістьма вершинами

Псевдоліс — це неорієнтований граф, у якому кожна зв'язна компонента містить максимум один цикл. Еквівалентно, це неорієнтований граф, у якому в кожній зв'язній компоненті ребер не більше, ніж вершин. Компоненти, що не мають циклів — це просто дерева, а компоненти, що мають єдиний цикл, називають 1-деревами або одноцикловими графами. Тобто 1-дерево — це зв'язний граф, що містить рівно один цикл. Псевдоліс із єдиною зв'язною компонентою (зазвичай званий псевдодеревом, хоча деякі автори визначають псевдодерево як 1-дерево) є або деревом, або 1-деревом. У загальному випадку псевдоліс може містити кілька зв'язних компонент, всі з яких є деревами або 1-деревами.

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

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

Орієнтовані псевдоліси

Версії цих визначень використовуються також для орієнтованих графів. Подібно до неорієнтованих графів орієнтовані графи складаються з вершин і ребер, але кожне ребро має напрямок (орієнтоване ребро зазвичай називають дугою). Орієнтований псевдоліс — це орієнтований граф, у якому кожна вершина має максимум одну вихідну дугу. Тобто граф має степінь виходу, що не перевищує одиниці. Орієнтований 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 псевдолісів.

Майже будь-який досить розріджений випадковий граф є псевдолісом. Тобто, якщо c — стала (0 < c < 1/2) і P_c(n) — ймовірність, що вибраний випадково серед графів з n вершинами і cn ребрами граф є псевдолісом, то P_c(n) прямує до одиниці в границі при зростанні n. Однак для c > 1/2 майже будь-який випадковий граф з cn ребрами має велику компоненту, яка не є одноцикловою.

Перерахування

Граф є простим, якщо в ньому немає петель і кратних ребер. Число простих 1-дерев з n позначеними вершинами дорівнює

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

Число максимальних орієнтованих псевдолісів із n вершинами, в яких дозволено петлі, дорівнює nⁿ, оскільки для будь-якої вершини є n можливих скінченних вершин вихідних дуг. Андре Жуаяль^[en] використав цей факт для бієктивного доведення формули Келі, що число неорієнтованих дерев на n вершинах дорівнює n^n − 2, шляхом знаходження біекції між максимальними орієнтованими псевдолісами і неорієнтованими деревами з двома різними вершинами. Якщо допускаються петлі, число максимальних орієнтованих псевдолісів дорівнює (n − 1)ⁿ.

Функціональні графи

Функція на множині {0,1,2,3,4,5,6,7,8} на себе та відповідний функціональний граф

Орієнтовані псевдоліси та відображення в собе в певному сенсі математично еквівалентні. Будь-яке відображення на множині X на себе (тобто ендоморфізм на X) можна інтерпретувати як визначення орієнтованого псевдолісу, який має дугу з x в y, коли ƒ(x) = y. Отриманий орієнтований псевдоліс максимальний і може включати петлі, якщо для деяких x ƒ(x) = x. Виключення петель призводить до немаксимальних псевдолісів. І навпаки, будь-який максимальний орієнтований псевдоліс визначає відображення ƒ, для якого ƒ(x) дорівнює кінцевій вершині дуги, що виходить з x і будь-який немаксимальний орієнтований псевдоліс можна зробити максимальним, додавши петлі і конвертувавши у функцію тим самим способом. Тому максимальні орієнтовані псевдоліси іноді називають функціональними графами. Подання функції як функціонального графа дає зручну мову опису властивостей, які непросто описати з погляду теорії функцій. Така техніка особливо корисна для задач, що використовують ітеровані функції^[en], які відповідають шляхам у теорії графів.

Пошук циклів, задача простежування шляхів у функціональному графі для знаходження в ньому циклу, застосовується в криптографії та обчислювальній теорії чисел як частина ро-алгоритму Поларда для факторизації цілих чисел і як метод знаходження конфліктів у криптографічних геш-функціях. У цих застосуваннях передбачається, що ƒ випадкова. Флажоле^[en] та Одлижко^[en] вивчали властивості функціональних графів, отриманих із випадкових відображень. Зокрема, з одного з варіантів парадоксу днів народження випливає, що у випадковому функціональному графі з n вершинами шлях, що починається з випадково вибраної вершини, зазвичай зациклюється після O(√n) кроків. Конягін^[ru] та ін. здійснили аналіз та обчислювальні статистичні дослідження.

Мартін, Одлижко і Вольфрам досліджували псевдоліси, що моделюють динаміку клітинних автоматів. Ці функціональні графи, які вони назвали діаграмами переходів станів, мають по одній вершині для кожної можливої конфігурації, в якій можуть перебувати комірки клітинного автомата, а дуги з'єднують кожну конфігурацію з конфігурацією, яка з неї отримується за правилами клітинного автомата. Зі структури цих діаграм можна отримати властивості автомата, такі як число компонентів, довжину скінченних циклів, глибину дерев, що з'єднують нескінченні стани цих циклів, або симетрії діаграми. Наприклад, будь-яка вершина без вхідної дуги відповідає едемському саду, а вершини з петлею відповідають натюрморту.

Інше раннє застосування функціональних графів — у ланцюжках, що використовуються для вивчення систем трійок Штейнера. Ланцюжок системи трійок — це функціональний граф, що містить по вершині кожної можливої трійки символів. Кожна трійка pqr відображається функцією в stu, де pqs, prt і qru — трійки, що належать системі трійок і містять пари pq, pr і qr відповідно. Показано, що, попри громіздкість обчислення, ланцюжки є потужним інваріантом системи трійок.

Біциклічний матроїд

Матроїд — це математична структура, в якій деякі множини елементів визначаються як незалежні, у тому сенсі, що незалежні множини задовольняють властивостям, які моделюють властивості лінійної незалежності у векторному просторі. Одним зі стандартних прикладів матроїдів є графовий матроїд^[en], у якому незалежні множини — це множини ребер у лісах графа. Матроїдна структура лісів важлива для алгоритмів обчислення мінімального кістякового дерева графа. Аналогічним можна визначити матроїди для псевдолісів.

Для будь-якого графа G = (V,E) можна визначити матроїд на ребрах графа G, в якому множина ребер незалежна тоді й лише тоді, коли ця множина утворює псевдоліс. Цей матроїд відомий як біциклічний матроїд^[en] графа G. Мінімальні залежні множини для цього матроїда — це мінімальні зв'язні підграфи графа G, що мають більше одного циклу, і ці підграфи іноді називаються біциклами. Існує три можливих типи біциклів — граф «тета», дві вершини якого, з'єднані трьома шляхами, які не мають внутрішніх спільних точок; «вісімка», що складається з двох циклів, які мають одну спільну вершину, і «наручники», утворені з двох циклів, що не мають спільних вершин, з'єднаних шляхом. Граф є псевдолісом тоді й лише тоді, коли він не містить біциклу як підграфа.

Заборонені мінори

«Метелик» (ліворуч) та «алмаз» (праворуч), заборонені мінори псевдолісів

Утворення мінору псевдолісу стягуванням деяких ребер та видаленням деяких інших ребер утворює новий псевдоліс. Таким чином, сімейство псевдолісів замкнуте за мінорами, а з теореми Робертсона — Сеймура тоді випливає, що псевдоліси можна описати в термінах скінченного набору заборонених мінорів, аналогічно теоремі Вагнера про опис планарних графів як графів, які не мають мінорами ні повного графа K₅, ні повного двочасткового графа K_3,3. Як обговорювалося раніше, будь-який граф, який не є псевдолісом, містить як підграф «наручники», «вісімку» або «тету». Будь-які «наручники» і «вісімки» можна стягнути до «метелика» («вісімка» з п'ятьма вершинами), а будь-яку «тету» можна стягнути до «алмазу» («тета» із чотирма вершинами), Так що будь-який граф, що не є псевдолісом, містить як мінор «метелика» або «алмаз», і тільки ці графи є мінімальними графами, що не належать до сімейства псевдолісів. Якщо заборонити лише «алмаз», але не «метелика», отримаємо ширше сімейство графів, що складається з «кактусів» та розрізненого об'єднання набору «кактусів».

Якщо розглядати мультиграфи з петлями, є лише один заборонений мінор — вершина з двома петлями.

Алгоритми

Раннє алгоритмічне застосування псевдолісів використовувало алгоритм мережевого симплекса та його застосування до узагальненої задачі про потоки в мережах для моделювання перетворень продуктів з одного типу в інший. У цих задачах задається транспортна мережа, де вершини моделюють кожен продукт, а ребра моделюють допустимість перетворення з одного продукту на інший. Кожне ребро маркується пропускною спроможністю (кількість продукту, яку можна перетворити за одиницю часу), потоком (швидкістю перетворення між продуктами) та ціною (скільки втрачаємо при перетворенні на одиницю продукту). Задача полягає у визначенні, скільки кожного продукту потрібно перетворити на кожній дузі транспортної мережі з метою мінімізувати ціну або максимізувати дохід, не порушуючи обмежень і не дозволяючи будь-якому типу продукту залишитися невикористаним. Цей тип задач можна сформулювати як задачу лінійного програмування та розв'язати за допомогою симплекс-методу. Проміжні розв'язки, одержувані з цього алгоритму, як і кінцевий оптимальний розв'язок, мають спеціальні структури — кожна дуга транспортної мережі або не використовується, або використовує максимальне значення пропускної спроможності, за винятком підмножини дуг, що утворюють кістяк псевдолісу транспортної мережі, і на цій підмножині дуг потік може набувати значення від нуля до максимальної пропускної здатності. У цьому застосуванні одноциклові графи іноді називають також доповненими деревами, а максимальні псевдоліси — доповненими лісами.

Завдання про мінімальний кістяковий псевдоліс використовує перебування кістякового псевдолісу мінімальної ваги у більшому графі G з вагами. Внаслідок матроїдної структури псевдолісів максимальні псевдоліса з мінімальною вагою можна знайти за допомогою жадібних алгоритмів подібно до задачі знаходження мінімального кістякового дерева. Однак Габов і Тарджан знайшли для цього випадку ефективніший підхід з лінійним часом.

Псевдодеревність графа G визначається за аналогією з деревністю як найменше число псевдолісів, на які можна розділити ребра. Еквівалентно, це найменше число k, таке, що граф G є (k, 0)-розрідженим, або найменше число k, таке що ребрам графа G можна задати напрямки, так що отриманий орієнтований граф матиме степінь результату, що не перевищує k. Внаслідок матроїдної структури псевдолісів псевдодеревність можна обчислити за поліноміальний час.

Випадковий двочастковий граф із n вершинами на кожній його частці з cn ребрами, вибраними випадково і незалежно для кожної пари n² можливих пар вершин з великою ймовірністю є псевдолісом за постійного c строго меншого від одиниці. Цей факт відіграє ключову роль в аналізі зозулиного гешування, структурі даних для пошуку пар ключ-значення переглядом однієї з двох геш-таблиць на місці, що визначається ключем, — можна сформувати «парний граф», вершини якого відповідають положенню в геш-таблицях, а ребра пов'язують два розташування, в яких один із ключів можна знайти. Парне гешування знаходить усі ключі тоді й лише тоді, коли парний граф є псевдолісом.

Псевдоліси відіграють також ключову роль у паралельних алгоритмах розфарбовування графів і пов'язаних задач.

Примітки

1. Розглянуті тут неорієнтовані графи є мультиграфами або псевдографами, а не простими графами.
2. Gabow, Tarjan, 1988.
3. Dantzig, 1963.
4. Picard, Queyranne, 1982.
5. Це визначення, наприклад, використовують Габов і Вестерман (Gabow, Westermann, (1992)).
6. Це визначення використовують Габов і Тарджан (Gabow, Tarjan, (1988)).
7. Див., наприклад, доведення леми 4 в статті Алвареза, Блеса і Серна (Àlvarez et al, (2002)).
8. Крускал, Рудольф і Снір (Kruskal et al, (1990)) замість цього використовують обернене визначення, в якому кожна вершина має вхідний степінь одиниця. Отримані графи, які вони називають одноцикловими, є транспонованими графами графів, розглянутих у цій статті.
9. Woodall, 1969.
10. Lovász et al, 1997.
11. Streinu, Theran, 2009.
12. Whiteley, 1988.
13. Болобаш (Bollobás, (1985)). Див., зокрема, наслідок 24, на стор.120, про межу числа вершин, що належать одноцикловим компонентам у випадковому графі, і наслідок 19, стор.113, про межу числа різних помічених одноциклових графів.
14. Riddell, (1951); див.  A057500 в Енциклопедії послідовностей цілих чисел.
15. Про метод бієктивного доведення можна почитати в статті Вершика (Вершик, (1986))
16. Aigner, Ziegler, 1998.
17. Flajolet, Odlyzko, 1990.
18. Konyagin et al, 2016.
19. Martin, Odlyzko, Wolfram, 1984.
20. В англійському варіанті — trains
21. White, 1913.
22. Colbourn, Colbourn, Rosenbaum, 1982.
23. Stinson, 1983.
24. Simoes-Pereira, 1972.
25. Matthews, 1977.
26. Glossary of Signed and Gain Graphs and Allied Areas. оригіналу за 3 березня 2016. Процитовано 23 жовтня 2016. 
27. Див. цю термінологію в списку малих графів( [Архівовано 18 листопада 2012 у Wikiwix]) на сайті Information System on Graph Class Inclusions( [ 5 лютого 2019 у Wayback Machine.]). Однак, назва метелик может стосуватися іншого сімейства графів, пов'язаних із гіперкубами.
28. El-Mallah, Colbourn, 1988.
29. Ahuja, Magnanti, Orlin, 1993.
30. Gabow, Westermann, (1992). Див. також швидкі схеми апроксимації Ковалика (Kowalik, (2006)).
31. Kutzelnigg, 2006.
32. Goldberg, Plotkin, Shannon, 1988.
33. Kruskal et al, 1990.

Література

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

Посилання

• Weisstein, Eric W. Одноцикловий граф(англ.) на сайті Wolfram MathWorld.