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

Альтернативу представляет канонический алгоритм разметки. Его идея заключается в следующем: в каждом классе изоморфизмов имеется уникальный канонический граф, который может быть найден алгоритмом, получившим на входе любой граф класса изоморфизмов. Каноническим графом может быть, например, наименьший граф в классе изоморфизмов согласно какому-либо упорядочению (к примеру, лексикографическому). Практические алгоритмы обычно вычисляют каноническую форму с прицелом на эффективность, а не простоту описания.