Пусть d-некоторая натуральная константа. Обозначим через G_d класс всех связных графов, в которых степени вершин не превосхо-дят d. В этой статье строится полиномиальный алгоритм проверки изоморфизма для класса графов, которые обладают цепными раз-ложениями по расстоянию с одноэлементным корневым множеством и компонентами из класса G_d.
展开▼