О сложности покрытия графов графами из специальных базисов

• Автор: Ложкина, Зинаида Сергеевна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2002
• Место защиты: Москва
• Количество страниц: 66 с.

Оглавление
1 Введение.
1.1 Общая характеристика работы
1.2 Определения и обозначения
1.3 Основные результаты
2 О соотношении между покрытием (0,1)-матрицы и покрытием графа двудольными графами.
3 Критерий реберной плотности базиса.
4 Необходимое условие почти плотного базиса.
5 Достаточное условие и критерий почти плотного базиса.
6 Критерий слабо плотного базиса.
7 Точное покрытие тождественной матрицы (ОД)-матрицами специального вида.
8 Алгоритм построения точного покрытия графа для слабо плотных базисов специального вида.
9 Алгоритм построения точного покрытия графа для произвольного слабо плотного базиса.
1 Введение.
1.1 Общая характеристика работы.
В настоящей диссертации исследуется задача о покрытии связного графа без петель и кратных ребер базисными графами. В работах, касающихся покрытия графов, в качестве базисов обычно рассматриваются бесконечные множества графов, обладающие свойством наследственности (см., например, [1]-[3], [6], [13]). Это означает, что любой подграф базисного графа также является базисным. В работах
[1]. [3], [6] исследовались покрытия графа планарными графами, то есть іі качестве базиса рассматривалось бесконечное множество всех планарных графов. Были получены оценки толщины полного графа ([1]). полного двудольного графа ([3]), и п-мерного куба ([6]). В работе
[2] изучался вопрос о покрытии графа графами, в. южимыми в плоскую целочисленную решетку. В работе [13] исследовались покрытия графа остовными лесами и были получены оценки дрсвесности графа, то есть минимального количества оетовных лесов, достаточного для его покрытия.
В данной работе рассматриваются произвольные конечные базисы, состоящие из связных графов и содержащие тривиальный граф - ребро. Возникновение такой задачи связано с проблемой проектирования электронных схем. Каждую схему можно представить в виде графа, в котором вершины соответствуют узлам, а ребра соединениям схемы. Таким образом, задачу о покрытии графа графами из произвольных конечных базисов можно интерпретировать как проблему покрытия электронной схемы блоками соединений определенного вида.
По аналогии с другими синтезными задачами вводятся понятия сложности покрытия, сложности графа, а также функции ПТеннона двух типов. Функция Шеннона первого типа 1;(д) представляет собой максимальную сложность графа с д ребрами, функция Шеннона второго тина 1в{я,Р) представляет собой максимальную сложность графа
с р вершинами и Пусть рв - максимальное число ребер в графах базиса Б. Величина Рв называется весом базиса Б. Оказывается, что для любого базиса Б выполнены неравенства д/рв < 1в(я) < Я и я/Рв < Ы(Я-Р) < Я< Базисы, для которых Ы{я) — я/Рв + о((]). называются реберно-плотными. Базисы, для которых 1в{я-р) = я/Рв + 0(р). называются почти плотными. Базисы, для которых 1ъ{Я-р) = я/Рв+о(р2). называются слабо плотными. Для каждого из перечисленных классов базисов получен критерий принадлежности базиса данному классу. Так, оказалось, что базис Б с весом р является реберно-плотным тогда и только тогда, когда р < 2, почти плотным тогда и только тогда, когда он содержит дерево с р ребрами, и слабо плотным тогда и только тогда, когда он содержит двудольный граф с р ребрами.
Все исследования, касающиеся слабо плотных базисов, основаны на соответствии между покрытием графа двудольными графами и покрытием (ОД)-матриц (ОД)-матрицами. Для класса слабо плотных базисов и одного его подкласса найдены оптимальные по порядку методы построения покрытия графа двудольными базисными графами.
Полученные в диссертации результаты являются новыми. Материалы параграфов 1-6 настоящей диссертации опубликованы в работах
[7]-[П].
Работа выполнена под руководством доктора физико-математических наук профессора В.Б. Алексеева.

Тогда для любых вещественных а, 5, таких, что а, Ь > 0 и а + Ь < с, в матрице М найдется не менее аз(М) строк, в каждой из которых содержится не менее Ьз(М) единиц.
Доказательств о. Обозначим * = ДА/). с = е(М). Докажем лемму от противного. Пусть существуют такие вещественные числа
а.Ь. что а.Ь > 0, а + Ь < с, и число строк матрицы Л/, содержащих не менее Ьз единиц, меньше, чем аз. Тогда количество единиц в строках матрицы М, содержащих не менее Ьз единиц, не превосходит аз2, а количество единиц в строках матрицы М, содержащих менее Ьз единиц, не превосходит Ьз2. Следовательно.
е < аз2 + Ьз2 = (а + Ь)з'2 < сз2.
а ото противоречит условию (6.1).
Л е м м а д о к азан а.
Л е м м а 6.2. Пусть М„. п = 1.2,.... последовательность
квадратных (ОД)-матриц, и пусть с. О < с < 1. такое вещественное число, что
1) з(Мп) ос,
2) е.(Мп) > с(з(Мп)) п = 1.
Тогда для любых натуральных чисел Я,Т найдется такой помер N = АТ(В.Т), что для любого натурального п > N матрица М„ содержит тождественную подматрицу размера Я х Т.
Доказ а г е л ь с т в о. Докажем лемму от противною. Пусть существуют такие натуральные числа Я, Т и такая подпоследовательность натуральных чисел чц., что для любого к — 1.2,... в матрице Мщ не содержится тождественная подматрица размера Я х Г.
Положим зі, = з(МПк). ек = е(Мщ). Тогда для последовачсльности матриц МПк выполнены следующие условия:

■2’)ек>сз1 А-= 1.2,
Пусть а.Ь - вещественные числа, о, Ь > 0 и а + Ь < с. Тогда из леммы