Графы, удовлетворяющие свойству продолжения метрики тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

ГТ6 од

8 ОКТ я^Д61*11151 наук

Сибирское отделение

Институт математики

им. С.Л.Соболева

Диссертационный совет Д 002.23.03

На правах рукописи УДК 519.176

Федоряева Татьяна Ивановна

ГРАФЫ, УДОВЛЕТВОРЯЮЩИЕ СВОЙСТВУ ПРОДОЛЖЕНИЯ МЕТРИКИ

(01.01.09 - математическая кибернетика)

Автореферат

диссертации на соискание ученой степени кандидата физико-математических наук

Новосибирск — 1996

Работа выполнена в Институте математики им. С.Л.Соболева СО РАН.

Научный руководитель: кандидат физико-математических наук, доцент А.А.Евдокимов

Официальные оппоненты: доктор физико-математических наук, профессор В.В.Алексеев доктор физико-математических наук, профессор В.А.Евстигнеев

Ведущая организация: Московский государственный университет им. М.В.Ломоносова

Защита диссертации состоится 1996 г. в часов на заседании

диссертационного совета Д 002.23.03 при Институте математики СО РАН по адресу: 630090 Новосибирск, Университетский пр., 4.

С диссертацией можно ознакомиться в библиотеке Института математики СО РАН.

Автореферат разослан 1996 г.

Ученый секретарь

диссертационного совета Д 002.23.03 д.ф.-м.н., профессор А.В.Косточка

Общая характеристика работы

Актуальность темы. Метрические аспекты занимают особое место а теории графов и в общей теории дискретных метрических пространств. Это объясняется тем, что, с одной стороны, многие метрические свойства и характеристики служат мощным инструментом исследований уже известных дискретных задач и, с другой стороны, они естественным образом возникают в различных разделах дискретной математики: теории кодирования, математической теории транспортных сетей, связи, теории выпуклого анализа и т.д., приводя к постановке и решению ряда интересных проблем. Таковы, например, вопросы о структуре центра и медианы графа, изометрических вложениях, реализации произвольных метрик графами, метрической выпуклости, расположении кратчайших цепей в графе [6-9,13].

В [1] А.А.Евдокимовым определены свойство продолжения метрики (СПМ) и свойство 5-продол жения метрики (<у-СПМ) для произвольного дискретного метрического пространства (X, рх\ в частности для связных обыкновенных графов с обычным расстоянием между вершинами. Пространство (X, рх) диаметра <1(Х) удовлетворяет СПМ, если 5]г(х) % (у) или (у) £ 5'х(х) для любых точек х,у £ X, где г = рх(х,у) < ¿(X) и — шар радиуса г с центром в точке г. Если СПМ рас-

сматривается лишь для точек х и у таких, что рх(х,у) < то получаем определение 9-СПМ.

СПМ и ?-СПМ возникли при исследовании общих свойств локально изометрических вложений. Так, в [1-3] изучались отображения дискретных метрических пространств, сохраняющие отношения р-близости и ^-отделимости между элементами (см. определения на стр.б), а среди них выделено двухпараметрическое семейство локально изометрических < р,д >-вложений. Отображения указанного типа возникают в различных разделах дискретного анализа и математической кибернетики, главным образом связанных с изучением таких преобразований дискретных систем, которые сохраняют определенную информацию об их метрическом строении, близости элементов, связности, отделимости и т.п. При этом свойства локально изометрических вложений с параметрами р, q оказываются связанными со свойствами самих дискретных метрических пространств. Тале, не для всякого дискретного метрического пространства X его отображение / : X —у У, сохраняющее смежность и ^-отделимость, сохраняет и меньшую д'-отделимость, <}' < д, т.е. для отображений / может не выполняться свойство монотонности по д-отделимости, в то время как для дискретных метрических пространств с д-СПМ любое вложение, сохраняющее смежность, обладает этим свойством монотонности [1,5]. Как оказалось, класс графов, удовлетворяющих ?-СПМ, полностью и характеризуется монотонностью по д-отделимости для всех отображений из более широкого класса отображений, сохраняющих 1-близость. В свою очередь, для дискретных метрических пространств X с СПМ это означает, что для любого отображения

/ : X —> У, сохраняющего 1-близость, корректно определен порог отделимости q(f), причем, как показано в диссерта&ии, существование порога отделимости в точности характеризует СПМ для графов. Тем самым графы с СПМ оказались "хорошими" в связи с их локально изометрическими отображениями /:(?—»//, т.е. отображениями со свойствами

PH(/(i),/(y)) < 9 => ра(х,у) < q,

Рв(х, y)<q=* pH(f(x)J(y)) = Рв(х,у)-Диаметр локальности (наибольшее значение q, q < d(G), при котором выполняются указанные свойства) всякого локально изометрического отображения / не превосходит m(f) = max{ç < d{G) \ / сохраняет ^-отделимость}. В диссертации показано, что только на графах с СПМ всякое отображение /, сохраняющее 1-близость, является локально изометрическим с максимально возможным диаметром локальности и т(/) = (?(/). Последнее свойство означает сохранение таким отображением / "малых" расстояний и несжимаемость "больших" расстояний ниже порога отделимости ?(/), что находит разнообразные применения, отмеченные, например, в [1]. Так, если / задало на графе с СПМ и действует в пространство слов Хемминга, то любое такое вложение является кодированием, при котором малые изменения в кодируемых объектах приводят к малым же изменениям в их кодах, и наоборот. Это позволяет по кодам делать вывод о метрической близости объектов исходного кодируемого множества, что существенно, например, при работе с кодами в ЭВМ. В частности, в задачах классификации и распознавании образов это ускоряет процедуру сравнения при установлении факта и меры похожести объектов или их признаковых векторов [11,19]. Кроме того, свойство сохранения "малых" расстояний используется при обработке и кодировании данных для увеличения надежности, быстродействия и исправления ошибок граничного считывания в аналого-цифровых преобразователях [4,18], поскольку невыполнение в кодах сохраняемых отображением свойств сигнализирует об ошибке. При проектировании коммуникационных сетей, каналов связи и т.п. СПМ для пространств этих моделей также оказывается существенным, так как обеспечивает сохранение любым вложением определенной локальной метрической информации о структуре исходного пространства. При этом "степень" локальности этих вложений зависит от их метрических характеристик. Отметим, что для вложений классических дискретных метрических пространств (которые удовлетворяют СПМ) таких, как конечная n-мерная целочисленная решетка, «-мерный тор, гиперкуб, пространства с метрикой Хемминга,в [1-3] приведены оценки сорога отделимости и радиуса изометричности.

Таким образом, СПМ и задача описания пространств с СПМ возникли при изучении влияний свойств метрик на общие свойства локально изометрических вложений. С другой стороны, СПМ оказалось интересным и для "чистой" теории графов, поскольку, как замечено в [1], приводит к просто формулируемому метрическому свойству для графа, а именно, любые две его вершины должны принадлежать некоторой диаметральной цепи.

В этой связи задачи исследования СПМ и характеризации классов графов, удовлетворяющих СПМ, естественно рассматривать в ряду других задач характеризации известных классов графов, также определяемых в терминах метрических свойств. Отметим, например, классы птолемеевых, хордовых, медианных, геодезических, дистанционно-регулярных графов, наследственных по расстоянию, графов с »¿-метрикой (см. обзоры [8,9]). Кроме того, в работе [5] показано, что почти все графы удовлетворяют СПМ.

В дальнейшем будем пользоваться следующим эквивалентным определением СПМ для графов [1].

ОПРЕДЕЛЕНИЕ. Две вершины графа в удовлетворяют СПМ, если они принадлежат некоторой диаметральной цепи графа в. Граф удовлетворяет СПМ, если любые две его вершины удовлетворяют СПМ.

В свою очередь^-СПМ для графов в точности означает отсутствие тупиковых (т.е. кратчайших и максимальных по вложению) цепей длины меньшей д [1,5]. Иными словами, это равносильно существованию покрытия всех пар вершин графа кратчайшими цепями длины не менее д (т.е. для любых двух вершин должна быть цепь, входящая в покрытие и проходящая через них). Поэтому д-СПМ для графов представляет собой вариант известной задачи о покрытии. Различные аспекты задачи о покрытии: выбор минимального покрытия, существование покрытий специального вида, нахождение мощности и числа покрытий таких, как покрытия графа циклами, звездами, двудольными, планарными подграфами, системой окрестностей его вершин, цепями, удовлетворяющими заданным ограничениям, — рассматривались в [8,10,12,16]. Отметим один прикладной аспект задачи о покрытии пар вершин графа кратчайшими цепями как математической модели задачи организации движения пассажирского транспорта [15], точнее, выбора системы транспортных маршрутов, позволяющей попасть из любого узла транспортной сети в любой другой без пересадок. Если мы будем дополнительно предполагать, что длина транспортных маршрутов не менее ц (что обусловлено, например, нецелесообразностью коротких маршрутов), -го возможность организации такой транспортной сети — это вопрос о существовании покрытия пар вершин кратчайшими цепями длины не менее у, т.е. о наличии <?-СПМ для графа, реализующего модель данной сети. Кроме того, в больших транспортных сетях естественно гарантировать только лишь локальную беспересадочность на транспортных маршрутах заданной длины <7, что может объясняться, например, надежностью эксплуатации, запасом горючего и т.п. Это также приводит к вопросу о <у-СПМ для графа, поскольку необходимо организовать покрытие всех пар вершин, расстояние между которыми не более кратчайшими цепями длины <7. Аналогичные математические модели возникают при эксплуатации коммуникационных сетей, каналов связи и т.п., когда требуется непосредственное соединение между двумя объектами без дополнительных устройств переключения.

Цель работы. Исследование СПМ для конечных обыкновенных графов с обычным расстоянием между вершинами и описание ряда классов графов с СПМ.

Научная новизна. Все результаты работы являются новыми. В диссертации получена характеризация графов, удовлетворяющих СПМ, в терминах метрических свойств локально изометрических отображений. Доказана теорема об изометрическом вложении с сохранением СПМ произвольного графа в подходящий граф заданной связности и показано, что задачи описания классов связных, связности п и п-связных графов с СПМ эквивалентны. Для графов малой связности получено полное описание естественных классов таких графов с СПМ, а именно, среди графов связности 1 описаны кактусы с СПМ, в классе графов связности 2 — двусвязные внешнепланарные графы с СПМ. Определены естественные усиления СПМ и доказаны харакгеризационные теоремы для классов графов, удовлетворяющих этим свойствам.

Практическая и теоретическая ценность. Диссертация носит теоретический характер. Результаты диссертации могут быть использованы при исследовании метрических свойств графов, общих свойств локально изометрических вложений дискретных метрических пространств и при решении других задач дискретной математики.

Публикации и апробация работы. Результаты диссертации докладывлись на семинарах Института математики СО РАН и НГУ "Дискретный анализ" и "Экстремальные задачи на графах", на X Международной конференции по проблемам теоретической кибернетики (г. Саратов, 1993 г.), Втором сибирском конгрессе по прикладной и индустриальной математике (г. Новосибирск, 1996 г.), представлены в тезисах на XI Международной конференции по проблемам теоретической кибернетики (г. Ульяновск, 1996 г.). Результаты диссертации опубликованы в [20-27].

Структура и объем работы. Диссертация состоит из введения, четырех глав, списка литературы и приложения. Объем работы 109 страниц. Список литературы содержит 46 наименований.

Содержание диссертации

Во введении обсуждается актуальность работы, дается обзор основных результатов и вводятся определения и обозначения. В диссертации используются общепринятые понятия теории графов и дискретных метрических пространств [6,7,13]. Рассматриваются конечные обыкновенные графы, которые предполагаются связными, если не оговорено особо.

Первая глава диссертации посвящена характеризации графов с СПМ и изучению инвариантных относительно СПМ операций и изометрических вложений.

В этой главе диссертации на основе результатов работ [1,5] получена характеризация графов, удовлетворяющих СПМ, в терминах метрических свойств локально изометрических отображений. Рассмотрим графы G, H и произвольное отображение / : G —> H. Пусть р, q — целые неотрицательные числа. Отображение / сохраняет р-6лизость, если для любых вершин г,у € таких, что ра{х,у) < р, выполнено неравенство Рн(/{х),/(у)) < Р■ Отображение } сохраняет q-отделимость, если для любых вершин х,у £ V(G) неравенство ра[х,у) > q влечет неравенство

Рн(К^), 1(у)) > q■ Будем говорить, что для отображения / определен порог отделимости, если существует число ?(/) < ¿(<?) такое, что / сохраняет ^-отделимость для любого ? < <?(/) и не сохраняет ^-отделимость при ? > д(/) а <] < ¿(б).

ТЕОРЕМА 1.1.1. Для графа О следующие условия эквивалентны:

(¡) (3 удовлетворяет СПМ;

(и) ¿ля всякого отображения / : б -» Я, сохраняющего 1-близость, определен порог отделимости ?(/).

Как отмечалось выше, диаметр локальности всякого локально изометрического отображения / не превосходит m(f).

СЛЕДСТВИЕ 1.1.1. Граф в удовлетворяет СПМ тогда и только тогда, когда всякое отображение / : (3 —» Н, сохраняющее 1-близость, является локально изометрическим с диаметром локальности т(/), при этом т(/) = q(f).

В этой же главе показано, что для описания графов с СПМ можно ограничиться изучением графов заданной связности. Пусть к(<3) — связность графа С, \¥п — класс всех графов (7 связности к(С) = п, п > 1, и IV* — класс всех графов из \У„, удовлетворяющих СПМ. Тогда и,>1 IV,- — класс всех связных графов, и,>„И/,' — класс всех гг-связных графов и имеем следующую цепочку строгих включений:

и,>,ИЛ* к ... э 1Л>„И7 Э и>„+1И7 э ...

Принадлежность графа в классу И'* накладывает ряд метрических ограничений на б, которые помогают описанию графов с СПМ. Например, наличие висячих вершин в С' с СПМ приводит к тому, что расстояние между этими вершинами должно быть равно диаметру графа (3. Причем, как показано во второй главе, это свойство является определяющим для описания СПМ в классе деревьев и существенно при характериза-ции унициклических графов с СПМ. В общем случае наличие "узких мест" — точек сочленения в графе (3 (т.е. принадлежность б классу М^) приводит к ограничениям на (3, которые позволили в главе 2 описать кактусы с СПМ. В случае графов класса 1У-2 в главе 3 также используются метрические ограничения для характеризадии внепшепланарных графов с СПМ.

Примечательно, что задачи описания классов связных, связности п и п-связных графов с СПМ оказались эквивалентными в том смысле, что описание любого из этих классов дает описание каждого оставшегося. Лля доказательства этого в первой главе определена операция, строящая по любому графу в новый граф Н заданной связности п > 1 с сохранением СПМ и метрики графа (7. Точнее, доказала

ТЕОРЕМА 1.3.1. Лля любого п > 1 существует изометрическое вложение произвольного графа (7 в подходящий граф Н связности п такой, что (7 удовлетворяет СПМ тогда и только тогда, когда Н удовлетворяет СПМ, причем ¿(Я) = 2й(С) + 1.

Из этой теоремы получено

СЛЕДСТВИЕ 1.3.1. Задачи описания классов ЦЫИ7,', и,>„И7 и п > 1, эквивалентны.

Для графов малой связности в диссертации получено описание естественных классов таких графов с СПМ, а именно среди графов связности 1 описаны кактусы с СПМ, в классе графов связности 2 — двусвязные внешнепланарные графы с СПМ.

В §1 главы 1 доказываются теорема 1.1.1 и ее следствия. В §2 исследуются вопросы сохранения СПМ операциями декартова произведения и соединения графов, первая из которых используется в доказательстве теоремы 1.3.1, а вторая — для определения простых операций, позволяющих из исходных графов получать новые графы с сохранением СПМ, а также для описания полных п-дольных графов с СПМ. Доказана инвариантность СПМ относительно операции декартова произведения О х II графов (3 и Н. Получены условия, при которых граф О II удовлетворяет СПМ. Для этого вводится определение волана и доказывается

ТЕОРЕМА 1.2.1. Пусть 0,Н — графи, не имеющие общих вершин (ке обязательно связные). Тогда граф (7 + Н удовлетворяет СПМ тогда и только тогда, когда выполнено одно из следующих условий:

(¡) (?, Н — полные графы;

(¡¡) хотя бы один из графов (?, Н неодновершинный и не представим в виде

+ Р (где Р — не обязательно связный граф) и каждая компонента связности графов <?,# не имеет волана.

Используя операции "х" и "4", можно получать новые графы с СПМ, например, справедливо следующее

СЛЕДСТВИЕ 1.2.1. Пусть б, и 1 < г < п, 1 < ] < т, п + т > 3, — графы диаметра не менее двух, попарно не имеющие общих вершин. Если все графы С?;,/^ удовлетворяют СПМ, то граф (и"=1 С,) + //,) удовлетворяет СПМ.

Теорема 1.2.1 позволяет также легко охарактеризовать полные п-дольные графы К{РЛ,Р2,-. - ,рп) с СПМ.

СЛЕДСТВИЕ 1.2.3. Полный п-дольный граф К(р\,... ,р„) удовлетворяет СПМ тогда и только тогда, когда выполнено одно из следующих условий:

1) р, = 1 при каждом : = 1,2,..., п;

2) р, ф 1 при каждом ¡ = 1,2.....пвп>2;

3) р, = 1 для некоторого г и pJ ф 1 при ] ф 1 < ¿, ,7 < п.

В §3 приводятся конструкции изометрических вложений. Доказываются теорема 1.3.1 и следствие 1.3.1, приводится способ построения из произвольного графа диаметра 2 нового графа, удовлетворяющего СПМ, с сохранением исходной метрики и диаметра (теорема 1.3.2).

Вторая глава посвящена изучению класса кактусов — естественных представителей класса IV; и описанию таких графов с СПМ. Напомним, что кактусом называется связный граф, в котором нет ребер, принадлежащих более чем одному простому циклу [14]. Кактусы называют также деревьями Хусими [17].

В §1 этой главы изучаются графы класса IV]. Для них определяется операция, позволяющая с сохранением СПМ получать новые графы этого класса и "разбирать" их до более простых графов из . С использованием этой операции далее описываются кактусы, удовлетворяющие СПМ. В §2 дается описание деревьев с СПМ (предложение 2.2.1) и уншиклических графов с СПМ (теорема 2.2.1). В §3 рассматривается общий случай и доказывается следующая

ТЕОРЕМА 2-3.1. Кактус в удовлетворяет СПМ тогда и только тогда, когда (3 — цепь, либо цикл, либо (? является одним из графов пяти конкретных видов.

В главе 3 рассматриваются естественные представители класса ТУа — двусвязные внешнепланарные графы и приводится характеризация таких графов, удовлетворяющих СПМ. Характеризация дана в терминах явного представления в виде таблицы 1 (приведенной в приложении диссертации) некоторого класса графов, называемых базисными, и трех операций склейки, с помощью которых из базисных графов строятся все остальные внешнепланарные графы, удовлетворяющие СПМ.

ТЕОРЕМА 3.1.1. Пусть б — двусвязный внешнепланарный граф. Граф (7 удовлетворяет СПМ тогда и только тогда, когда либо С? базисный граф, либо (7 получается операциями склейки из базисных графов одинакового четного диаметра, равного ¿(в).

Доказано, что для получения всех двусвязных внешнепланарных графов с СПМ нельзя отказаться ни от одной из операций склейки, т.е. каждая из них независима. Кроме того, каждая из операций склейки, применяемая к графам четного диаметра, сохраняет их диаметр и, следовательно, все двусвязные внешнепланарные графы с СПМ нечетного диаметра содержатся среди базисных. Отметим также, что базисные графы устроены следующим образом: каждый из них (за исключением цикла и графов

к > 6, Н\, Н2, изображенных на рисунке в диссертации) имеет внутреннюю га-грат, п < 12, к некоторым ребрам которой присоединены графы специального вида, названные лесенками и обобщенными лесенками. Явное описание базисных графов с точностью до изоморфизма дает следующая

ТЕОРЕМА 3.1.2.

1. Каждый базисный граф удовлетворяет СПМ.

2. Граф б является базисным тогда и только тогда, когда либо (7 простой цикл, граф 8/,, к > 6, Их или //2, либо (7 граф из таблицы 1.

3. Следующие базисные графы попарно неизоморфны: простой цикл, графы Зк, к > 6 , Н\, Нъ, графы, из таблицы, 1 с различными номерами.

Самостоятельный интерес представляет следующее следствие из теоремы 3.1.1.

СЛЕДСТВИЕ 3.1.1. Пусть G — двусвязпый внешнепланарный граф, не содержащий треугольников. Тогда G удовлетворяет СПМ тогда и только тогда, когда G — простой цикл длина, не менее 4 или G — один из графов одиннадцати конкретных видов.

В главе 4 определены некоторые естественные усиления свойства продолжения метрики и приводятся характеризапионные теоремы для классов графов, удовлетворяющих этим свойствам. Будем говорить, что граф G удовлетворяет СПМ1, если любые три его вершины принадлежат некоторой диаметральной цепи. Граф G удовлетворяет СПМ2, если любые два его ребра принадлежат некоторой диаметральной цепи. Граф G удовлетворяет СПМЗ, если любые его вершина и ребро принадлежат некоторой диаметральной цепи.

ТЕОРЕМА 4.1.1. Граф G удовлетворяет СПМ1 тогда и только тогда, когда G — цепь или 4-вершинный цикл.

СЛЕДСТВИЕ 4.1.1. При фиксированном п > 4 в графе G любые п вершин принадлежат некоторой его диаметральной цепи тогда и только тогда, когда G — цепь.

ТЕОРЕМА 4.1.2. Граф G удовлетворяет СПМ2 тогда и только тогда, когда G — цепь или G является графом одного конкретного вида.

СЛЕДСТВИЕ 4.1.2. При фиксированном п > 3 в графе G любые п ребер принадлежат некоторой его диаметральной цепи тогда и только тогда, когда G — цепь.

ТЕОРЕМА 4.1.3. Граф G удовлетворяет СПМЗ тогда и только тогда, когда G — двудольный граф, удовлетворяющий СПМ.

Таким образом, в этой главе рассмотрены все возможные усиления СПМ, когда при фиксированных пат таких, что п + m > 2, любые п вершин и m ребер принадлежат некоторой диаметральной цепи графа.

Автор выражает глубокую признательность своему научному руководителю А.А.Евдокимову за постоянное внимание к работе и многочисленные полезные обсуждения.

Литература

[1] Евдокимов A.A. Метрические свойства вложений и коды, сохраняющие расстояния // Тр. Ин-та математики / АН СССР. Сиб. отд-ние. 1988. Т.10: Модели и методы оптимизации. С. 116-132.

[2] Евдокимов A.A. Кодирование аналоговых данных и локально изометрические вложения дискретных пространств // 9-я Всесоюз. конф. по теории кодирования и передачи информации: Тез. докл. Одесса, 1988. Ч. 1. С. 317-318.

[3] Евдокимов A.A. Цепные коды с произвольным расстоянием // Докл. АН СССР. 1976. Т. 228, №6. С. 1273-1276.

[4] Евдокимов A.A. Локально изометрические кодирования с нулевой или асимптотически оптимальной избыточностью // X Симпоз. по проблеме избыточности в информационных системах: Тез. докл. Л., 1989. С. 27-30.

[5] Евдокимов A.A. Локально изометрические вложения графов и свойство продолжения метрики // Сиб. журн. исслед. операций. 1994. Т. 1, №1. С. 5-12.

[6] Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990. 384 с.

[7] Зыков A.A. Основы теории графов. М.: Наука, 1987. 381 с.

[8] Козырев B.II., Юшманов C.B. Теория графов (алгоритмические, алгебраические, и метрические проблемы) // Итоги науки и техники. Теория вероятностей. Мат. статистика. Теорет. кибернетика. М.: ВИНИТИ, 1985. Т. 23. С. 68-117.

[9] Козырев В.П., Юшманов C.B. Представления графов и сетей (кодирование, укладки и вложения) // Итоги науки и техники. Теория вероятностей. Мат. статистика. Теорет. кибернетика. М.: ВИНИТИ, 1990. С. 129-196.

[10] Ню В., Евдокимов A.A. Покрытия графов маршрутами // Методы дискретного анализа в оптимизации управляющих систем: Сб. науч. тр. Новосибирск: Ин-т математики СО АН СССР, 1983. Вып. 40. С. 72-86.

[11] Рейнгольд Э., Нивергельтп Ю., Лео Н. Комбинаторные алгоритмы, теория и практика. М.: Мир, 1980. 476 с.

[12] Сапоженко A.A., Асратян A.C., Кузюрин H.H. Обзор некоторых результатов по задачам о покрытии // Методы дискретного анализа в решении комбинаторных задач: Сб. науч. тр. Новосибирск: Ин-т математики СО АН СССР, 1977. Вып. 30. С. 46-75.

[13] Харари Ф. Теория графов. М.: Мир, 1973. 300 с.

[14] Харари Ф., Налмер Э. Перечисление графов. М.: Мир, 1977. 324 с.

[15] Юшманов C.B. Покрытие графа системой кратчайших простых цепей // Докл. АН СССР. 1982. Т. 266, №6. С. 1303-1305.

[16] Harary F. Covering and packing in graphs // Ann. N. Y. Acad. Sci. 1970. V. 175, №1. P. 198-205.

[17] Harary F., Norman R.Z. The dissimilarity characteristic of Husimi trees // Ann. of Math. 1953. V. 58. P. 134-141.

[18] Шее V. The use of circuit codes in analog-digital conversion // Graph Theory and its applications. N. Y. Acad. Press, 1970. P. 121-131.

[19] Preparata F.P., Nievergelt J. Difference-preserving codes // JEEE Trans. IT 20. 1974. P. 643-649.

Работы автора по теме диссертации

[20] Федоряева Т.И. Характеризация одного класса графов со свойством продолжения метрики / / Методы дискретного анализа в исследовании функциональных систем: Сб. пауч. тр. Новосибирск: Ин-т математики СО АН СССР, 1988. Вып. 47. С. 89-93.

[21] Федоряева Т.И. Усиленные свойства продолжения метрики // Методы дискретного анализа в теории графов и сложности: Сб. науч. тр. Новосибирск: Ин-т математики СО АН СССР, 1992. Вып. 52. С. 112-118.

[22] Федоряева Т.И. Характеризация классов графов со свойством продолжения метрики // Методы и системы технической диагностики. Саратов, 1993. Вып. 18. С. 175.

[23] Федоряева Т.И. Внешнепланарвые графы, удовлетворяющие свойству продолжения метрики. I. Новосибирск, 1995. (Препринт / РАН. Сиб. отд-ние. Ин-т матема-

[24] Федоряева Т.И. Внешнепланарные графы, удовлетворяющие свойству продолжения метрики. II. Новосибирск, 1995. (Препринт / РАН. Сиб. отд-ние. Ин-т математики; №2).

[25] Федоряева Т.И. Внешнепланарные графы, удовлетворяющие свойству продолжения метрики. III. Новосибирск, 1995. (Препринт / РАН. Сиб. отд-ние. Ин-т математики; К'З).

[26] Федоряева Т.И. Операции и изометрические вложения графов, связанные со свойством продолжения метрики // Дискрет, анализ и исслед. операций. 1995. Т. 2, №3. С. 49-67.

[27] Федоряева Т.И. Свойство продолжения метрики и порог отделимости отображений //XI Междунар. конф. по пробл. теорет. кибер.: Тез. докл. Ульяновск, 1996. С.'/ЭЧ.

тики; №1).