Как проверить, является ли График Плоским Графиком или нет?
Для перефразирования то, что сказали другие: прием не находится в схема , это находится в запрос .
наивная схема Объектов/Маркировок/Тегов является правильным способом пойти. Но поскольку Вы видели, это не сразу понятно, как выполнить И запрос с большим количеством тегов.
лучший способ оптимизировать тот запрос будет зависим от платформы, таким образом, я рекомендовал бы повторно отметить Ваш вопрос с Вашим RDBS и изменить заголовок на что-то как "Оптимальный способ выполнить И запросить на базе данных меток".
я имею несколько предложений для SQL MS, но воздержусь в случае, если это не платформа, Вы используете.
4 ответа
Regarding planarity...
The well known e <= 3v - 6 criteria by Euller mentioned here says that if a graph is planar, then that condition must hold. However, not all graphs in which that condition holds are necessarily planar. That is why you actually need a planarity test algorithm.
A thing to notice is that planarity testing algorithms are not easy to implement. There's a very old one which is based on subgraphs finding and removal. I can't remember the original authors right now, but the problem with their algorithm is that it has O(n³) complexity.
The first planarity test algorithm considered to be efficient - O(n) in the case - is due to Hopcroft and Tarjan. This was already mentioned here in the post by Yin Zhu. You can find the original paper here.
This time, the problem with the algorithm was that many people found it too hard to understand and even to implement. So there are papers with the intention of just clarifying points of the original paper. For instance, the Kocay paper.
The Hopcraft-Tarjan paper is classic and if you want to try to implement it, the best reference I have is this other paper, which presents the theory together with a C++ implementation. That was written by the people who implemented the algorithm in the LEDA library.
Years later after the Hopcroft-Tarjan paper (which was in 1974), others O(n) algorithms were published. I don't know much about them, but some used PC/PQ trees. There is one, however, which I read and found very interesting. It's due to Boyer and Myrvold and it's from 2004. You can find it here. Besides the algorithm itself, of course, a good thing about this paper is that it provides a rigorous historical reference about planarity test algorithms.
Very recently, I discovered a another paper from 2008 in which Tarjan is one of the authors. Haven't checked it yet.
Well, if you got tired just by reading this post, I assume you don't want to implement your own algorithm. :) In this case, I can recommend some C++ libraries.
- Boost.
- GDToolkit.
- LEDA.
- OGDF.
- GTAD - This is my own graph library (which, unfortunately, I haven't been able to work on it lately). There's an implementation of the Hopcroft-Tarjan algorithm, which I wrote based on that paper I mentioned. Since the paper already provides real code, things are a lot easier.
Тестирование плоского неориентированного графа или нет - хорошо решено, и существуют эффективные алгоритмы. На самом деле это часть работы Р. Тарьяна по премии Тьюринга 1986 года.
Вы можете сначала проверить эту заметку. http://bkocay.cs.umanitoba.ca/G&G/articles/Planarity.pdf
Вы также можете проверить исходную статью Тарьяна и Хопкрафта: http://portal.acm.org/citation.cfm?id=321852
Я не знаю, произошли ли значительные улучшения в алгоритмах. Но алгоритм T&H уже очень быстр.
Между прочим, реализовать алгоритм очень сложно, и теорема на странице вики не дает вам подсказки по эффективной реализации (хотя и простой).
Ваш вопрос, похоже, охватывает две темы: - график плоский? (Ваш заголовок) - (если да?) как его раскрасить (сколько цветов не скажешь).
Для первой части В Википедии есть полезный раздел: http://en.wikipedia.org/wiki/Planar_graph
Вы должны прочитать его полностью, но он дает два простых требования для планарности:
Для простого связного планарного графа с v вершинами и e ребрами следуя простым критериям планарности выполнено:
Теорема 1. Если v ≥ 3, то e ≤ 3v - 6;
Теорема 2. Если v> 3 и нет циклов длины 3, то e ≤ 2v - 4.
Вам нужно будет создать структуру данных, способную удерживать вершины и ребра, и тогда вам нужно будет определить циклы длины 3 (треугольники).
Вы можете попробовать использовать Graphanalyzer ( http://grafoanalizator.unick-soft.ru/program/indexen.php ). Или отправьте вопрос автору программы.