Задача изоморфизма графов: различия между версиями

В общем случае, если цвета ребер обозначены целыми числами <math> \{ 1; 2... , 2^d - 1 \} \; </math>, имеются d уровней, и двоичное разложение каждого числа, обозначающего цвет, определяет, какие уровни содержат ребра. Вертикальные потоки (каждый из которых соответствует одной вершине исходного графа) могут связываться посредством путей либо клик. Если исходный граф имел n вершин и k цветов, новый граф будет иметь <math>O(n \; log \; k)</math> вершин. Это значение может быть улучшено до <math>O(n \sqrt {log k} ) \;</math> вершин в случае использования негоризонтальных ребер.