Разметка графа
Материал из WEGA
Разметка графа (Graph labeling, Marking) - приписывание элементам графа так называемых меток (или пометок), в качестве которых обычно используются числа или слова. Разметка вершин --- функция, сопоставляющая пометки с вершинами графа, а разметка дуг --- с дугами графа. Граф называется помеченным, если он снабжен хотя бы одной из этих разметок. В отличие от нумерации вершин разметка может приписывать одну и ту же метку нескольким вершинам, разбивая их на классы одинаково помеченных.
См. также Раскраска, Задача анализа свойств состояний, Конечный автомат, Сеть Петри, Укладка.
Литература
[Евстигнеев/85],
[Касьянов/88],
[Евстигнеев-Касьянов/94]