Разметка графиков
- Маркировка графа — присвоение меток ребрам и/или вершинам графа.
- Граф с маркировкой вершин называется графом с вершинной меткой.
- Граф с реберной меткой имеет метки ребер, являющиеся элементами упорядоченного набора.
- Термин «помеченный граф» обычно относится к графу с вершинами, все метки которых различны.
- Ребрам или вершинам могут быть присвоены метки, имеющие смысл в соответствующей области.
- Понятие маркировки может быть применено ко всем расширениям и обобщениям графов.
- Изящная маркировка графа определяется переходом от вершин к {0, …, |E|} и маркировкой ребер от 1 до |E|.
- Грациозная маркировка ребер на простом графе без петель или множественных ребер является маркировкой ребер различными целыми числами.
- Гармоничная маркировка на графе G — это инъекция из вершин G в группу целых чисел по модулю k.
- Раскраска графа — это подкласс графических меток, присваивающий разные метки соседним вершинам и ребрам.
- Удачная маркировка графа G — это присвоение целых положительных чисел вершинам графа таким образом, что если S(v) обозначает сумму меток на соседних с v графах, то S — это раскраска вершин графа G.
Полный текст статьи: