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

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Разметка графа''' (''Graph labeling, Marking'') - приписывание элементам графа так назы...)
 
Нет описания правки
Строка 1: Строка 1:
'''Разметка графа''' (''Graph labeling, Marking'') -  
'''Разметка графа''' (''[[Graph labeling]], [[Marking]]'') -  
приписывание
приписывание
элементам графа так называемых ''меток'' (или ''пометок''), в
элементам графа так называемых ''[[метка|меток]]'' (или ''[[пометка|пометок]]''), в
качестве которых обычно используются числа или
качестве которых обычно используются числа или
слова.
слова.
''Разметка вершин'' --- функция,
''[[Разметка вершин]]'' --- функция,
сопоставляющая пометки с вершинами графа, а ''разметка дуг'' ---
сопоставляющая пометки с [[вершина|вершинами]] [[граф|графа]], а ''[[разметка дуг]]'' ---
с дугами графа.
с [[дуга|дугами]] графа.
Граф называется помеченным, если он снабжен хотя бы одной из
Граф называется помеченным, если он снабжен хотя бы одной из
этих разметок.
этих разметок.
В отличие от ''нумерации'' вершин разметка
В отличие от [[нумерация вершин|''нумерации'' вершин]] разметка
может приписывать
может приписывать
одну и ту же метку нескольким вершинам, разбивая их на
одну и ту же метку нескольким вершинам, разбивая их на
классы одинаково помеченных.
классы одинаково помеченных.


См. также ''Раскраска, Задача анализа свойств состояний, Конечный автомат, Сеть Петри, Укладка''.
==См. также==
''[[Раскраска]], [[Задача анализа свойств состояний]], [[Конечный автомат]], [[Сеть Петри]], [[Укладка]]''.
==Литература==
==Литература==
[Евстигнеев/85],
[Евстигнеев/85],

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

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

См. также

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

Литература

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

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

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