4551
правка
Задача изоморфизма графов: различия между версиями
Материал из WEGA
Задача изоморфизма графов (посмотреть исходный код)
Версия от 13:33, 21 апреля 2015
, 21 апреля 2015→Применение
Irina (обсуждение | вклад) м (→Применение) |
Irina (обсуждение | вклад) м (→Применение) |
||
| Строка 51: | Строка 51: | ||
В общем случае, если цвета ребер обозначены целыми числами <math> \{ 1; 2... , 2^d - 1 \} \; </math>, имеются d уровней, и двоичное разложение каждого числа, обозначающего цвет, определяет, какие уровни содержат ребра. Вертикальные потоки (каждый из которых соответствует одной вершине исходного графа) могут связываться посредством путей либо клик. Если исходный граф имел n вершин и k цветов, новый граф будет иметь <math>O(n \; log \; k)</math> вершин. Это значение может быть улучшено до <math>O(n \sqrt {log k} ) \;</math> вершин в случае использования негоризонтальных ребер. | В общем случае, если цвета ребер обозначены целыми числами <math> \{ 1; 2,... , 2^d - 1 \} \; </math>, имеются d уровней, и двоичное разложение каждого числа, обозначающего цвет, определяет, какие уровни содержат ребра. Вертикальные потоки (каждый из которых соответствует одной вершине исходного графа) могут связываться посредством путей либо клик. Если исходный граф имел n вершин и k цветов, новый граф будет иметь <math>O(n \; log \; k)</math> вершин. Это значение может быть улучшено до <math>O(n \sqrt {log k} ) \;</math> вершин в случае использования негоризонтальных ребер. | ||
| Строка 60: | Строка 60: | ||
Изоморфизм гиперграфов и схем | Изоморфизм гиперграфов и схем | ||
Гиперграф похож на неориентированный граф, за исключением того, что ребра могут представлять собой множества вершин любой величины, а не только величины 2. Подобная структура также называется схемой. | [[Гиперграф]] похож на неориентированный граф, за исключением того, что ребра могут представлять собой множества вершин любой величины, а не только величины 2. Подобная структура также называется [[схема|схемой]]. | ||
В левой части рисунка 3 представлен гиперграф с пятью вершинами, двумя ребрами величины 2 и одним ребром величины 3. Справа представлен эквивалентный ему граф с раскрашенными вершинами. Вершины слева, раскрашенные в один цвет, представляют ребра гиперграфа; вершины справа, раскрашенные в другой цвет, представляют дуги гиперграфа. Ребра графа обозначают отношение инцидентности (включения) гиперграфа. | В левой части рисунка 3 представлен гиперграф с пятью вершинами, двумя ребрами величины 2 и одним ребром величины 3. Справа представлен эквивалентный ему граф с раскрашенными вершинами. Вершины слева, раскрашенные в один цвет, представляют ребра гиперграфа; вершины справа, раскрашенные в другой цвет, представляют дуги гиперграфа. Ребра графа обозначают отношение инцидентности (включения) гиперграфа. | ||
