Разметка графа

Разметка графа (Graph labeling, Marking) - приписывание элементам графа так называемых меток (или пометок), в качестве которых обычно используются числа или слова. Разметка вершин --- функция, сопоставляющая пометки с вершинами графа, а разметка дуг --- с дугами графа. Граф называется помеченным, если он снабжен хотя бы одной из этих разметок. В отличие от нумерации вершин разметка может приписывать одну и ту же метку нескольким вершинам, разбивая их на классы одинаково помеченных.

См. также Раскраска, Задача анализа свойств состояний, Конечный автомат, Сеть Петри, Укладка.

Литература

[Евстигнеев/85],

[Касьянов/88],

[Евстигнеев-Касьянов/94]