Разметка графа: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Создана новая страница размером '''Разметка графа''' (''Graph labeling, Marking'') - приписывание элементам графа так назы...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Разметка графа''' (''Graph labeling, Marking'') - | '''Разметка графа''' (''[[Graph labeling]], [[Marking]]'') - | ||
приписывание | приписывание | ||
элементам графа так называемых ''меток'' (или ''пометок''), в | элементам графа так называемых ''[[метка|меток]]'' (или ''[[пометка|пометок]]''), в | ||
качестве которых обычно используются числа или | качестве которых обычно используются числа или | ||
слова. | слова. | ||
''Разметка вершин'' --- функция, | ''[[Разметка вершин]]'' --- функция, | ||
сопоставляющая пометки с вершинами графа, а ''разметка дуг'' --- | сопоставляющая пометки с [[вершина|вершинами]] [[граф|графа]], а ''[[разметка дуг]]'' --- | ||
с дугами графа. | с [[дуга|дугами]] графа. | ||
Граф называется помеченным, если он снабжен хотя бы одной из | Граф называется помеченным, если он снабжен хотя бы одной из | ||
этих разметок. | этих разметок. | ||
В отличие от ''нумерации'' вершин разметка | В отличие от [[нумерация вершин|''нумерации'' вершин]] разметка | ||
может приписывать | может приписывать | ||
одну и ту же метку нескольким вершинам, разбивая их на | одну и ту же метку нескольким вершинам, разбивая их на | ||
классы одинаково помеченных. | классы одинаково помеченных. | ||
См. также ''Раскраска, Задача анализа свойств состояний, Конечный автомат, Сеть Петри, Укладка''. | ==См. также== | ||
''[[Раскраска]], [[Задача анализа свойств состояний]], [[Конечный автомат]], [[Сеть Петри]], [[Укладка]]''. | |||
==Литература== | ==Литература== | ||
[Евстигнеев/85], | [Евстигнеев/85], | ||
Версия от 14:13, 15 января 2010
Разметка графа (Graph labeling, Marking) - приписывание элементам графа так называемых меток (или пометок), в качестве которых обычно используются числа или слова. Разметка вершин --- функция, сопоставляющая пометки с вершинами графа, а разметка дуг --- с дугами графа. Граф называется помеченным, если он снабжен хотя бы одной из этих разметок. В отличие от нумерации вершин разметка может приписывать одну и ту же метку нескольким вершинам, разбивая их на классы одинаково помеченных.
См. также
Раскраска, Задача анализа свойств состояний, Конечный автомат, Сеть Петри, Укладка.
Литература
[Евстигнеев/85],
[Касьянов/88],
[Евстигнеев-Касьянов/94]