Оглавление
1 Введение. 3
1.1 Общая характеристика работы......................... 3
1.2 Определения и обозначения........................... о
1.3 Основные результаты................................. 9
2 О соотношении между покрытием (ОД)-матрицы и покрытием графа двудольными графами. 13
3 Критерий реберной плотности базиса. 16
4 Необходимое условие почти плотного базиса. 22
5 Достаточное условие и критерий почти плотного базиса. 27
6 Критерий слабо плотного базиса. . 34
7 Точное покрытие тождественной матрицы (0,1 (-матрицами специального вида. 43
8 Алгоритм построения точного покрытия графа для слабо плотных базисов специального вида. 53
9 Алгоритм построения точного покрытия графа для произвольного слабо плотного базиса. 56
1 Введение.
1.1 Общая характеристика работы.
В настоящей диссертации исследуется задача о покрытии связного графа без петель и кратных ребер базисными графами. В работах, касающихся покрытия графов, и качестве базисов обычно рассматриваются бесконечные множества графов, обладающие свойством наследствен пости (см., например, [1]-[3], [С]. [13]). Это означает, что любой подграф базисного графа также является базисным. В работах
[1]. [3]. [0] исследовались покрытия графа планарными графами, то есть в качестве базиса рассматривалось бесконечное множество всех планарных графов. Были получены оценки толщины полного графа ([!])• полного двудольного графа ([3]), и п-мерпого куба ([б]). В работе
[2] изучался вопрос о покрытии графа графами, вложимымм в плоскую целочисленную решетку. В рабой* [13] исследовались покрытия графа остоиными лесами и были получены оценки дровесности графа, то есть минимального количества остовных лесов, достаточного для его покры і ИЯ.
В данной работе рассматриваются произвольные конечные базисы, состоящие из связных графов п содержащие тривиальный граф - ребро. Возникновение такой задачи связано с проблемой проек гирования электронных схем. Каждую схем) можно представить в виде графа, в котором вершины соответствуют уздам, а ребра соединениям схемы. Таким образом, задачу о покрытии графа графами из произвольных конечных базисов можно интерпретировать как проблему покрытия электронной схемы блоками соединений определенного вида.
По аналогии с другими синтезными задачами вводятся понятия сложности покрытия, сложности графа, а также функции Шеннона двух типов. Функция Шеннона первого типа /\;(</) представляет собой максимальную сложность графа с су ребрами, функция Шеннона второго типа/б(^?р) предс тавляет собой максимальную сложность графа
Л
с р вершинами и ц ребрами. Обычно в сиптезных задачах асимптотика функции Шеннона исследуется на основе свойств рассматриваемых базисов- В данной работе используется несколько иной подход. В зависимости от асимптотики функций Шеннона выделяются различные классы базисов, а затем исследуются их свойства и методы нос і роения оптимальных покрытий.
Пусть рв - максимальное число ребер в графах базиса Б. Величина />в называется весом базиса Б. Оказывается, что для любого базиса Б выполнены неравенства д/р^ < /Б(</) < и я/рь < М>1>) < Я- Базисы, для которых іб((і) — ЧІРб~^°(я)' называются реберно-плотными. Базисы, для которых 1\,(ч- р) = я//}\> + 0(р)- называются почти плотными. Базисы, для которых 1б{Я-Р) — я/Ръ+°(р2)‘ называются слабо плотными. Для каждого из перечисленных классов базисов получен критерий принадлежности базиса данному классу. Гак. оказалось, что базис Б с весом р является реберно-плотным тогда п только тогда, когда р < 2. почти плотным тогда и только тогда, когда он содержит дерево с р ребрами, и слабо плотным тогда и только тогда, когда он содержит двудольный граф с р ребрами.
Все исследования, касающиеся слабо плотных базисов, основаны на соответствии между покрытием графа двудольными графами и покрытием (ОЛ)-матрнц (ОД)-матрицами. Для класса слабо плотных базисов и одного его подкласса найдены оптимальные но порядку методы построения покрытия графа двудольными базисными графами.
Полученные в диссертации результаты являются новыми. Материалы параграфов 1-6 настоящей диссертации опубликованы в работах
то].
Работа выполнена под руководством доктора физико-математических наук профессора В.Б. Алексеева.
4
1.2 Определения и обозначения.
Пусть Q множество всех связных графов без псі ель и кратных ребер, имеющих хотя бы одно ребро.
О п р е д е л е н и е . Граф, состоящий из двух вершин и одного ребра, соединяющего эти вершины, назовем тривиальным.
О и р е д е л е п и е . Множество попарно различных графов Б =
{G'i, ...,£гЛ} с числом ребер Г] rs соответственно называется базисом,
если оно содержит тривиальный граф, и при любом і = 1,2.... s G, € Q. Весом базиса Б называется величина
рГу = njax п.
]<1<S
Очевидно, что для любого базиса Б выполнено неравенство рв > 1-
0 и р е д е л е и и о . Пусть графы G, #ь..., Нгп. т > 1, принадлежа! классу с7. Покрытием графа G графами Н\ II ш называется
такое взаимооднозначное соответствие* между графами Hi IIи
подграфами G\,....Gm графа G, при котором каждое ребро графа G
принадлежит по крайней мере одному из подграфов G‘i Gm, іг для
любого і = 1..... т граф G, изоморфен графу
О п р е д о л е н и о . Будем говорить, что граф G Є Q покрывается грифами базиса Б. если существует такое покрытие графа G графами II \ что Ні Є Б для любого і = 1.2,..., т . Сложностью такого
покрытия б\дем называть число входящих в него графов, т.е. число т.
О и р <* д е л е н и е. Покрытие графа G € Q графами Н\ Нш
из базиса Б называется точным, если подграфы G\ Gm графа
G. соответствующие графам попарно не пересекаются но
ребрам.
Через q{G) обозначим число ребер графа G. а через p{G) - число его вершин.
О п ]> е д е л с и и е . Минимальное число базисных графов, достаточное для покрытия всех ребер графа G Є С. называется слож-
ностъю графа С и обозначается 1и(0). Покрытие' графа С называется минимальным, если его сложность равна /п(СУ).
Очевидно, что для любого графа С Є 1/ в любом базисе Б выполнены неравенства
— <ЫС)<я(С). (1.1)
РВ
ПерВОО из этих не равенств следует из того, что
/в(6‘)
Я(0) < Е я{Нк).
А=1
где Н|,.... Я/,.(£> - минимальное покрытие графа С: второе неравенство вытекает из наличия в базисе Б тривиального графа.
() н р е д е л е н и е . Функцией Шеннона I типа в классе С/ называется функіція
1Ъ(([) = шах /Б(С).
<?€(/: </{6’)=?
Функцией Шеннона II типа в классе (7 называется функция
1ъ(<1-р) = шах ЫО)-
О £ у:
Из (1.1) и определения функпиП Шеннона следует, что для любого базиса Б и любых натуральных у,р справедливы неравенства
— <1б((МО < ?• — < *в(</) < <7* (1-2)
Ри Рб
О и р е д е л е и и е . Базис Б называется рсСІерно-плотным,. если
Ыя) = — + °{(і)-
РБ
О пред е л е н и (* . Базис Б называется почти плотным., если
1вШ = ± + 0(р).
Рп
Определение. Базис Б называется слабо плотным, (»ели
Ы(1'Р) — — + °(р2)-Рб
- Київ+380960830922