Введение к работе
Актуальность темы. Метрические аспекты занимают особое место в теории графов и в общей теории дискретных метрических пространств. Это объясняется тем, что, с одной стороны, многие метрические свойства и характеристики служат мощным инструментом исследований уже известных дискретных задач и, с другой стороны, они естественным образом возникают в различных разделах дискретной математики: теории кодирования, математической теории транспортных сетей, связи, теории выпуклого анализа и т.д., приводя к постановке и решению ряда интересных проблем. Таковы, например, вопросы о структуре центра и медианы графа, изометрических вложениях, реализации произвольных метрик графами, метрической выпуклости, расположении кратчайших цепей в графе [6-9,13].
В [1] А.А.Евдокимовым определены свойство продолжения метрики (СПМ) и свойство q-продол жения метрики (<у-СПМ) для произвольного дискретного метрического пространства (X, рх\ в частности для связных обыкновенных графов с обычным расстоянием между вершинами. Пространство (X, рх) диаметра d(X) удовлетворяет СПМ, если Sx(x) % Sx(y) или Sx(y) g S'x(x) для любых точек х,у Є X, где і = рх{х,у) < d{X) и Sx(z) — шар радиуса г с центром в точке z. Если СПМ рассматривается лишь для точек хну таких, что рх{х,у) < ?, то получаем определение 9-СПМ.
СПМ и 9-СПМ возникли при исследовании общих свойств локально изометрических вложений. Так, в [1-3] изучались отображения дискретных метрических пространств, сохраняющие отношения р-близости и ^-отделимости между элементами (см. определения на стр.б), а среди них выделено двухпараметрическое семейство локально изометрических < p,q >-вложений. Отображения указанного типа возникают в различных разделах дискретного анализа и математической кибернетики, главным образом связанных с изучением таких преобразований дискретных систем, которые сохраняют определенную информацию об их метрическом строении, близости элементов, связности, отделимости и т.п. При этом свойства локально изометрических вложений с параметрами р, q оказываются связанными со свойствами самих дискретных метрических пространств. Так, не для всякого дискретного метрического пространства X его отображение / : X — Y, сохраняющее смежность и ^-отделимость, сохраняет и меньшую g'-отделимость, q' < q, т.е. для отображений / может не выполняться свойство монотонности по q-отделимости, в то время как для дискретных метрических пространств с g-СПМ любое вложение, сохраняющее смежность, обладает этим свойством монотонности [1,5]. Как оказалось, класс графов, удовлетворяющих q-CTIM, полностью и характеризуется монотонностью по ^-отделимости для всех отображений из более широкого класса отображений, сохраняющих 1-близость. В свою очередь, для дискретных метрических пространств X с СПМ это означает, что для любого отображения
/ : X —> Y, сохраняющего 1-близость, корректно определен порог отделимости q(f), причем, как показано в диссертации, существование порога отделимости в точности характеризует СПМ для графов. Тем самым графы с СПМ оказались "хорошими" в связи с их локально изометрическими отображениями / : G —> Н, т.е. отображениями со свойствами
Рн(/(і),/(у)) < 9 => />с(х,у) < д, Рв(х,y)
Диаметр локальности (наибольшее значение q, q < d(G), при котором выполняются указанные свойства) всякого локально изометрического отображения / не превосходит m(f) = max{g < d(G) \ / сохраняет «^-отделимость}. В диссертации показано, что только на графах с СПМ всякое отображение /, сохраняющее 1-близость, является локально изометрическим с максимально возможным диаметром локальности и m(/) = (/). Последнее свойство означает сохранение таким отображением / "малых" расстояний и несжимаемость "больших" расстояний ниже порога отделимости (/), что находит разнообразные применения, отмеченные, например, в [1]. Так, если / задано на графе с СПМ и действует в пространство слов Хемминга, то любое такое вложение является кодированием, при котором малые изменения в кодируемых объектах приводят к малым же изменениям в их кодах, и наоборот. Это позволяет по кодам делать вывод о метрической близости объектов исходного кодируемого множества, что существенно, например, при работе с кодами в ЭВ.М. В частности, в задачах классификации и распознавании образов это ускоряет процедуру сравнения при установлении факта и меры похожести объектов или их признаковых векторов [11,19]. Кроме того, свойство сохранения "малых" расстояний используется при обработке и кодировании данных для увеличения надежности, быстродействия и исправления ошибок граничного считывания в аналого-цифровых преобразователях [4,18], поскольку невыполнение в кодах сохраняемых отображением свойств сигнализирует об ошибке. При проектировании коммуникационных сетей, каналов связи и т.п. СПМ для пространств этих моделей также оказывается существенным, так как обеспечивает сохранение любым вложением определенной локальной метрической информации о структуре исходного пространства. При этом "степень" локальности этих вложений зависит от их метрических характеристик. Отметим, что для вложений классических дискретных метрических пространств (которые удовлетворяют СПМ) таких, как конечная n-мерная целочисленная решетка, n-мерный тор, гиперкуб, пространства с метрикой Хемминга, в [1-3] приведены оценки порога отделимости и радиуса изометричности.
Таким образом, СПМ и задача описания пространств с СПМ возникли при изучении влияний свойств метрик на общие свойства локально изометрических вложений. С другой стороны, СПМ оказалось интересным и для "чистой" теории графов, поскольку, как замечено в [1], приводит к просто формулируемому метрическому свойству для графа, а именно, любые две его вершины должны принадлежать некоторой диаметральной цепи.
.4
В этой связи задачи исследования СПМ и характеризации классов графов, удовлетворяющих СПМ, естественно рассматривать в ряду других задач характеризации известных классов графов, также определяемых в терминах метрических свойств. Отметим, например, классы птолемеевых, хордовых, медианных, геодезических, дистанционно-регулярных графов, наследственных по расстоянию, графов с «^-метрикой (см. обзоры [8,9]). Кроме того, в работе [5] показано, что почти все графы удовлетворяют СПМ.
В дальнейшем будем пользоваться следующим эквивалентным определением СПМ для графов [1].
ОПРЕДЕЛЕНИЕ. Две вершины графа G удовлетворяют СПМ, если они принадлежат некоторой диаметральной цепи графа G. Граф удовлетворяет СПМ, если любые две его вершины удовлетворяют СПМ.
В свою очередь,?-СПМ для графов в точности означает отсутствие тупиковых (т.е. кратчайших и максимальных по вложению) цепей длины меньшей q [1,5]. Иными словами, это равносильно существованию покрытия всех пар вершин графа кратчайшими цепями длины не менее q (т.е. для любых двух вершин должна быть цепь, входящая в покрытие и проходящая через них). Поэтому ?-СПМ для графов представляет собой вариант известной задачи о покрытии. Различные аспекты задачи о покрытии: выбор минимального покрытия, существование покрытий специального вида, нахождение мощности и числа покрытий таких, как покрытия графа циклами, звездами, двудольными, планарными подграфами, системой окрестностей его вершин, цепями, удовлетворяющими заданным ограничениям, — рассматривались в [8,10,12,16]. Отметим один прикладной аспект задачи о покрытии пар вершин графа кратчайшими цепями как математической модели задачи организации движения пассажирского транспорта [15], точнее, выбора системы транспортных маршрутов, позволяющей попасть из любого узла транспортной сети в любой другой без пересадок. Если мы будем дополнительно предполагать, что длина транспортных маршрутов не менее q (что обусловлено, например, нецелесообразностью коротких маршрутов), го возможность организации такой транспортной сети — это вопрос о существовании покрытия пар вершин кратчайшими цепями длины не менее q, т.е. о наличии q-СПМ для графа, реализующего модель данной сети. Кроме того, в больших транспортных сетях естественно гарантировать только лишь локальную беспересадочность на транспортных маршрутах заданной длины q, что может объясняться, например, надежностью эксплуатации, запасом горючего и т.п. Это также приводит к вопросу о q-CUM для графа, поскольку необходимо организовать покрытие всех пар вершин, расстояние между которыми не более q, кратчайшими цепями длины q. Аналогичные математические модели возникают при эксплуатации коммуникационных сетей, каналов связи и т.п., когда требуется непосредственное соединение между двумя объектами без дополнительных устройств переключения.
Цель работы. Исследование СПМ для конечных обыкновенных графов с обычным расстоянием между вершинами и описание ряда классов графов с СПМ.
Научная новизна. Все результаты работы являются новыми. В диссертации получена характеризация графов, удовлетворяющих СПМ, в терминах метрических свойств локально изометрических отображений. Доказана теорема об изометрическом вложении с сохранением СПМ произвольного графа в подходящий граф заданной связности и показано, что задачи описания классов связных, связности п и п-связных графов с СПМ эквивалентны. Для графов малой связности получено полное описание естественных классов таких графов с СПМ, а именно, среди графов связности 1 описаны кактусы с СПМ, в классе графов связности 2 — двусвязные внешнепланарные графы с СПМ. Определены естественные усиления СПМ и доказаны характеризационные теоремы для классов графов, удовлетворяющих этим свойствам.
Практическая и теоретическая ценность. Диссертация носит теоретический характер. Результаты диссертации могут быть использованы при исследовании метрических свойств графов, общих свойств локально изометрических вложений дискретных метрических пространств и при решении других задач дискретной математики.
Публикации и апробация работы. Результаты диссертации докладывлись на семинарах Института математики СО РАН и НГУ "Дискретный анализ" и "Экстремальные задачи на графах", на X Международной конференции по проблемам теоретической кибернетики (г. Саратов, 1993 г.), Втором сибирском конгрессе по прикладной и индустриальной математике (г. Новосибирск, 1996 г.), представлены в тезисах на XI Международной конференции по проблемам теоретической кибернетики (г. Ульяновск, 1996 г.). Результаты диссертации опубликованы в [20-27].
Структура и объем работы. Диссертация состоит из введения, четырех глав, списка литературы и приложения. Объем работы 109 страниц. Список литературы содержит 46 наименований.