Теоремы о продолжении З-раскрасок плоских графов и интервальные раскраски графов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

АКАДЕМИЯ НАУК СССР ОРДЕНА ЛЕНИНА СИБИРСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ

На пранах рук леи

УШ 319.17 1

АКСЕНОВ Валерий Алать-.ьович

ТЕОРЕМЫ О ПРОДОЛЖЕНИИ З-РАСКРАСОК ПЛОСКИХ ГРАГ08 И ИНТЕРВАЛЬНЫЕ РАСКРАСКИ ГРАДОВ

(Специальность: 01 01.09 - математическая кибернетика)

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

Новосибирск - 1990

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

Научный руководитель:

кандидат физико-математических наук, доцент Мельников Л.С.

Офиадапьи. ) оппоненты:

• доктор фИЕ':ко-математичоских наук Тышкевич Р. И.

кандидат физико-математических наук Евстигнеев В.А.

•

Ведущая организация:

Вычислительный центр г )бирского отделения АН СССР

Зашита состоится ••_*• __19°о г. в _. часов на

заседании Специализированного совета К.002.23.01 в Институте математики СО АН СССР С630090, г.Новосибирск-90, УНисе^»итотский пр., 4, Институт математики >.0 ' ' СССР}.

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

Ааторэфорат разослан _;_1990 г.

Ученый секретарь Специализированного совета, кандидат <риз. -мат. наук

Ю. П. Васильев

ОБЩАЯ Х/ФЖ1ЕРИСТИКА Р/СОШ

Актуальность '-ом». Тома работы связана с задачей, раскраски графоь,» которая является одчой иг? основных г» т< ри графов. Это обусловлено тоской си"^ью проблемы поиска минимальном раскраски с рядом важных прикладных задач Практически I ая задача, в оторой тро^уотся найти оптимальное время выполнения нокоторой работь., допусчощой разбиение оо на аломоитарпью действия, на которые наложены "условия несовместимости" Сневозможности одновременного выполнения), может быть представлена соответст ацей задачей раскраски графов.

В диссертации раес матг" заютс я три задачи задача 3-раскраски плоских графов, ддача однозначной 3-раскра< , плоских графов и задача интервалы < раскраски гоношенных графов. Все они принадлежат классу полиномиально полных задач, поатому их исследование велось в отравлении изучения взаимосвязи различных числових и структурных характеристик. Основою речультаты, представленные в предлагаемой рас../ге, объединяет мотод, с помощью которого они получены. Этот мотод ножио назвать мотодом продолжения раскраски, и суть его сводится к тому, что изучаются условия, при ко ,рых правильную раскрась, вершин .. .«оторой части графа можно продолжить на весь граф Сто ость достроить до г шильной раскраски всего графа).

Исследованиям, относящимся к этому кругу вопросов, посвяшрны работы Д. Голлора, м Голунбица, В. Гроциа,

Б.Грюнбаума, И.Г.Дмитриова, Л. С. Мельникова, - П.Хавола, <¥. Харарии, Г.Чартронда, и других.

Цель работы:

1. Изучение структурных свойств плоских З-раскратваомик и однозначно 3-раскрашиоаемых графов.

2. Получение оценок интервального - матичоского числа ювоиюнного графа.

Научная новизна.

1. Дано правильное доказательство' изпостной тео)>емн Грюнбаума о достаточных ус ж чх З-раскрашиваемости плоских рафоп.

2. ,. Получено полноо описание графов ч 3-раскрасок гран' нопродолжаемых иа весь граф С полное описание KOHTtip'tMOfioEi к ранее еушретповашю^у доказательству теоремы ' Г'рюпбаума),

На оснойо изучения свойств графов, содержащих хроматически с.нязннэ вершины, дано обг^чонив и усиление необхс- чмых условил однозначной раскрашииаомости плоских графов, pa.i-.o полученных друх'ими авторами.

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

Научная и практическая цонность.

бота имоот теоретическую направленность. Полученные розу ль i имеют конструктивны? доказательст . которые могут быть положены и основу полиномиальных алгоритмов решения конкретных задач, кроме того, испол (уемый мо,од продолжения раскраски м .от 6. сь предложен для .решения Д1 гих задач ,'оории графов.

/апробация работы.

Результаты, представленные в диссертации, докладынались на III .всесоюзном совещании "Методы и про, ра <ы решения оптимизационных задач на графах и сетях" (Ташконт, 1984), VII Всесоюзной конференции "Проблемы теоретической ю орнотики" СИркутск, 1УУ5), 20-ом и 33-ем Международных математических коллоквиумах СГ1Р, Ьльмопау, 1985, 1988), 1В-ом Коллоквиуме» математического общества им. Я .ольяи С ВНР, Кестхой, 1976), г -•союзных пколах по применению тоорь.. графой я исследовании больших систем СВильяндии, 19' "; Пущине, 19??), на семинарах по дис:1' тной 'атематико в ".Одессе С1974), а также на сем!* чрах "Дискретный анализ" и "Экстремальные з ¡.ачи на графах" Института математики СО АН СССР.

Публикации. По теме диссертации „публиковано 12 печатных работ.

Структура и объел работы

Шсеортация изложена на 91 страницах машинописного те ко та. Сс хчит из i. одоии^ трех глав И списка литературы, . -одержавшего 49 наименование,;

СОДЕРЖАНИЕ РАБОТЫ

Во ппсдонми дан краткий обзор работ по тематико диссертации и сложено содержание работы.

Г', диссертации используется тор. апология, шюдопная в книгах Л. Л. Зыкоаа "Теория графой" СН1в9> и 'Т. Харлри "Тооря грае,«!)" С5973.

В гюриом параграфе г пата 1 доиопи'лтоиьно ш чятся следующие понятия: {-гранью и ¿-циклом назьшоются соотпотствонно гргшь и цикл, содержали© в с по он границе £-ро6ор; С(У,Е>-граф, гдо V - множоство I шин, а К -миожостпо ребор. При правильной раскраско в три цпота перни.л 5-грани дно пары поршин окра'' чы и доа цвета и 1,на - п тротий. Си га будот иа-зыпа п,ся г. поциальной, а роб, , протиооположноо о той ооршино, - спо лытм ребро' Грань, на которой поданы цг'ота. будот насыпаться отмоченной. Величины п(О'), т(С), 1(0) и а(х) будут обозначат) оотвотстпонно число норшин, робор, 3-циклов п графе О и степень вершин:.' х. Множество м будет обозначать множество плоских графой, содержащих только 3-, Л- и 3-грани и но болоо трех 3~цикл<и; 1в - множоство плоских, графоп, содержащих только 3-, и

'З-грани но болоо о.у хо 3-цикла и отмочонную грань; ч множоство плоских гр.^ро», содер. лцих только 3-, 4- и 3-грани, и равно один 3—цикл, имеющий общоо специально' ребро с отмоченной 5-гранью. В случао, если граф С принадлежит множостпу € и имоот 3-грань У, отличную от отмеч^ .ной, будок, говорить, что она имоот выделяют 4-цикл, осли в С существует такой разделяющий 4-цикл, что 3-дикл и отмоченная 3-грань лежат о одной ого компоненте, а ,3-грань Р - в другой. Множество грае,о!! из С, у которых каждая !>-грань, отличная отмоченной, имоот выделяющий 4-цикл, будем обозначать чороз П.).

Параграф 2 гпапн 1 поспащсн доказательству слодующ->и тооромы о продолжении раскраски:

Теорема ). Пусть 6- плоений сраф, тогда:

a) если О А. то С - З-раекрашиваим;

b) если СЛ1ГЛС. то любую рек», и-.ку отмеченной грсвш. люто продо.ипжъ »га весь ерагр.

Из теоремы 1 легко ы каот справедливость ияпостной

теоромы Грюнбаума < "Если в плоском граф. не более трех ,'J'ifj гоЗ. то он З-раскрашиваеж''), доказатольстно которой, опубликованное о 1963 году, содержало ряд ошибок, обнаружен!! ix лишь в. 1972 году.

Г? параграф« 3 .лапы 1 продолжено рассмотрение успоиий продолжаемости р;»скраски с грани графа G. "эорома 2 содержит нообх имыр и • достаточные споиия непродолжаемости 3~раскраски с некоторой З-гранИ.

Тоорома 2. 'ушь в графе С,, принадлежашол С нет раздели-хщхс 3-цшс"<Я. Заданную на атжгчаююй spat tu pacicpacicy нельзя ь^оболхшь на весь граф тогда и только тогда, когда Gell).

Дальнейшее развитие проблемы трох красой было связано с попыткой доказать зависимость З-раскрашшмомости плоского грае от расстояния между 3-циклами - d(G). Б атом напран.' ии И.Ханелом были построены дг-«. примера не 3-раекрашиваемых графов с d(G)"i и d(G)~2.

В заключительном, четвертом пар графе г/к а 1 построено несколько ( :конв' jx серий но З-раскршшшаемы- графов с >асстояниом между 3 иклами, равным 1, 2 и 3. Кроме того, в этом параграфе построены примеры гр. . jb, опровергающие гипотоэу Х.Закса о структуре не З-раскрашиваемых графов с d(G)* 2. Показано, что в основе всох • -»строенных не З-раскрашиваэмых графов, лежат так называемые "ю ,и-вершины" и "квазя-робра . то ость графы, у которых в любой правильной 3-раскраско две выделенные вершины, лежащие в о д.. ой грани, охрршены одним И соответственно разными цветами. Доказана минимальность нокотрых квази-'-обер (для (1(G)™\, d(G)-2).

Глава 2 посвящена однозначно 3-р ¡сращиваемым графам.

В параграфе 1 этой глав" продолжено изучение свойств квази-i .шин. Годится более общее понятие: 3-хроматически свяг"ых вершин, то есть таких вершин Сне обязательш лежащих в од.а)й грашО, которые в любой правильной 3-раскраско графа окрашены одинаковым цветом. Ос >энои результат итого параграфа следующий:

Теорема 3. Если я плоском графе G имеются 3-хроматически, связные ßtушасы, то L (G)±2.

Эт<-1 т«орема олобщаот полученныо раноо Чартрендом И Гелкчром j. .'ультать. j своГ вах однозначно 3- раскрамныаомых

графов, поскольку ï побом oj означнс "i-pacкрашиваемок граф« n(G)>3 содержится пара 3-хроматически связных i римг

Д><я доказательства теоремы S -ользуется следующей. Teopoi . о продолжении:

Теорема 7. Пусь в тираном графе имеются и.алько 3-, 4- и ñ-грата и пусть мобая 3-раснраска некоторой грана S яри продолжении на весь граф оФюзнсеию задает цвете 8ej 'хкы о, £>o*S, тогда 1 7)>1. "

Во втором параграфе главы 2 дань уск ения результатов Чартренда И Геллера для or >зн -'но З-раскпашваомых грэг ч.

Теорема 8. Если G - однозначно 3-раснраши£авлый. rua^.atü граф и n(G)z4, то /¿2¿(G)+2, где a(G)-m(G)~Pn(G)+3.

Теорема 9. 1 ли G одна: jhho 3-раскрашЫ^,-jmti граф и тц0)>5, то t(G)i:3.. . - " V

В основе доказательств :-чх торем - использованы мощностные оценки. ' .

Теорема 10 вместе с Тооро ~й 15 , доказанные з атом же параграфе, дают полное описание ' плоских одиозна' ю З-ргкжряшиваемых графов, содержащих ровно три 3-цинла, а имен" i доказано, что такие графы всегда содержа''' вершину ; степени 2. Доказательство этих теорем существе, .о оазируетег на теоремах о продолжении, докзк. иных в главе Î. ' ,

Глава 3 посвяшрна интерпальной раскраске гпафов. Б порвем-.

параграфе вв> .ятса дополнительные определения. b~«<ei иным

рафом (G,u>) называемся граф вершинам которого приписаны

неотрицательные числа ч>(х). Правильным интервальным.'

представпе. to и взвоыонного . афа (G,w) на' -павте«. ' фуикцка R, '

котор;«1 каждой вершине . ,т графа ставит соответствие

yaitpi ьй интервал R(x) H" число! й так, что ..ля всех

fx.y.'cñ выполняется: IR(x)(\R(ij)\*-'k Длиной чнторш .ьного

представления называется величина 1 О Ri'x) I, а ин-ерв.здьн^

хеУ

хроматическим числом - xl'G.w) ~ минимум этой величины, взятый

по всем '"'lanHrihHMM интерь 1ьным предсть лониям.

Пуст») p(G,w) - max т(К), где максимум ->рется по всом ЯьО

полным подг; рам К графа С, функция весов и> наэынае 4.,» совершенной, если для всякого подгр<"*а Я вс. о 7>(í',w).

В параграфе 2 главы 3 вводит'"'., понятиь сюпени-

- ? -

соворшонс.' i грана • . Так называется величина

' in ю(х)

■ Х-Л'

p(G)'-iíuix------,

', • ' w max т(х)

х- V

.гцо максимум ошс-кшиа дни" i наименьшего интервала к длине ■ аиболыиого берется по исом со. иионг-'и функциям w.

(X-,í;oi...o:m розуль гатом утого napai рафа являет с ворхияя одр 'а хроматического числа графа чороз ого плотность- v(G) И стон'лш госоршшяуп

Тес ма_2'~' x(G)-p(GJ<r(G).

Далее в этом параграфе вычислены ' значения слово. сс ^ршонстпа дл; uokotoi ч классов графов.

В параграфе 3 гл;шы У дана сорхияя оцонкя и ороального хроматичоского числа через вое самой тяжелой окрестности

ворш1 -i:

Теорема!?.. x(G,\o)'-&(G,w), trK- Z(C,m)*= max(v>(H(x))m(x)),

-----.ZteV

a N(x) - лаюхоапво ^гтш в G апюжсых ex.

!' 'азатсльстио ьмой тооремы конструктивно И используот в . качостно основы вспомогатопьную тоорсму о продолжении интервальной раскраски с нутренНе устойчивого множества на

ЬОСЬ Г, ,1.

Тоорома 14. Д.ы jooüoho )tci того ónymptjHiie устойчивого лдюхества A spctfxi G суирхяпвует . прабилыюе проОатипльпаю R графи G, илтхузв слсдухк, - свойства: a) Tt(x)=\ O.mWI, дли всех х-:А W • 11(G)\?~'(г:,и>).

Amиригмично^ть доказательства теоромы 14 используотся в параграро 3 этой главы для построен' ч полиномиального алгоритма приближенно решения задачи гоории распис. ли,, июстиой под названием "opon shop ргоЫит", то ость задачи обработки }{ деталей на I станка; ири заданном времени обрабс и í-ой дотали на j-om станке - í . и произвольном порядке оЬрл'. . ки цстыюи на танках. Раноо бы) показано, что ота задача при ТгДгЗ принадлежит классу полиномиально полных. Предложенный алгори: дает решение, но болое чом в два раза отличакядоося от оптимального .за 0(k-1 ■ min(h, I i) шагов. ,

По tomo диссср1.",ии oiiyt ¡кованы педукхдао рабУго:

1. Аксенов В. Л. О продолжении 3-pac,(pach на плоских графах. - со. Дйекро-шый ар"<лиз, 1974. гмм. 2N, с.3-19.

2. ">Jccoiioi¡ В.Л. Связна;. pat i^cica плоски- гра<1 Материалы XII1 Всо<~"чозной ..аучной студончоскс. конкуренции, Новосибирск, 1975, с.29-30.

3. Аксенов В. А. Хроматически-связные воршш. г плос к графах,- сб. 4годы дискретного анализа в теории управляющих систом, 1977, Вып.31, C.5-1S.

4. Аксенов В. A. Conopi ннь^ взвопюннио графы,- 7 исы докладов III Всесоюзного совещания "Методы и ирогр«... .¿ы решения оптимизационн задач на графах и сетях", Ташкент,

1 Р°4. >'

5. Аксенов В. А. Степень совершонства графа,- сб. >1отоды . дискретного анализа в изучении ре; заци аогичоских функпий, 1984, Вып.41, с.3-11.

R. Аксенов В. А. Об одной зерхней оценке хромагичоской длины взвешенного графа,- 'Гозж-ы доя- 'Доп VII Всесокгч i конференции "Проблемы теоретической киоернетики". Иркутск, 1Ж5.

7. Аксонов В.А. Обобщение иокоторых одонок . рематического числа графов. - 30 Г ni ern. VÍ1;;-j. ,.Л1. TU Ilmenau., ÍÜSS, F, с.3-D.

8. Аксенов В. А. Полиномиальный алгоритм приб. яе'-'ого Г 'пения одной задачи ->ории- расписаний,- с.б. "Управляемые системы", 198В, Выл.28, c.ö-11.

П. Акссов В. А. Полинок чльный алгоритм ц.иближошюго решения одной уадачи теории расписаний.- - .^3 ritern. Wise. Kol 1. "Н Ilmenau, 1988, С2, 'с. i Л" 445.

10. Airol onov Y.Л. Orí v.a1quoly 3-color «ole planer gr. .hs.-Diccrote Maitiemail es, 1977, .20, c. 2 ,-216.

11. Akstonov V. A., Moi'nllcov L.S. Esso on t.tw .no:- the three-color problem.- 18 СЫ1. Math. S-X" J. Bol y al. 197В, с. 23-34. "* .

12. Akslonov V. А., Mol'ntkov L. S, Sorm. cont or example? asroclatecf w/ .n i he ('"-ee-col problem,- J. of CoKiblii. theory, 1980, 28B, n.i, c.l~9. , í '

• p.-K^nJ:

g -