Содержание к диссертации
Введение
ГЛАВА I. Общие свойства максимального рода графов ... 13
1.1. К- разложения, хордовость и максимальный род графов 13
1.2.O-хордовые графы 23
1.3.Хордово критические графы 30
1.4. Существенность ребер графа относительно максимального рода 37
ГЛАВА 2. Нахождение максимального рода графов 47
2.1. Циклическая связность и максимальный род графов 47
2.2.Максимальный род плоских графов 56
2.3. Полиномиальный алгоритм нахождения макси мального рода связного графа 63
2.4.Применения полученных результатов 74
Литература 84
Приложение 91
- К- разложения, хордовость и максимальный род графов
- Существенность ребер графа относительно максимального рода
- Циклическая связность и максимальный род графов
- Полиномиальный алгоритм нахождения макси мального рода связного графа
Введение к работе
Одна из наиболее важных и интересных проблем современной теории графов заключается в определении множества родов всех компактных ориентируемых 2-многообразий, в которые граф вкладывается 2-клеточно. Согласно известной теореме Р.А.Дьюка [27] о промежуточных вложениях, связный граф G- вкладывается в ориентируемое 2-многообразие б'у рода V 2-клеточно тогда и только
тогда, когда
f (&)* V^ JTM(G)r
где К*" (G-) - абсолютный, a J*" (G)- максимальный роды графа &. В то время как исследования абсолютного рода (или просто рода) графов имеют почти столетнюю историю (первой работой в этой области можно считать статью П.Хивуда [ЗО]), первые публикации, посвященные максимальному роду графов, относятся к
1970 году. Это, в первую очередь работа Н.П.Хоменко и Э.Б.Явор
ского [21], в которой с помощью метода У- преобразований впер
вые был найден критерий 1-компонентной 2-клеточной вложимости
графа Gr в ориентируемое 2-многообразие ^ , представляющий
собой следующее утверждение.
Теорема 9 [2l] . Граф Q- вкладывается в ориентируемое 2-многообразие <5у 1-компонентно 2-клеточно тогда и только тогда, когда в нем существуют такие V независимых пар смежных ребер, после удаления которых остается фактордерево графа G- .
С помощью этого критерия авторам удалось установить роды ориентируемых 2-многообразий, в которые I- или 2-компонентно 2-клеточно вкладываются графы Кл, Qn, Кп,п . Тем самым впервые был найден максимальный род этих графов.
Понятие максимального рода графов было, однако, введено в
1971 году Е.А.Нордхаузом, Б.М.Стюартом и А.Т.Уайтом в работе
_ 4 -/42], в которой также (другим методом) был найден максимальный род графа Кп . Эти же авторы вместе с Р.Д.Рингайзеном в работе [4lJ нашли условия, при которых максимальный род графа равен нулю. Р.Д.Рингайзен в работе[45]нашел максимальный род некоторых плоских графов, а в работе[46J- максимальный род графа Л/77,/7. В работe/47J Р.Д.Рингайзен ввел в рассмотрение класс сверху вложимых графов , т.е. таких графов G , для которых
^ (Q. ) = [_ lls2J , изучил ряд свойств этих графов и высказал несколько гипотез.
В 1973 году вышел в свет ряд работ, посвященных исследованию максимального рода графов с помощью метода <р - преобразований. Особое место среди этих работ заняла статья Н.П.Хоменко, Н.А.Островерхого и В.А.Кузьменко [19J , в которой была доказана следующая фундаментальная в теории максимального рода графов теорема.
ТеоремаА [19] . Максимальный род произвольного графа & равен максимальному числу таких независимых пар смежных ребер в G , что граф, полученный из о- в результате удаления всех ребер этих пар, будет связным факторграфом графа & .
Благодаря этому результату был найден максимальный род полных К- дольных, диаметрально-критических и других классов графов. В работе Н.А.Островерхого и В.А.Кузьменко [llj с помощью теоремы А [19] был найден максимальный род декартового, сильного декартового и лексикографического произведений двух графов, а в работе Н.А.Островерхого [ю] - найден максимальный род некоторых произвольных графов.
Интересно отметить, что практически все результаты, полученные к 1973 году в области максимального рода графов, можно более или менее просто вывести из теоремы А [19] . Это относится к результатам работ[10,II,19,41,42,45,46], также к результа-
ту работы Э.Б.Яворского [23], в которой получен новый критерий I-компонентной 2-клеточной вложимости графа в ориентируемое 2-многообразие.
В 1974 году была опубликована работа Н.П.Хоменко и Н.А.Островерхого [18], в которой теорема А [19] была, в частности, применена к решению вопроса о существовании относительных 2-клеточных вложений. В том же году была опубликована статья Дж.Закса [61], посвященная нахождению максимального рода декартового произведения двух графов. Результаты последней работы перекрывались результатами более ранней работы [ilj .
В 1975 году вышли в свет две работы А.Г.Вентре [.52,53] , содержащие некоторые результаты о максимальном роде графов, блоки которых сверху вложимы и доказательство сверху вложимости графа Грецша. Эти результаты довольно легко выводятся из теоремы А [19].
В 1976 году была опубликована еще одна работа А.Г.Вентре [54] о сверху вложимости графов, блоки которых сверху вложимы, которая, однако, не содержала существенно новых результатов. В том же году Н.Х.Ксуонг опубликовал две работы [57,58] ', в которых (без ссылки на работу [I9J ) была приведена теорема, по существу совпадающая с теоремой А [19], а также некоторые ее следствия.
В 1977 году вышла в свет работа Н.П.Хоменко и А.Д.Глухова [16] , посвященная исследованию сверху вложимых графов, и работа А.Д.Глухова [2J , в которой были построены контрпримеры к некоторым предположениям, высказанным в работе [47], в частности построен пример 3-связного не сверху вложимого графа. В том же году Ф.Жагер, Н.Х.Ксуонг и Ш.Пейан опубликовали работу ІЗЗЗ, в которой анонсировали результаты о максимальном роде одного
- б -
класса кубических графов и о сверху вложимости циклически 4-реберно связных графов, а А.Г.Вентре опубликовал новую работу Г55] об аддитивности максимального рода графов, в которой несколько обобщил результаты, полученные им в работах [52-54].
В 1978 году была опубликована работа Э.В.Яворского [24], содержащая утверждение об однокомпонентной 2-клеточной вложи-мости графов с четным цикломатическим числом и с диаметром не больше двух. К сожалению, доказательство этого утверждения было некорректным из-за применения неверной леммы. В том же году вышли в свет две статьи, содержащие изложение докладов на конференции в Орсее в 1976 году - работа А.Буше [26] , в которой был построен класс 3-связных не сверху вложимых графов и работа Р.Д.Рингайзена [48], посвященная аддитивности максимального рода графов. Результаты последней нашли более полное отражение в работе К.Х.Литтла и Р.Д.Рингайзена [37], которая обобщала также основные результаты работ [53-55]. В 1978 году были также опубликованы работа М.Юнгермана [34], в которой доказывался критерий сверху вложимости связного графа, полученный еще в 1973 году в работе [19], и работа Р.Д.Рингайзена [49] о графах Q , удовлетворяющих условию ]fM (G)-f(G-) ~/
В 1979 году вышел в свет целый ряд работ, посвященных максимальному роду графов. В работе Ш.Пейана и Н.Х.Ксуонга [44] были доказаны результаты, анонсированные в работе [33], а в работе этих же авторов вместе с Ф.Жагером [32] были найдены два новых класса сверху вложимых графов. Н.Х.Ксуонг в двух своих работах [59] и [60] дал развернутое изложение результатов, анонсированных им ранее в статьях [57] и [58] (отметим, что основные из этих результатов были получены еще в работе [19. В статье Ф.Жагера, Ш.Пейана и Н.Х.Ксуонга [31] была найдена новая формула для максимального рода кубических графов,
а в статье [43] последних двух авторов были описаны все графы , для которых jf~M(Qr)~lf(G)~ 1 . А.Г.Вентре в своей работе [56] получил оценку для максимального рода графа, для которого известны максимальные роды его подграфов определенного вида. В работе Лю Янпея [38] для нахождения максимального рода графа применялся подход, развитый еще в работе [21], основанный на изучении эйлеровых циклов в графе Ос/ и получены ранее известные результаты: найдены j/bM(Kn) и f*M (Кт,п) , а в работе М.Е.Арагно [25] доказана сверху вложимость одного класса кубических гамильтоновых графов. Р.Д.Рингайзен в 1979 году опубликовал обзорную статью [50J, посвященную максимальному роду графов. В этой статье получили отражение все существенные результаты зарубежных ученых в области максимального рода, однако, к сожалению, совершенно не были упомянуты важные результаты советских математиков.
В 1980 году была опубликована работа Н.П.Хоменко и А.Д.Глу-хова [17] , в которой наряду с развитым в работах [21] и [19] подходом, основанном на хордовом натягивании, был применен также новый подход к исследованию максимального рода графов. Это позволило авторам найти новую формулу для максимального рода произвольного связного графа и получить эффективную характери-зацию графов с данным максимальным родом. В том же году вышла в свет статья А.Д.Глухова [3], в которой были изучены свойства, введенных в работе [17] .. хордово критических графов.
В 1981 году были опубликованы две статьи Л.Небески [39] и [40] . В первой из них показано, что всякий связный и локально связный граф сверху вложимый. Основным результатом второй работы является теорема о максимальном роде графов, эквивалентная теореме 1.2 настоящей диссертации. Эта теорема впервые
была доказана в работе [17]. В том же году была опубликована работа В.Г.Лещенко [8], в которой доказана теорема об одноком-понентной 2-клеточной вложимости графов с четным цикломатичес-ким числом и диаметром не больше двух. Кроме того, в 1981 году была опубликована работа А.Д.Глухова [5], в которой была развита (примененная уже в работе [I7J ) техника Л- разложений и построен полиномиальный алгоритм нахождения максимального рода произвольного связного графа. В работе [6] А.Д.Глухова эта же техника была применена к исследованию максимального рода плоских графов.
Настоящая диссертация посвящена исследованию максимального рода графов и содержит результаты, опубликованные в работах [2-6, 16,17] . Диссертация содержит две главы, каждая из которых разбита на четыре параграфа.
В первой главе изучаются общие свойства максимального рода графов. Здесь развита техника Л-разложений, которая затем систематически применяется на протяжении всей работы.
В I.I. вводится ряд основных понятий (хордовость, к- разложения и др.) и доказываются утверждения, позволяющие применять 1- разложения к исследованию максимального рода графов. Главными результатами этого параграфа являются теорема I.I. о существовании приведенных А-разложений для любого связного графа, теорема 1.2, дающая новую формулу для максимального рода графа, и теорема 1.4, которая дает эффективную харак-теризацию графов с данным максимальным родом.
В 1.2 изучен весьма важный, с точки зрения максимального рода, класс 0-хордовых графов или графов, вкладывающихся I-компонентно 2-клеточно в ориентируемое 2-многообразие. Здесь доказано утверждение (теорема 1.5) о 0-хордовых факторграфах
данного связного графа, позволяющее свести задачу нахождения максимального рода данного графа к построению некоторой цепочки его 0-хордовых факторграфов, а также утверждения о строении максимальных 0-хордовых факторграфов связного графа (предложения I.I и 1.2 и их следствия). Кроме того, получен новый критерий 0-хордовости связного графа в терминах существования I - фактора в графе базиса циклов данного графа (теорема 1.6).
В 1.3 содержит некоторые результаты о хордово критических графах, которые наряду с 0-хордовыми графами играют существенную роль в теории максимального рода графов. Здесь установлен критерий хордовой критичности графа (теорема 1.7), а также найдены ряд необходимых и достаточных условий хордовой критичности.
В 1.4 рассмотрен вопрос о существенности ребер связного графа относительно максимального рода при удалении из графа или стягивании этих ребер. С помощью Л- разложений описаны
jf- существенные в целом реберные подпространства (предложения 1.9 и I.10) и расположение f- несущественных ребер (теоремы 1.9 и 1.10) в связном графе. Найдены также достаточные условия
f - несущественности ребер по стягиванию в связном графе (предложения I.I2 и I.I3).
Вторая глава посвящена нахождению максимального рода и построению максимальных 2-клеточных вложений графов. Изложение при этом существенно опирается на результаты, полученные в первой главе настоящей работы.
В 2.1 исследуется связь между циклически нечетной реберной связностью (это понятие, обобщающее циклическую реберную связность, было введено в 1.3) и максимальным родом графа. Показано, что любой циклически нечетно 4-реберно связный граф сверху вложимый (теорема 2.1) и найдена нижняя оценка для мак-
симального рода циклически нечетно 3-реберно связных графов. Кроме того, доказано, что случайный граф Onpf р~ t—— » iLtTI OJ(n) =z оо , сверху вложимый с вероятностью f-o(1).
В 2.2 доказано утверждение, позволяющее свести проверку 0-хордовости 2-реберно связного плоского графа G- к проверке критичности графа J (G- , {,^о) межевания 2-клеток вложения f'G~^(% графа G- в сферу б"0 (теорема 2.4). При этом использован полученный в 1.2 критерий 0-хордовости связного графа. На основе этого утверждения построен алгоритм полиномиальной временной сложности для нахождения максимального рода любого связного плоского графа (алгоритм I). Разработан также весьма эффективный алгоритм нахождения максимального рода для одного класса плоских графов -так называемых К VP -графов или параллельно-последовательных графов (алгоритм 2).
В 2.3 построен алгоритм полиномиальной временной сложности для нахождения максимального рода произвольного связного графа (алгоритм 4). Для обоснования этого алгоритма доказан ряд вспомогательных утверждений о введенных здесь однородных Л-разложениях (леммы 2.6 - 2.9). Идея алгоритма состоит в построении такой цепочки Т- F0<^ Ff<=^ ,..<=^ Fm 0 - хордовых факторгра-фов связного графа , что T*G0 , oC'(Fi\f}!i)^Z, L=*f(t)m, m^M(Q). При этом находятся как однородные Л- разложения, так и -разложения (т.е. представления в виде фактордерева с добавленными к нему парами смежных ребер) каждого из графов Fc ,
і- о(1)т . Теорема 2.5 обосновывает правильность и полиноми-альность алгоритма 4.
2.4 посвящен применению полученных результатов. Здесь описаны три полиномиальных алгоритма (алгоритмы 5,6,7), основанных на алгоритме 4. Алгоритм 5 строит максимальное 2-клеточное вложение произвольного связного графа Q- в ориентируемое
- II -
2-многообразие, а алгоритм 6 строит 2-клеточные вложения связного графа G в ориентируемые 2-многообразия 6^ родов У = Уо fl)fM(G) , если задано 2-клеточное вложение этого графа в 2-многообразие бу0 . Оба эти алгоритма задают соответствующие вложения в виде вращений. С помощью алгоритма 7 для кубических графов решается задача о нахождении в графе минимального (по числу элементов) множества вершин, после удаления которого получается граф без циклов (лес). Для случая произвольных графов эта задача, имеющая прикладное значение, является JvT - трудной.
Основные результаты настоящей диссертации можно сформулировать следующим образом.
Разработана техника Х- разложений, позволившая получить ряд новых результатов в теории максимального рода графов.
Получена новая формула для максимального рода произвольного связного графа и дана эффективная характеризация графов с данным максимальным родом.
Исследованы 0-хордовые и хордово критические графы, играющие важную роль в теории максимального рода графов, а также изучен вопрос о существенности ребер связного графа при удалении или стягивании относительно максимального рода графов.
Введено понятие циклически нечетной реберной связности графа и получены результаты о максимальном роде циклически нечетно 3- и 4-реберно связных графов, а также о максимальном роде связного случайного графа.
Решена задача нахождения максимального рода любого связного плоского графа путем сведения ее к задачам теории па-росочетаний.
С помощью техники X - разложений и хордового копредстав-ления (натягивания) графов разработаны алгоритмы полиномиальной
временной сложности для нахождения максимального рода и построения максимальных 2-клеточных вложений в ориентируемые 2-много-образия произвольного связного графа.
Отметим, что полученные в диссертации результаты дают решение некоторых из поставленных в работе 14] проблем в теории вложений графов в 2-многообразия.
Понятия и обозначения, используемые в настоящей диссертации, в основном взяты из работы [15] . Под графом как правило понимается топологический граф, т.е. конечный одномерный CU/~ комплекс G ~С +G , где &, 0-{ - вершинное и реберное пространства графа Q- соответственно. Буква CL {Ucfu' и т.д.) будет всегда обозначать ребро графа От , а буква V (Ui,U и т.д.) - реберное подпространство графа Q . Компонентами связности реберного подпространства V графа Q являются ребра этого графа; число этих ребер обозначается через PQ(U).
Автор благодарит своего научного руководителя старшего научного сотрудника Института математики АН УССР Николая Павловича Хоменко за помощь и постоянное внимание к работе.
- ІЗ -
К- разложения, хордовость и максимальный род графов
В 1.2 изучен весьма важный, с точки зрения максимального рода, класс 0-хордовых графов или графов, вкладывающихся I-компонентно 2-клеточно в ориентируемое 2-многообразие. Здесь доказано утверждение (теорема 1.5) о 0-хордовых факторграфах данного связного графа, позволяющее свести задачу нахождения максимального рода данного графа к построению некоторой цепочки его 0-хордовых факторграфов, а также утверждения о строении максимальных 0-хордовых факторграфов связного графа (предложения I.I и 1.2 и их следствия). Кроме того, получен новый критерий 0-хордовости связного графа в терминах существования I - фактора в графе базиса циклов данного графа (теорема 1.6).
В 1.3 содержит некоторые результаты о хордово критических графах, которые наряду с 0-хордовыми графами играют существенную роль в теории максимального рода графов. Здесь установлен критерий хордовой критичности графа (теорема 1.7), а также найдены ряд необходимых и достаточных условий хордовой критичности. В 1.4 рассмотрен вопрос о существенности ребер связного графа относительно максимального рода при удалении из графа или стягивании этих ребер. С помощью Л- разложений описаны jf- существенные в целом реберные подпространства (предложения 1.9 и I.10) и расположение f- несущественных ребер (теоремы 1.9 и 1.10) в связном графе. Найдены также достаточные условия f - несущественности ребер по стягиванию в связном графе (предложения I.I2 и I.I3). Вторая глава посвящена нахождению максимального рода и построению максимальных 2-клеточных вложений графов. Изложение при этом существенно опирается на результаты, полученные в первой главе настоящей работы. В 2.1 исследуется связь между циклически нечетной реберной связностью (это понятие, обобщающее циклическую реберную связность, было введено в 1.3) и максимальным родом графа. Показано, что любой циклически нечетно 4-реберно связный граф сверху вложимый (теорема 2.1) и найдена нижняя оценка для максимального рода циклически нечетно 3-реберно связных графов. Кроме того, доказано, что случайный граф Onpf р t—— » iLtTI OJ(n) =z оо , сверху вложимый с вероятностью f-o(1). В 2.2 доказано утверждение, позволяющее свести проверку 0-хордовости 2-реберно связного плоского графа G- к проверке критичности графа J (G- , {, о) межевания 2-клеток вложения f G (% графа G- в сферу б"0 (теорема 2.4). При этом использован полученный в 1.2 критерий 0-хордовости связного графа. На основе этого утверждения построен алгоритм полиномиальной временной сложности для нахождения максимального рода любого связного плоского графа (алгоритм I). Разработан также весьма эффективный алгоритм нахождения максимального рода для одного класса плоских графов -так называемых К VP -графов или параллельно-последовательных графов (алгоритм 2). В 2.3 построен алгоритм полиномиальной временной сложности для нахождения максимального рода произвольного связного графа (алгоритм 4). Для обоснования этого алгоритма доказан ряд вспомогательных утверждений о введенных здесь однородных Л-разложениях (леммы 2.6 - 2.9). Идея алгоритма состоит в построении такой цепочки Т- F0 Ff = ,.. = Fm 0 - хордовых факторгра-фов связного графа , что T G0 , oC (Fi\f}!i) Z, L= f(t)m, m M(Q). При этом находятся как однородные Л- разложения, так и -разложения (т.е. представления в виде фактордерева с добавленными к нему парами смежных ребер) каждого из графов Fc , і- о(1)т . Теорема 2.5 обосновывает правильность и полиноми-альность алгоритма 4. 2.4 посвящен применению полученных результатов. Здесь описаны три полиномиальных алгоритма (алгоритмы 5,6,7), основанных на алгоритме 4. Алгоритм 5 строит максимальное 2-клеточное вложение произвольного связного графа Q- в ориентируемое 2-многообразие, а алгоритм 6 строит 2-клеточные вложения связного графа G в ориентируемые 2-многообразия 6 родов У = Уо fl)fM(G) , если задано 2-клеточное вложение этого графа в 2-многообразие бу0 . Оба эти алгоритма задают соответствующие вложения в виде вращений. С помощью алгоритма 7 для кубических графов решается задача о нахождении в графе минимального (по числу элементов) множества вершин, после удаления которого получается граф без циклов (лес). Для случая произвольных графов эта задача, имеющая прикладное значение, является JvT - трудной. Основные результаты настоящей диссертации можно сформулировать следующим образом. 1. Разработана техника Х- разложений, позволившая получить ряд новых результатов в теории максимального рода графов. 2. Получена новая формула для максимального рода произвольного связного графа и дана эффективная характеризация графов с данным максимальным родом. 3. Исследованы 0-хордовые и хордово критические графы, играющие важную роль в теории максимального рода графов, а также изучен вопрос о существенности ребер связного графа при удалении или стягивании относительно максимального рода графов. 4. Введено понятие циклически нечетной реберной связности графа и получены результаты о максимальном роде циклически нечетно 3- и 4-реберно связных графов, а также о максимальном роде связного случайного графа. 5. Решена задача нахождения максимального рода любого связного плоского графа путем сведения ее к задачам теории па-росочетаний.
Существенность ребер графа относительно максимального рода
Следующая теорема дает критерий 0 - хордовости 2-реберно связного плоского графа. Отметим, что произвольный граф является 0 - хордовым тогда и только тогда, когда все его 2-реберно связные компоненты 0 - хордовые ri9j. Граф называется критическим, если для любой его вершины л. граф \ fa/ непримитивен.
Теорема 2.4. Пусть /:- - % - произвольное вложение 2-реберно связного графа в сферу С . Граф будет 0 - хордовым тогда и только тогда, когда граф J f, fi %) межевания 2-клеток вложения f будет критическим. Доказательство. Пусть f : % - произвольное вложение 2-реберно связного графа в сферу Q . Если граф 0 - хордовый, то, в силу теоремы 1.6, для любого его базиса Л циклов граф J{,$) непримитивен. Но, если S -произвольная 2-клетка вложения у , то множество циклов, являющихся границами всех остальных 2-клеток этого вложения, образуют базис Д. циклов графа и J ft3s) J (Є f,0 ) (s). - 58 -Поэтому граф J(G,/Заявляется критическим. Обратно, пусть граф G не является 0-хордовым. Тогда, в силу следствия I теоремы I.I, найдется такое Я- разложение G=G + Аграфа G , для которого выполнено условие: JH(g ) / (V). Будем предполагать, что Я- разложение &= +V выбрано среди всех А - разложений графа G , удовлетворяющих указанному условию так, чтобы число fkfV)было минимальным. Тогда, в силу леммы 2.5, все листы Я- разложения = 2 будут подграфами графа & Вложение f : - - % графа G индуцирует вложение / : ,/ =/L, графа G vi вложение // : % +(% ,//=/\е, каждого листа G/A- разложения G=G/+ir . Зафиксируем некоторую 2-клетку So вложения / , для которой So П V= 0 . Будем говорить, что лист 6; Я- разложения G +ir охватывает лист G,- этого Я- разложения, если лист Gj принадлежит некоторой 2-клетке вложения /t- листа - и & п s9 - ф . Если существуют листы А- разложения G = +.ir , которые охватывают другие листы этого А.- разложения, то выберем такой его лист Gfc , все охватываемые которым листы не охватывают никаких других листов. Пусть з - 2-клетка вложения // листа , которой принадлежат охватываемые листом листы Я - разложения G-G +V. Так как граф G 2-реберно связный, то V = уns 0 Пусть далее і - количество циклически нечетных листов Я -- разложения G=G -f-V , принадлежащих 2-клетке s . Возможны следующие три случая. I) I р (V) . В этом случае для Я - разложения = { + 1/ )+ (У \ V) будут справедливы неравенства которые противоречат выбору Л- разложения G G +V, ибо ро (if ir ) р (У) 2) і =.р0 (и1), в этом случае для А- разложения G = (G +V)-(V\ У ) графа 6- будут справедливы равенства: A» (G + V) = A»(G ) - I =A"f6f) -po (V) , иб0 цикличес кая четность листа А- разложения g -fG -f-V) -fV V ) , содержащего лист G , будет совпадать с циклической четностью самого листа . Поэтому будет иметь место неравенство А ( +и) ро (Tf V) t противоречащее выбору А - разложения =f +V. 3) і рс (V) . В этом случае для А - разложения G- (G \ V ) -V графа будут справедливы неравенства: A (G \ V) / р (Vf) , противоречащие выбору Я- разложения G ffbV , ибо / o(v ) .p,(V) . Таким образом, показано, что ни один лист Л- разложения (r — G +V не охватывает других листов этого Л- разложения. Так как, кроме того, все листы А - разложения G - G V являются подграфами графа , то все 2-клетки вложения // листа с- этого Л- разложения, не пересекающиеся с 2-клеткой So » будут также 2-клетками вложения f графа . Поэтому пространство V целиком лежит в 2-клетке s/ . Следовательно граф J(G , /і&о) (So ) будет подграфом графа ilfg, f4 % &J, где 30 - 2-клетка вложения / , принадлежащая 2-клетке S0/ . При этом граф J(G р &0) \ (ST, ) получается из графа xT(G, /, %) \ (s0) удалением /hfv) вершин, соответствующих 2-клеткам вложения / , не являющихся 2-клетками вложения / и содержит J fG J компонент нечетного порядка. Поэтому, в силу неравенства (& ) ро (V) и теоремы Татта Г5ІІ , граф J(G, f,6 )\(So) примитивен, а значит граф J (6і,/,& ) не является критическим. Отметим, что так как построение графа О (; -fi&o) межевания 2-клеток вложения / плоского графа & в сферу ( и проверку его критичности можно осуществить за полиномиальное время, то по теореме 2.4 проверку 0 - хордовости плоского графа также можно осуществить за полиномиальное время. Опишем теперь алгоритм полиномиальной временной сложностиу находящий максимальный род связного графа & , вложенного в сфе РУ Алгоритм I. Шаг I. В качестве начального 0 - хордового факторгра-фа F графа Q выбрать произвольное его фактордерево. Шаг 2. Пусть F- очередной построенный 0 - хордовый факторграф графа G-. Если oc fC Ff) / , то перейти к шагу 4. Шаг 3. Перебирая все пары и?и ребер графа C F для каждого графа F +и + и строить граф Т межевания 2-клеток вложения в сферу той 2-реберно связной компоненты графа F-+i/- u[ которая содержит оба ребра U, it \ если такой компоненты нет, то продолжить перебор пар ребер. Если граф «7 будет критическим, то прекратить перебор пар ребер, выбрать граф F-u+u в качестве очередного 0 - хордового факторграфа F и перейти к шагу 2.
Циклическая связность и максимальный род графов
Настоящая диссертация посвящена исследованию максимального рода графов и содержит результаты, опубликованные в работах [2-6, 16,17] . Диссертация содержит две главы, каждая из которых разбита на четыре параграфа.
В первой главе изучаются общие свойства максимального рода графов. Здесь развита техника Л-разложений, которая затем систематически применяется на протяжении всей работы. В I.I. вводится ряд основных понятий (хордовость, к- разложения и др.) и доказываются утверждения, позволяющие применять 1- разложения к исследованию максимального рода графов. Главными результатами этого параграфа являются теорема I.I. о существовании приведенных А-разложений для любого связного графа, теорема 1.2, дающая новую формулу для максимального рода графа, и теорема 1.4, которая дает эффективную харак-теризацию графов с данным максимальным родом. В 1.2 изучен весьма важный, с точки зрения максимального рода, класс 0-хордовых графов или графов, вкладывающихся I-компонентно 2-клеточно в ориентируемое 2-многообразие. Здесь доказано утверждение (теорема 1.5) о 0-хордовых факторграфах данного связного графа, позволяющее свести задачу нахождения максимального рода данного графа к построению некоторой цепочки его 0-хордовых факторграфов, а также утверждения о строении максимальных 0-хордовых факторграфов связного графа (предложения I.I и 1.2 и их следствия). Кроме того, получен новый критерий 0-хордовости связного графа в терминах существования I - фактора в графе базиса циклов данного графа (теорема 1.6). В 1.3 содержит некоторые результаты о хордово критических графах, которые наряду с 0-хордовыми графами играют существенную роль в теории максимального рода графов. Здесь установлен критерий хордовой критичности графа (теорема 1.7), а также найдены ряд необходимых и достаточных условий хордовой критичности. В 1.4 рассмотрен вопрос о существенности ребер связного графа относительно максимального рода при удалении из графа или стягивании этих ребер. С помощью Л- разложений описаны jf- существенные в целом реберные подпространства (предложения 1.9 и I.10) и расположение f- несущественных ребер (теоремы 1.9 и 1.10) в связном графе. Найдены также достаточные условия f - несущественности ребер по стягиванию в связном графе (предложения I.I2 и I.I3). Вторая глава посвящена нахождению максимального рода и построению максимальных 2-клеточных вложений графов. Изложение при этом существенно опирается на результаты, полученные в первой главе настоящей работы. В 2.1 исследуется связь между циклически нечетной реберной связностью (это понятие, обобщающее циклическую реберную связность, было введено в 1.3) и максимальным родом графа. Показано, что любой циклически нечетно 4-реберно связный граф сверху вложимый (теорема 2.1) и найдена нижняя оценка для максимального рода циклически нечетно 3-реберно связных графов. Кроме того, доказано, что случайный граф Onpf р t—— » iLtTI OJ(n) =z оо , сверху вложимый с вероятностью f-o(1).
В 2.2 доказано утверждение, позволяющее свести проверку 0-хордовости 2-реберно связного плоского графа G- к проверке критичности графа J (G- , {, о) межевания 2-клеток вложения f G (% графа G- в сферу б"0 (теорема 2.4). При этом использован полученный в 1.2 критерий 0-хордовости связного графа. На основе этого утверждения построен алгоритм полиномиальной временной сложности для нахождения максимального рода любого связного плоского графа (алгоритм I). Разработан также весьма эффективный алгоритм нахождения максимального рода для одного класса плоских графов -так называемых К VP -графов или параллельно-последовательных графов (алгоритм 2).
В 2.3 построен алгоритм полиномиальной временной сложности для нахождения максимального рода произвольного связного графа (алгоритм 4). Для обоснования этого алгоритма доказан ряд вспомогательных утверждений о введенных здесь однородных Л-разложениях (леммы 2.6 - 2.9). Идея алгоритма состоит в построении такой цепочки Т- F0 Ff = ,.. = Fm 0 - хордовых факторгра-фов связного графа , что T G0 , oC (Fi\f}!i) Z, L= f(t)m, m M(Q). При этом находятся как однородные Л- разложения, так и -разложения (т.е. представления в виде фактордерева с добавленными к нему парами смежных ребер) каждого из графов Fc ,
Полиномиальный алгоритм нахождения макси мального рода связного графа
Учитывая, что граф 6- эйлеров, в силу предложения 1.4, достаточно показать, что в нем нет такого циклически нечетного подграфа И , что Р(Н 6х Н)=В. Предположим, что М - такой подграф графа и =N+tf +uf + Hz, %$ П ИФ Ф } ? с-/7 W Ф , г =/, . Тогда граф Н+и , где ди = Н Л C 9uf t/ 9uz) удовлетворяет условиям предложения, хотя в противоречии с вышедоказанным является циклически четным. Таким образом, предложение доказано.
Предложение 1.6. Любой циклически нечетный блок, каждое ребро которого принадлежит циклу длины не больше, чем 3, является хордово критическим.
Доказательство. Пусть 6 - блок наименьшего порядка, удовлетворяющий условиям предложения, но не являющийся хордово критическим. Заметим вначале, что граф 6 3- циклически нечетно реберно связен. Действительно, в противном случае граф 6 можно было бы представить в виде = /+е+и,+г/ , 9ut пб; Ф-0 , hj = ,Z и так как 6- блок, то ребра U y uz не принадлежали бы циклам длины не больше, чем 3.
Таким образом, в силу теоремы 1.8, граф 0- представим в виде & = Qrh&t,fiit-bUzi-u5j ЭисП Фф, = /,2,5, j = /,2 , где 0{ - циклически нечетный граф, а 4 - циклически четный, но не 0-хордовый граф. Так как граф является блоком и каж дое из ребер Ц, и%? и3 должно принадлежать циклам длины не боль ше чем 3, то легко видеть, что с точностью до нумерации эти ребра имеют вид &i = {& &,)7 Ц,-(4 г z), UJ far е) , причем faf i)1 . /, f&zfiz) & 4 . Поэтому граф 47 » где Эй 3f&& z) удовлетворяет условиям предложения, хотя не является хордово критическим, ибо граф - не 0-хордовый. Но это противоречит нашему предложению, так как {&z-ru) Q0/ &). Таким образом, предложение доказано. Следствие. Любой блок, каждое ребро которого принадлежит циклу длины не больше, чем 3, является сверху вложимым. Доказательство. Пусть - блок, удовлетворяющий условиям следствия. Если блок - циклически нечетный, то он в силу предложения 1.6, хордово критический и, следовательно, сверху вложимый. Если же блок С- - циклически четный, то блок +u f du =JU; CL = gf в силу предложения 1.6 является хордово критическим и поэтому блок О- -0 - хордовый, а значит и сверху вложимый. Предложение 1.7. Любой связный реберно-симмет-рический циклически нечетный граф является хордово критическим. Доказательство. Пусть - связный реберно-сим метрический циклически нечетный граф. Так как граф не 0-хор довый, то для ребра и , не принадлежащему максимальному 0-хор довому факторграфу графа , имеет место равенство f/Gw ) — fM(&). Пусть и- теперь произвольное ребро графа . Тогда в силу реберной симметричности графа ff (?\и & ?1и и поэтому откуда в силу теоремы 1.7, следует, что граф & хордово критический. В этом параграфе будет рассмотрен вопрос об изменении максимального рода связного графа при удалении или стягивании ребер последнего. Как и ранее, основным инструментом исследования будут служить Х- разложения. Определение І.ІІ. Циклическое ребро и связного графа называется f - существенным, если f few) - (2)-1 и / -несущественным, если fM{G u) -=/ мґ)% Отметим, что в силу леммы I [19] любое циклическое ребро связного графа является либо f - существенным либо / - несущественным. Определение I.I2. Реберное подпространство V связного графа Q , Do (G \ V) - 1 называется / - существен ным в целом, если г-1 (ff\Tf) -{"fG) - ро (и) , и f"- несущественным в целом, если fM (б сг) =у (g). Определение I.I3. Пусть bv и = +& - два Л -разложения связного графа G , f/jf - множество листов первого Л- разложения. Будем говорить, что Л - разложение Q.= G +V подчинено Я- разложению G — P -fV , если V l/ и что J- - разложение = 7 слаб о подчинено Л - разложению G. = в + Vі , если If с Gf\ U ( ) . В дальнейшем понадобится следующее тривиально доказываемое утверждение. Лемма 1.6. Л- разложение = +V ТОгда и только тогда слабо подчинено Л - разложению - рафа, которое эквивалентно А- разложению (r-O +V. Следствие. Если два Я- разложения связного графа (слабо) подчинены друг другу, то они эквивалентны. Следующие утверждения устанавливают связь между экстремальными А- разложениями связного графа и его / " существенными в целом реберными подпространствами. Предложение 1.8. А - разложение - +V связного графа Q- является экстремальным J. - разложением, все нетривиальные листы которого хордово критические тогда и только тогда, когда V - максимальное по включению / - существенное в целом реберное подпространство графа г . Доказательство. Пусть G- G- +V - экстремальное А- разложение, все нетривиальные листы которого хордово критические, связного графа G . Тогда, в силу следствия I теоремы 1.1. core/fa) = Л н( 0-ро( V) и так как core/( )= =J" Ґ4 ) , то f"fff ) = Г"ҐЄ)-/ f0 . Поэтому V- / - существенное в целом реберное подпространство графа -. Пусть V - / - существенное в целом реберное подпространство графа и V lf . Рассмотрим А- разложение G = +V . Согласно выбору пространства V имеет место равенство / " (Є ) - f-Mf)-р fV j\ а значит и равенства со rot(Є ) = cord fff) + po (г/ ) } CordfG ) j"(e ) -po (V) +po (V ) =AH( ) +f o [V N v). С другой стороны, в силу леммы I.I, справедливо неравенство.
Похожие диссертации на Исследование максимального рода графов
