Разметка графа: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Разметка графа''' (''Graph labeling, Marking'') - приписывание элементам графа так назы...)
(нет различий)

Версия от 14:10, 14 января 2010

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

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

Литература

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

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

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