Помеченный граф

Графы бывают помеченными и непомеченными. Ниже представлено $2$ графа одинаковой конфигурации, но один из них является непомеченным (левый), а другой помеченным (правый).

непомеченный граф	помеченный граф

Думаю, что вам стало сразу понятно, какой граф является помеченным, а какой — нет!

Помеченный граф — граф, вершинам которого присвоены какие-либо обозначения/метки.

➡ Например, метками вершин данного графа являются натуральные числа:Но никто не запрещает использовать метки, например, выраженные буквами латинского алфавита:

Также важно еще понимать, что помеченность распространяется только на вершины графа. Абсолютно непринципиально, например, является граф ориентированным или нет, взвешенным или нет, двудольным или нет и т.д. Если к каждой вершине приписано какое-то обозначение (как правило, натуральное число), то граф является помеченным и точка.
➡ Вот пример ориентированного помеченного мультиграфа:

С помеченным графом работать гораздо удобнее, чем с непомеченным. Поэтому в вузах в $99\%$ случаев студенты сталкиваются с помеченными графами. Непомеченные графы лишь иногда выступают в качестве иллюстрации какой-либо конфигурации. Но разбирать алгоритмы на непомеченных графах практически невозможно, так как нет возможности идентифицировать ту или иную вершину.

💡 Всегда старайтесь взаимодействовать с помеченными графами.

Материал подготовил Александр Георгиевич, специалист по графам и графовым алгоритмам. Для записи на частную подготовку звонить по номеру телефона: 8(926) 610 — 61 — 95 (электронный адрес: proglabs@mail.ru).