Сопоставление (теория графов)

В математической дисциплине теории графов в совпадающее или независимое множество ребер неориентированном графе представляет собой множество ребер без общих вершин . ^[1]Другими словами, подмножество ребер является паросочетанием, если каждая вершина встречается не более чем в одном ребре этого паросочетания. Поиск соответствия в двудольном графе можно рассматривать как задачу сетевого потока .

Определения [ править ]

Для данного графа $G = (V, E)$ паросочетание представляет собой M в G набор попарно несмежных ребер, ни одно из которых не является петлей ; то есть никакие два ребра не имеют общих вершин.

Вершина считается сопоставленной (или насыщенной ), если она является конечной точкой одного из ребер сопоставления. В противном случае вершина несовпадающая (или ненасыщенная ).

Максимальное паросочетание — это паросочетание M графа G , которое не является подмножеством какого-либо другого паросочетания. Паросочетание M графа G является максимальным, если каждое ребро в G имеет непустое пересечение хотя бы с одним ребром из M . На следующем рисунке показаны примеры максимальных паросочетаний (красные) в трех графах.

( Максимальное сопоставление также известное как сопоставление максимальной мощности) ^[2]) — паросочетание, содержащее максимально возможное количество ребер. Максимальных совпадений может быть много. Соответствующий номер $\nu (G)$ графа $G$ — размер максимального паросочетания. Каждое максимальное паросочетание является максимальным, но не каждое максимальное паросочетание является максимальным паросочетанием. На следующем рисунке показаны примеры максимальных совпадений на тех же трех графах.

Идеальное паросочетание — это паросочетание, которому соответствуют все вершины графа. То есть паросочетание является совершенным, если каждая вершина графа инцидентна ребру паросочетания. Соответствие является идеальным, если $|M|=|V|/2$ . Каждое совершенное паросочетание является максимальным и, следовательно, максимальным. термин полное совпадение В некоторой литературе используется . На приведенном выше рисунке только часть (b) показывает идеальное совпадение. Идеально сочетается также боковая крышка минимального размера . Таким образом, размер максимального паросочетания не больше размера минимального реберного покрытия: $\nu (G)\leq \rho (G)$ . Граф может содержать идеальное паросочетание только в том случае, если в графе четное число вершин.

Почти идеальное совпадение — это совпадение, при котором ровно одна вершина не совпадает. Очевидно, что граф может содержать почти идеальное паросочетание только в том случае, если граф имеет нечетное число вершин, а почти идеальные паросочетания являются максимальными паросочетаниями. На рисунке выше часть (c) показывает почти идеальное совпадение. Если каждой вершине не соответствует какое-то почти идеальное сопоставление, то граф называется факторно-критическим .

Учитывая совпадение M , альтернативный путь — это путь, который начинается с несовпадающей вершины. ^[3]и чьи ребра принадлежат поочередно паросочетанию, а не паросочетанию. Дополняющий путь — это альтернативный путь, который начинается и заканчивается в свободных (несовпадающих) вершинах. Лемма Бержа утверждает, что паросочетание M является максимальным тогда и только тогда, когда не существует расширяющего пути относительно M .

— Индуцированное паросочетание это паросочетание, которое является множеством ребер индуцированного подграфа . ^[4]

Свойства [ править ]

В любом графе без изолированных вершин сумма числа совпадений и числа покрытия ребер равна количеству вершин. ^[5]Если существует идеальное совпадение, то и номер совпадения, и номер покрытия края равны $| В | / 2$ .

Если $A$ и $B$ — два максимальных паросочетания, то $| А | \leq 2| Б |$ и $| Б | \leq 2| А |$ . Чтобы убедиться в этом, заметим, что каждое ребро в $B \ A$ может быть смежным не более чем с двумя рёбрами в $A \ B$ , поскольку $A$ — паросочетание; при этом каждое ребро в $A \ B$ смежно с ребром в $B \ A$ по максимальности $B$ , следовательно,

|A\setminus B|\leq 2|B\setminus A|.

Далее мы делаем вывод, что

|A|=|A\cap B|+|A\setminus B|\leq 2|B\cap A|+2|B\setminus A|=2|B|.

В частности, это показывает, что любое максимальное паросочетание является 2-приближением максимального паросочетания, а также 2-приближением минимального максимального паросочетания. Это неравенство строгое: например, если $G$ — путь с 3 ребрами и 4 вершинами, размер минимального максимального паросочетания равен 1, а размер максимального паросочетания равен 2.

Спектральная характеристика числа согласования графа дана Хассани Монфаредом и Малликом следующим образом: Пусть $G$ быть графиком на $n$ вершины и $\lambda _{1}>\lambda _{2}>\ldots >\lambda _{k}>0$ быть $k$ отдельные ненулевые чисто мнимые числа , где $2k\leq n$ . Тогда соответствующее число $G$ является $k$ тогда и только тогда, когда (а) существует действительная кососимметричная матрица $A$ с графиком $G$ и собственные значения $\pm \lambda _{1},\pm \lambda _{2},\ldots ,\pm \lambda _{k}$ и $n-2k$ нули и (б) все вещественные кососимметричные матрицы с графиком $G$ иметь максимум $2k$ ненулевые собственные значения . ^[6] Обратите внимание, что (простой) график вещественной симметричной или кососимметричной матрицы $A$ порядка $n$ имеет $n$ вершины и ребра, заданные ненулевыми недиагональными элементами $A$ .

Соответствующие полиномы [ править ]

Производящая функция количества паросочетаний k -ребер в графе называется согласующим полиномом. Пусть G — граф, а m _k — количество паросочетаний k -ребер. Один совпадающий полином G — это

\sum _{k\geq 0}m_{k}x^{k}.

Другое определение дает соответствующий полином как

\sum _{k\geq 0}(-1)^{k}m_{k}x^{n-2k},

где n — количество вершин в графе. Каждый тип имеет свое применение; дополнительную информацию см. в статье о сопоставлении полиномов.

Алгоритмы и вычислительная сложность [ править ]

Сопоставление по максимальной мощности [ править ]

Фундаментальной проблемой комбинаторной оптимизации является поиск максимального паросочетания . Эта задача имеет разные алгоритмы для разных классов графов.

В невзвешенном двудольном графе задача оптимизации состоит в нахождении соответствия максимальной мощности . Задача решается алгоритмом Хопкрофта-Карпа за время $O (\sqrtVE . плоские)$ времени, и существуют более эффективные рандомизированные алгоритмы , алгоритмы аппроксимации и алгоритмы для специальных классов графов, таких как двудольные графы , как описано в основной статье .

Соответствие максимального веса [ править ]

Во взвешенном двудольном графе задача оптимизации состоит в том, чтобы найти паросочетание с максимальным весом; двойная задача — найти паросочетание с минимальным весом. Эту проблему часто называют максимальным взвешенным двусторонним сопоставлением или проблемой назначения . Венгерский алгоритм решает задачу назначения и положил начало алгоритмам комбинаторной оптимизации. Он использует модифицированный поиск кратчайшего пути в алгоритме увеличения пути. Если алгоритм Беллмана-Форда , время работы венгерского алгоритма становится на этом этапе используется $O(V^{2}E)$ или стоимость края может быть смещена с возможностью достижения $O(V^{2}\log {V}+VE)$ время работы с алгоритмом Дейкстры и кучей Фибоначчи . ^[7]

В недвудольном взвешенном графе задача сопоставления максимального веса может быть решена за время $O(V^{2}E)$ используя алгоритм цветения Эдмондса .

Максимальные совпадения [ править ]

Максимальное соответствие можно найти с помощью простого жадного алгоритма . Максимальное паросочетание также является максимальным паросочетанием, и, следовательно, можно найти наибольшее максимальное паросочетание за полиномиальное время. Однако не известен ни один алгоритм с полиномиальным временем для поиска минимального максимального паросочетания , то есть максимального паросочетания, содержащего наименьшее возможное количество ребер.

Максимальное паросочетание с k ребрами — это множество с доминирующими ребрами, состоящее из k ребер. И наоборот, если нам задан минимальный набор доминирующих ребер с k ребрами, мы можем построить максимальное паросочетание с k ребрами за полиномиальное время. Следовательно, задача нахождения минимального максимального паросочетания по существу равна проблеме нахождения минимального доминирующего множества ребер. ^[8]Обе эти две задачи оптимизации известны как NP-трудные ; варианты решения этих задач являются классическими примерами NP-полных задач. ^[9] Обе задачи можно аппроксимировать с коэффициентом 2 за полиномиальное время: просто найдите произвольное максимальное паросочетание M . ^[10]

Задачи со счетом [ править ]

Количество паросочетаний в графе известно как индекс Хосоя графа. , даже для двудольных графов. #P-полно Вычислить эту величину ^[11]Подсчет идеальных паросочетаний также является #P-полным , даже в двудольных графах , поскольку вычисление перманента произвольной матрицы 0–1 (еще одна #P-полная задача) — это то же самое, что вычисление количества идеальных паросочетаний в двудольном графе. имея данную матрицу в качестве матрицы двусмежности . Однако существует полностью полиномиальная рандомизированная по времени аппроксимационная схема для подсчета количества двудольных паросочетаний. ^[12] Замечательная теорема Кастелейна утверждает, что количество идеальных паросочетаний в плоском графе можно вычислить точно за полиномиальное время с помощью алгоритма FKT .

Количество идеальных паросочетаний в полном графе K _n (с четным n ) определяется двойным факториалом ( n − 1)!!. ^[13] Количество паросочетаний в полных графах, без ограничения на идеальность паросочетаний, задается телефонными номерами . ^[14]

Число идеальных паросочетаний в графе также известно как гафниан его матрицы смежности .

Нахождение всех максимально совпадающих ребер [ править ]

Одна из основных задач теории паросочетания — найти в заданном графе все ребра, которые можно расширить до максимального паросочетания в графе (такие ребра называются максимально сопоставляемыми ребрами или разрешенными ребрами). Алгоритмы решения этой задачи включают в себя:

Для общих графов детерминированный алгоритм по времени $O(VE)$ и рандомизированный алгоритм по времени ${\tilde {O}}(V^{2.376})$ . ^[15]^[16]
Для двудольных графов, если найдено одно максимальное совпадение, детерминированный алгоритм выполняется во времени. $O(V+E)$ . ^[17]

Двустороннее сопоставление онлайн [ править ]

Проблема разработки онлайн-алгоритма сопоставления была впервые рассмотрена Ричардом М. Карпом , Умешем Вазирани и Виджаем Вазирани в 1990 году. ^[18]

В онлайн-режиме узлы на одной стороне двудольного графа поступают по одному и должны быть либо немедленно сопоставлены с другой стороной графа, либо отброшены. Это естественное обобщение задачи о секретаре , которое можно применить к онлайн-аукционам рекламы. Лучший онлайн-алгоритм для случая невзвешенной максимизации с моделью случайного поступления достигает конкурентоспособности 0,696 $коэффициента$ . ^[19]

Характеристики [ править ]

Теорема Кенига утверждает, что в двудольных графах максимальное паросочетание равно размеру минимального вершинного покрытия . Благодаря этому результату задачи о минимальном покрытии вершин, максимальном независимом множестве и биклике максимальных вершин могут быть решены за полиномиальное время для двудольных графов.

Теорема Холла о браке дает характеристику двудольных графов, имеющих идеальное паросочетание, а теорема Тутта дает характеристику произвольных графов.

Приложения [ править ]

Соответствие в общих графиках [ править ]

Структура Кекуле ароматического соединения представляет собой идеальное совпадение его углеродного скелета , показывающее расположение двойных связей в химической структуре . Эти структуры названы в честь Фридриха Августа Кекуле фон Страдоница , который показал, что бензолу (в терминах теории графов, 6-вершинному циклу) может быть придана такая структура. ^[20]
Индекс Хосоя — это количество непустых совпадений плюс одно; он используется в вычислительной химии и исследованиях математической химии органических соединений.
Задача китайского почтальона включает в себя поиск идеального соответствия минимального веса в качестве подзадачи.

Сопоставление в двудольных графах [ править ]

Задача выпуска заключается в выборе минимального набора классов из заданных требований для окончания обучения.
Транспортная задача Хичкока включает в себя двустороннее сопоставление в качестве подзадачи.
Проблема изоморфизма поддеревьев включает в себя двустороннее сопоставление как подзадачу.

См. также [ править ]

Сопоставление в гиперграфах — обобщение сопоставления в графах.
Дробное соответствие .
Разложение Дулмаджа – Мендельсона — разбиение вершин двудольного графа на подмножества, при котором каждое ребро принадлежит идеальному паросочетанию тогда и только тогда, когда его конечные точки принадлежат одному и тому же подмножеству.
Раскраска ребер — разбиение ребер графа на паросочетания.
Преключение совпадения — минимальное количество ребер, которое нужно удалить, чтобы предотвратить существование идеального совпадения.
Радужное сопоставление , сопоставление в двудольном графе с раскрашенными ребрами без повторяющихся цветов.
Кососимметричный граф — тип графа, который можно использовать для моделирования поиска альтернативных путей для совпадений.
Стабильное соответствие — соответствие, при котором никакие два элемента не предпочитают друг друга своим совпадающим партнерам.
Независимый набор вершин — набор вершин (а не ребер), ни одна из которых не является смежной.
Проблема стабильного брака (также известная как проблема стабильного соответствия)

Ссылки [ править ]

^ "is_matching" . Документация NetworkX 2.8.2 . Проверено 31 мая 2022 г. Каждый узел инцидентен не более чем одному ребру сопоставления. Говорят, что ребра независимы.
^ Алан Гиббонс, Алгоритмическая теория графов, издательство Кембриджского университета, 1985, Глава 5.
^ «Предварительный просмотр» .
^ Кэмерон, Кэти (1989), «Индуцированные сопоставления», специальный выпуск Первой Монреальской конференции по комбинаторике и информатике, 1987, Дискретная прикладная математика , 24 (1–3): 97–102, doi : 10.1016/0166-218X(92) )90275-Ф , МР 1011265
^ Галлай, Тибор (1959), «О наборах крайних точек и ребер», Ann. Университет наук. Будапешт. Секта Этвёша. Математика , 2 : 133–138 .
^ Кейван Хассани Монфаред и Судипта Маллик, Теорема 3.6, Спектральная характеристика паросочетаний в графах, Линейная алгебра и ее приложения 496 (2016) 407–419, https://doi.org/10.1016/j.laa.2016.02.004 , https ://arxiv.org/abs/1602.03590
^ Фредман, Майкл Л.; Тарьян, Роберт Эндре (1987), «Кучи Фибоначчи и их использование в улучшенных алгоритмах сетевой оптимизации», Journal of the ACM , 34 (3): 596–615, doi : 10.1145/28869.28874 , S2CID 7904683
^ Яннакакис, Михалис; Гаврил, Фаника (1980), «Множества с доминирующими краями в графах» (PDF) , SIAM Journal on Applied Mathematics , 38 (3): 364–372, doi : 10.1137/0138030 .
^ Гэри, Майкл Р .; Джонсон, Дэвид С. (1979), Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты , WH Freeman, ISBN 0-7167-1045-5 . Множество с доминирующим ребром (версия решения) обсуждается в рамках проблемы доминирующего множества, которая представляет собой проблему GT2 в Приложении A1.1. Минимально-максимальное сопоставление (вариант решения) — это задача GT10 в Приложении A1.1.
^ Аузиелло, Джорджо; Крещенци, Пьерлуиджи; Гамбози, Джорджио; Канн, Вигго; Маркетти-Спаккамела, Альберто; Протаси, Марко (2003), Сложность и аппроксимация: задачи комбинаторной оптимизации и их свойства аппроксимации , Springer . Минимальный набор доминирующих ребер (версия оптимизации) — это задача GT3 в Приложении B (стр. 370). Минимальное максимальное соответствие (версия оптимизации) — это задача GT10 в Приложении B (стр. 374). См. также «Минимальный набор доминирующих ребер» и «Минимальное максимальное соответствие» в веб-справочнике .
^ Лесли Валиант , Сложность проблем перечисления и надежности , SIAM J. Comput., 8 (3), 410–421
^ Безакова, Ивона; Штефанкович, Даниэль; Вазирани, Виджай В .; Вигода, Эрик (2008). «Ускорение моделирования отжига для решения постоянных и комбинаторных задач счета». SIAM Journal по вычислительной технике . 37 (5): 1429–1454. CiteSeerX 10.1.1.80.687 . дои : 10.1137/050644033 . S2CID 755231 .
^ Каллан, Дэвид (2009), Комбинаторный обзор тождеств для двойного факториала , arXiv : 0906.1317 , Bibcode : 2009arXiv0906.1317C .
^ Тичи, Роберт Ф.; Вагнер, Стефан (2005), «Экстремальные задачи для топологических индексов в комбинаторной химии» (PDF) , Journal of Computational Biology , 12 (7): 1004–1013, doi : 10.1089/cmb.2005.12.1004 , PMID 16201918 .
^ Рабин, Майкл О.; Вазирани, Виджай В. (1989), «Максимальные совпадения в общих графах посредством рандомизации», Journal of Algorithms , 10 (4): 557–567, CiteSeerX 10.1.1.228.1996 , doi : 10.1016/0196-6774(89)90005 -9
^ Чериян, Джозеф (1997), «Рандомизированный ${\widetilde {O}}(M(|V|))$ алгоритмы для задач теории сопоставления», SIAM Journal on Computing , 26 (6): 1635–1655, doi : 10.1137/S0097539793256223
^ Тасса, Тамир (2012), «Нахождение всех максимально совпадающих ребер в двудольном графе», Theoretical Computer Science , 423 : 50–58, doi : 10.1016/j.tcs.2011.12.071
^ Карп, Ричард М .; Вазирани, Умеш В. ; Вазирани, Виджай В. (1990). «Оптимальный алгоритм двустороннего сопоставления в режиме онлайн» (PDF) . Материалы 22-го ежегодного симпозиума ACM по теории вычислений (STOC, 1990) . стр. 352–358. дои : 10.1145/100216.100262 . ISBN 0-89791-361-2 .
^ Махдиан, Мохаммед; Ян, Цици (2011). «Двустороннее онлайн-сопоставление со случайными поступлениями: подход, основанный на сильно выявляющих факторах ЛП». Труды сорок третьего ежегодного симпозиума ACM по теории вычислений . стр. 597–606. дои : 10.1145/1993636.1993716 .
^ См., например, Тринайстич, Ненад ; Кляйн, Дуглас Дж.; Рандич, Милан (1986), «О некоторых решенных и нерешенных проблемах химической теории графов», International Journal of Quantum Chemistry , 30 (S20): 699–742, doi : 10.1002/qua.560300762 .

Дальнейшее чтение [ править ]

Ловас, Ласло ; Пламмер, доктор медицинских наук (1986), Теория соответствия , Анналы дискретной математики, том. 29, Северная Голландия, ISBN 0-444-87916-1 МР 0859549
Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Стейн (2001), Введение в алгоритмы (второе изд.), MIT Press и McGraw – Hill, глава 26, стр. 643–700, ISBN 0-262-53196-8 {{citation}}: CS1 maint: несколько имен: список авторов ( ссылка )
Андраш Франк (2004). О венгерском методе Куна – дань уважения Венгрии (PDF) (Технический отчет). Исследовательская группа Эгервари.
Майкл Л. Фредман и Роберт Э. Тарьян (1987), «Кучи Фибоначчи и их использование в улучшенных алгоритмах сетевой оптимизации», Journal of the ACM , 34 (3): 595–615, doi : 10.1145/28869.28874 , S2CID 7904683 .
С. Дж. Сайвин и Иван Гутман (1988), Структуры Кекуле в бензоидных углеводородах , Springer-Verlag
Марек Карпински и Войцех Риттер (1998), Быстрые параллельные алгоритмы для задач сопоставления графов , Oxford University Press, ISBN 978-0-19-850162-6

Внешние ссылки [ править ]

Библиотека графов с реализацией сопоставления максимальной мощности на основе Хопкрофта-Карпа и Push-Relabel.

[NetworkX_2.8.2_documentation-1] "is_matching" . Документация NetworkX 2.8.2 . Проверено 31 мая 2022 г. Каждый узел инцидентен не более чем одному ребру сопоставления. Говорят, что ребра независимы.

[2] Алан Гиббонс, Алгоритмическая теория графов, издательство Кембриджского университета, 1985, Глава 5.

[3] «Предварительный просмотр» .

[4] Кэмерон, Кэти (1989), «Индуцированные сопоставления», специальный выпуск Первой Монреальской конференции по комбинаторике и информатике, 1987, Дискретная прикладная математика , 24 (1–3): 97–102, doi : 10.1016/0166-218X(92) )90275-Ф , МР 1011265

[5] Галлай, Тибор (1959), «О наборах крайних точек и ребер», Ann. Университет наук. Будапешт. Секта Этвёша. Математика , 2 : 133–138 .

[6] Кейван Хассани Монфаред и Судипта Маллик, Теорема 3.6, Спектральная характеристика паросочетаний в графах, Линейная алгебра и ее приложения 496 (2016) 407–419, https://doi.org/10.1016/j.laa.2016.02.004 , https ://arxiv.org/abs/1602.03590

[Fredman87-7] Фредман, Майкл Л.; Тарьян, Роберт Эндре (1987), «Кучи Фибоначчи и их использование в улучшенных алгоритмах сетевой оптимизации», Journal of the ACM , 34 (3): 596–615, doi : 10.1145/28869.28874 , S2CID 7904683

[8] Яннакакис, Михалис; Гаврил, Фаника (1980), «Множества с доминирующими краями в графах» (PDF) , SIAM Journal on Applied Mathematics , 38 (3): 364–372, doi : 10.1137/0138030 .

[9] Гэри, Майкл Р .; Джонсон, Дэвид С. (1979), Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты , WH Freeman, ISBN 0-7167-1045-5 . Множество с доминирующим ребром (версия решения) обсуждается в рамках проблемы доминирующего множества, которая представляет собой проблему GT2 в Приложении A1.1. Минимально-максимальное сопоставление (вариант решения) — это задача GT10 в Приложении A1.1.

[10] Аузиелло, Джорджо; Крещенци, Пьерлуиджи; Гамбози, Джорджио; Канн, Вигго; Маркетти-Спаккамела, Альберто; Протаси, Марко (2003), Сложность и аппроксимация: задачи комбинаторной оптимизации и их свойства аппроксимации , Springer . Минимальный набор доминирующих ребер (версия оптимизации) — это задача GT3 в Приложении B (стр. 370). Минимальное максимальное соответствие (версия оптимизации) — это задача GT10 в Приложении B (стр. 374). См. также «Минимальный набор доминирующих ребер» и «Минимальное максимальное соответствие» в веб-справочнике .

[11] Лесли Валиант , Сложность проблем перечисления и надежности , SIAM J. Comput., 8 (3), 410–421

[12] Безакова, Ивона; Штефанкович, Даниэль; Вазирани, Виджай В .; Вигода, Эрик (2008). «Ускорение моделирования отжига для решения постоянных и комбинаторных задач счета». SIAM Journal по вычислительной технике . 37 (5): 1429–1454. CiteSeerX 10.1.1.80.687 . дои : 10.1137/050644033 . S2CID 755231 .

[13] Каллан, Дэвид (2009), Комбинаторный обзор тождеств для двойного факториала , arXiv : 0906.1317 , Bibcode : 2009arXiv0906.1317C .

[14] Тичи, Роберт Ф.; Вагнер, Стефан (2005), «Экстремальные задачи для топологических индексов в комбинаторной химии» (PDF) , Journal of Computational Biology , 12 (7): 1004–1013, doi : 10.1089/cmb.2005.12.1004 , PMID 16201918 .

[15] Рабин, Майкл О.; Вазирани, Виджай В. (1989), «Максимальные совпадения в общих графах посредством рандомизации», Journal of Algorithms , 10 (4): 557–567, CiteSeerX 10.1.1.228.1996 , doi : 10.1016/0196-6774(89)90005 -9

[16] Чериян, Джозеф (1997), «Рандомизированный ${\widetilde {O}}(M(|V|))$ алгоритмы для задач теории сопоставления», SIAM Journal on Computing , 26 (6): 1635–1655, doi : 10.1137/S0097539793256223

[17] Тасса, Тамир (2012), «Нахождение всех максимально совпадающих ребер в двудольном графе», Theoretical Computer Science , 423 : 50–58, doi : 10.1016/j.tcs.2011.12.071

[18] Карп, Ричард М .; Вазирани, Умеш В. ; Вазирани, Виджай В. (1990). «Оптимальный алгоритм двустороннего сопоставления в режиме онлайн» (PDF) . Материалы 22-го ежегодного симпозиума ACM по теории вычислений (STOC, 1990) . стр. 352–358. дои : 10.1145/100216.100262 . ISBN 0-89791-361-2 .

[19] Махдиан, Мохаммед; Ян, Цици (2011). «Двустороннее онлайн-сопоставление со случайными поступлениями: подход, основанный на сильно выявляющих факторах ЛП». Труды сорок третьего ежегодного симпозиума ACM по теории вычислений . стр. 597–606. дои : 10.1145/1993636.1993716 .

[20] См., например, Тринайстич, Ненад ; Кляйн, Дуглас Дж.; Рандич, Милан (1986), «О некоторых решенных и нерешенных проблемах химической теории графов», International Journal of Quantum Chemistry , 30 (S20): 699–742, doi : 10.1002/qua.560300762 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]