Маркировка графика
В математической дисциплине теории графов маркировка графа — это присвоение меток, традиционно представленных целыми числами , ребрам и/или вершинам графа . [1]
Формально для данного графа маркировка вершин является функцией множества меток; граф с такой определенной функцией называется графом с метками вершин . Точно так же маркировка ребер является функцией набора меток. В этом случае граф называется графом с ребрами .
Когда метки ребер являются членами упорядоченного набора (например, действительные числа ), это можно назвать взвешенным графом .
При использовании без уточнения термин «граф с метками» обычно относится к графу с метками вершин, в котором все метки различны. Такой граф может быть эквивалентно помечен последовательными целыми числами , где - количество вершин в графе. [1] Во многих приложениях ребрам или вершинам присваиваются метки, которые имеют смысл в соответствующей области. Например, ребрам могут быть назначены веса , представляющие «стоимость» прохождения между инцидентными вершинами. [2]
В данном определении под графом понимается конечный неориентированный простой граф. Однако понятие маркировки может применяться ко всем расширениям и обобщениям графов. Например, в теории автоматов и теории формальных языков удобно рассматривать помеченные мультиграфы , т. е. пара вершин может быть соединена несколькими помеченными ребрами. [3]
Большинство обозначений графов восходят к обозначениям, представленным Александром Розой в его статье 1967 года. [4] Роза определил три типа маркировки, которые он назвал α , β- и ρ -маркировкой. [5] β -обозначения позже были переименованы Соломоном Голомбом в «изящные» , и с тех пор это имя стало популярным.
