Графы с атрибутами

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

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