4551
правка
Задача изоморфизма графов: различия между версиями
Перейти к навигации
Перейти к поиску
Задача изоморфизма графов (посмотреть исходный код)
Версия от 13:29, 21 апреля 2015
, 21 апреля 2015→Применение
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 54: | Строка 54: | ||
[[Файл:Graph_Isom_2.jpg]] | |||
Рис. 2. Изоморфизм графов с раскрашенными ребрами | |||
Изоморфизм графов с раскрашенными ребрами | |||
| Строка 68: | Строка 64: | ||
В левой части рисунка 3 представлен гиперграф с пятью вершинами, двумя ребрами величины 2 и одним ребром величины 3. Справа представлен эквивалентный ему граф с раскрашенными вершинами. Вершины слева, раскрашенные в один цвет, представляют ребра гиперграфа; вершины справа, раскрашенные в другой цвет, представляют дуги гиперграфа. Ребра графа обозначают отношение инцидентности (включения) гиперграфа. | В левой части рисунка 3 представлен гиперграф с пятью вершинами, двумя ребрами величины 2 и одним ребром величины 3. Справа представлен эквивалентный ему граф с раскрашенными вершинами. Вершины слева, раскрашенные в один цвет, представляют ребра гиперграфа; вершины справа, раскрашенные в другой цвет, представляют дуги гиперграфа. Ребра графа обозначают отношение инцидентности (включения) гиперграфа. | ||
[[Файл:Graph_Isom_3.jpg]] | |||
Рис. 3. Изоморфизм гиперграфов/схем как изоморфизм графов | |||
Матрица инцидентности ребер и вершин изображена в центральной части рисунка. Ею может быть любая бинарная матрица, позволяющая корректно отобразить тот факт, что рассматриваемая задача заключается в определении эквивалентности матриц (0, 1) при независимой перестановке строк и столбцов. Сочетая эту идею с предыдущей конструкцией, можно поддерживать подобное отношение эквивалентности на множестве матриц с произвольными значениями. | Матрица инцидентности ребер и вершин изображена в центральной части рисунка. Ею может быть любая бинарная матрица, позволяющая корректно отобразить тот факт, что рассматриваемая задача заключается в определении эквивалентности матриц (0, 1) при независимой перестановке строк и столбцов. Сочетая эту идею с предыдущей конструкцией, можно поддерживать подобное отношение эквивалентности на множестве матриц с произвольными значениями. | ||
== Другие примеры == | == Другие примеры == | ||