Здравствуйте.

Реализовал для курсовой 2 алгоритма:
1) http://rain.ifmo.ru/cat/data/theory/graph-...006/article.pdf (Гамма-алгоритм, использую для проверки на планарность).
2) Жадный алгоритм раскраски графа с оговоркой, что работает не с вершинами подряд, а обходит граф в ширину с помощью списков смежности.

Всё работает, но в курсовой еще нужно их сложность написать, так как всего 1 попытка будет на сдачу, боюсь, что ошибусь, может кто-то сможет определить сложность? Буду очень благодарен.

Также, если не трудно, на сколько понимаю, жадный алгоритм на списках смежности не является точным алгоритмом раскраски (не всегда раскрашивает в минимальное кол-во цветов), может кто-то может привести пример графа, когда он раскрасит не в минимальное кол-во? (Это не обязательно, но вдруг и с этим поможете..)

Заранее большое спасибо.

Небольшое гугление показывает, что асимптотика этого алгоритма O(n^3):

http://stackoverflow.com/questions/5652083...ph-on-the-plane
[...] there is one article in Russian, the algorithm named "Gamma algorithm" is descrbed there, but I want to find some more information, and I couldn't even find anything about "Gamma algorithm" (in English, it seems like it has another name), nor about other algorithm in English.
[...] I've stumbled across the algorithm i've been searching for — according to http://www.cs.brown.edu/~rt/gdhandbook/cha...s/planarity.pdf it is Auslander and Parter ,or Goldstein cycle-based algorithm.

http://mathworld.wolfram.com/PlanarGraph.html:
[...] Most are based on the  algorithm of Auslander and Parter (1961; Skiena 1990, p. 247).

Впрочем, за правильность не ручаюсь - т.к. читать статью на rain.ifmo.ru лень (особенно учитывая, что это чуть ли не единственное описание  "гамма-алгоритма" во всём интернете - и написанное некими студентами).



Обход в ширину работает за O(n+m), следовательно, жадный алгоритм (при правильной реализации) - имеет ту же асимптотику O(n+m).