Я изучаю теорию графов, и в настоящее время я сосредоточен на конкретной проблеме c маркировки графов. Учитывая (неориентированный или направленный) граф G и ориентированный граф M, где G имеет больше вершин, чем M, я хочу пометить некоторые вершины в G так, чтобы они соответствовали меткам каждой вершины в M. Маркировка должна сохранять пути между вершинами в М. Я приведу реальный пример того, что я имею в виду здесь. Предположим, что есть город с количеством строений X, соединенным с дорогами, и график «карты сокровищ» с количеством вершин Y и X> Y. Предположим, мы хотим назначить несколько зданий в городе в качестве вершин в сокровище карта. Мы хотим, чтобы назначение сохраняло связи между вершинами карты, и под «сохранением» я имею в виду следующее: учитывая, что вершины J и K карты сокровищ с ребром между ними, J и K должны быть назначены двум зданиям в городе соединенные путем, ДАЖЕ ЕСЛИ есть другие (неназначенные) здания на пути между этими двумя зданиями. Таким образом, в принципе, задание является правильным, если у людей (которые хотят играть в игру «Охота за сокровищами») есть способ добраться из здания J в здание K.
Были ли книги / бумаги / исследует эту проблему, и если да, может ли кто-нибудь указать мне на книги / статьи / исследования? Большое спасибо. Если вы хотите вместо этого объяснить решение, я буду признателен за это.