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