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