Задачи раскраски инцидентеоров и их приложения тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Пяткин, Артем Валерьевич

• Пяткин, Артем Валерьевич
• кандидат физико-математических наук
• 1999

Оглавление диссертации кандидат физико-математических наук Пяткин, Артем Валерьевич

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ

ГЛАВА 1. Исходная задача

1. Задача раскраски инциденторов

2. Примеры задач раскраски инциденторов

3. Содержательная постановка исходной задачи

4. Математическая модель исходной задачи

5. Первый алгоритм решения исходной задачи

(алгоритм А\)

6. Второй алгоритм решения исходной задачи

(алгоритм Аг)

7. Приближенный алгоритм меньшей трудоемкости

ГЛАВА 2. Варианты исходной задачи

8. Случай произвольных пропускных способностей

9. Задача с двумя сеансами

10. Случай ограниченной памяти

11. Доказательство гипотезы Визинга-Мельникова

в двух частных случаях

11.1. Случай малой степени ориентированной части мультиграфа

11.2. Случай малой степени мультиграфа

12. Обобщение исходной задачи

13. Задача равномерного распределения информации между т центральными ЭВМ

13.1. Постановка задачи

13.2. О приближенных алгоритмах решения

задачи о камнях

ЗАКЛЮЧЕНИЕ

ЛИТЕРАТУРА

з

Введение диссертации (часть автореферата) на тему «Задачи раскраски инцидентеоров и их приложения»

Введение

За последние сто лет дискретная математика в целом и теория графов в частности претерпели бурное развитие. Это прежде всего связано с ростом приложений дискретных математических моделей в различных областях науки и техники.

Среди задач теории графов особо можно выделить задачи раскраски (окраски) графов. Под раскраской понимается отображение множества объектов раскраски во множество целых положительных чисел [цветов). Объектами раскраски, как правило, являются вершины графа, его ребра или объединение множеств вершин и ребер. Соответствующие раскраски называются вершинными, реберными и тотальными. В зависимости от налагаемых ограничений различают правильные [7,10], предписанные [14,22,29], дистрибутивные [4] и многие другие раскраски. Наиболее известны и хорошо изучены правильные раскраски, в которых нужно использовать наименьшее число цветов, так чтобы при этом никакие два смежных или инцидентных объекта не были окрашены одинаковыми цветами Это наименьшее число цветов называется в зависимости от объектов раскраски вершинным, реберным или тотальным хроматическим числом графа. Заметим, что

правильная тотальная раскраска графа должна включать в себя как правильную реберную, так и правильную вершинную его раскраски.

Теоретическую оценку алгоритмической сложности различных классов задач дает теория NP-пoлныx проблем, основанная Куком [11] и Карпом [9]. В этой теории рассматривается класс КР задач распознавания свойств, разрешимых за полиномиальное время недетерминированной машиной Тьюринга, и класс Р задач распознавания свойств, разрешимых за полиномиальное время детерминированной машиной Тьюринга.

В классе № выделяются так называемые ИР-полные задачи, к которым полиномиально сводится любая задача из КР. Под полиномиальной сводимостью задачи А распознавания свойств к задаче В понимается существование полиномиального алгоритма построения по исходным данным любой индивидуальной задачи /д данных некоторой индивидуальной задачи 1в, причем каждая индивидуальная задача /д имеет ответ "да"тогда и только тогда, когда соответствующая ей индивидуальная задача 1в имеет ответ "да". Следовательно, полиномиальный алгоритм решения КР-полной задачи может существовать тогда и только тогда, когда Р=№. Обширный список ЫР-полных задач приведен в книге Гэри и Джонсона [5].

Оптимизационную задачу называют ЫР-труднощ если к ней полиномиально сводится некоторая КР-полная задача. Основной вывод из этой сводимости заключается в том, что существование полиномиаль-

ного алгоритма хотя бы для одной NP-трудной задачи влечет существование такого алгоритма для всех задач из NP, и, следовательно, P=NP.

Многие из оптимизационных раскрасочных задач, в том числе задачи вершинной и реберной раскраски графов, являются NP-трудными [5],[24]. Можно выделить два подхода к решению таких задач.

Первый подход заключается в построении приближенных алгоритмов. Обозначим через Fa(I) значение целевой функции индивидуальной задачи I, найденное некоторым алгоритмом А, а через F*(I) — оптимальное значение целевой функции. Алгоритм А имеет абсолютную погрешность к, если

sup I F*(I) - Fa(I) |= i

и относительную погрешность £, если

supl (F'(I)-FA(I))/F'(I) \=е.

I

Аппроксимационной схемой называется алгоритм А£, который по входу (1,е) выдает приближенное решение индивидуальной задачи I с относительной погрешностью не превосходящей е.

Второй подход к решению NP-трудных задач заключается в выделении более простых, чем общая задача, подзадач. Прежде всего речь идет о полиномиально разрешимых подзадачах. Например, NP-трудная задача реберной раскраски графов (Хойлер [24]) допускает полиномиальное решение на классе двудольных графов [8,30]. Но иногда выделение подзадачи оказывается полезным даже в том случае,

если сама выделяемая подзадача продолжает оставаться КР-трудной. Так, упомянутая выше задача реберной раскраски графов получается ограничением задачи вершинной раскраски графов на класс реберных графов (т.е. является подзадачей последней). Но в то время как для раскраски вершин графа не существует алгоритма с заданной абсолютной погрешностью (если Р^ [5], то для реберной раскраски такой алгоритм существует [1-3]. Это алгоритм Визинга, строящий решение, не более чем на единицу отличающееся от оптимального (для мультиграфов абсолютная погрешность не превосходит мощности максимального мультиребра).

Для некоторых КР-трудных задач с числовыми параметрами также можно предложить точный алгоритм, время работы которого ограничено полиномом не только от размерности задачи, но и от значений числовых параметров. Такой алгоритм называется псевдополиноми-алъным. Например, псевдополиномиальным алгоритмом является метод динамического программирования для решения таких задач, как РЮКЗАК, РАЗБИЕНИЕ и некоторых других [5,16].

Описанная выше терминология будет использоваться в дальнейшем на протяжении всей диссертации.

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

книге Йенсена и Тофта [26], которая посвящена описанию раскрасоч-ных задач и их приложений.

В диссертации исследуются задачи раскраски объектов, ранее в теории графов практически не расматривавшихся. Это инциденторы, или "половинки дуг". Формально инцидентор определяется в ориентированном графе как упорядоченная пара, состоящая из вершины и инцидентной ей дуги. Первоначально этот термин был введенн Зыковым [7] для обозначения элементов множества V х Е. В последствии он был предложен Визингом и Мельниковым [35] вместо применяемого ранее автором диссертации [42] термина "полудуги".

При постановке задачи окраски инциденторов можно учитывать два типа ограничений. Во-первых можно налагать условия на цвета инциденторов, имеющих общую вершину. Этот тип ограничений в диссертации не варьировался — во всех рассматривавшихся задачах требовалось, чтобы любые два инцидентора, имеющие общую вершину, были окрашены в разные цвета (условие правильности раскраски инциденторов). Во-вторых, можно устанавливать ограничения на цвета двух инциденторов одной дуги (условие допустимости раскраски инциденторов). Различные вариации этого типа ограничений позволяют создать обширную гамму задач инциденторной раскраски.

Задача окраски инциденторов заключается в построении правильной и допустимой раскраски инциденторов некоторого ориентированного мультиграфа в наименьшее число цветов.

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

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

Примерами рассматривавшихся в диссертации сетей могут являться широкополосные цифровые сети, активно разрабатываемые в США, Японии, Канаде и ряде стран Западной Европы начиная с середины 80-х годов. Для них характерна иерархичиеская организация с высокой пропускной способностью каналов связи верхнего уровня и звездной структурой подключения абонентских терминалов нижнего уров-

ня. Создание таких сетей стало возможным благодаря появлению быстродействующих микропроцессоров и дешевого волоконно-оптического кабеля. Более подробно с широкополосными сетями можно ознакомиться в работах Лазарева [12], Захарова [6] и других авторов [21,23].

Диссертация состоит из введения, двух глав, заключения и списка литературы.

В главе 1 формулируются основные изучаемые в диссертации задачи. Во-первых, это формулировка задачи окраски инциденторов ориентированного мультиграфа (раздел 1) и примеры, демонстрирующие уже решенные задачи окраски инциденторов (раздел 2). Во-вторых, это исходная задача оптимизации расписания передачи сообщений в локальной сети связи, различные вариации которой рассматривается во всей остальной диссертации. Содержательная постановка исходной задачи приведена в разделе 3, построение математической модели — задачи окраски инциденторов — производится в разделе 4. Наконец, завершают главу 1 два алгоритма решения основной задачи (в ее теоретико-графической постановке) в разделах 5 и 6, а также некоторые соображения по снижению трудоемкости этих алгоритмов в разделе 7.

Глава 2 содержит различные варианты основной задачи. Все разделы кроме последнего построены по сходной схеме: содержательная постановка задачи — задача окраски инциденторов — полученные результаты. Не перечисляя все рассматривавшиеся в главе 2 задачи,

отметим лишь, что в этой главе особенно ярко проявилась удивительная гибкость математической модели. Такие разные вариации, как ограничения на память (раздел 10), ограничения на способы передачи информации (разделы 9 и 11), наконец, ограничения на саму структуру сети связи (раздел 12) — все они укладывались в рамки задачи окраски инциденторов! И лишь в последнем, завершающем главу 2 разделе 13 сформулирована задача, для которой этих рамок оказалось недостаточно. Оказалось, что для того чтобы свести задачу равномерного распределения информации между т центральными ЭВМ к исходной задаче, необходимо предварительно решить задачу о камнях, для которой приводится анализ аппроксимационных схем и алгоритмов ее решения.

Основные результаты диссертации сформулированы в заключении. Завершает диссертацию список использованной литературы, включающий 46 работ.

Основные результаты диссертации докладывались на семинарах Института математики СО РАН по исследованию операций, теории графов, дискретным экстремальным задачам, избранным задачам комбинаторики, семинаре Института вычислительной математики и математической геофизики по моделированию и оптимизации коммутационных сетей, а также на конференции ШРШМ-96 (Новосибирск, 1996), Первой научной молодежной школе по дискретной математике и ее приложениям (Москва, 1997) и Второй научной молодежной шко-

ле по дискретной математике и ее приложениям (Нижний Новгород, 1998). По материалам диссертации опубликовано 5 работ.

Автор выражает искреннюю благодарность своему научному руководителю Ерзину А.И., а также Бородину О.В., Дементьеву В.Т., Косточке A.B., Мельникову JI.C. и Шамардину Ю.В. за всестороннюю помощь и поддержку в работе.

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Пяткин, Артем Валерьевич

Заключение

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

Основными результатами работы являются:

1) Формулировка задачи раскраски инциденторов, что является новым направлением в задачах теории графов.

2) Постановка исходной задачи минимизации времени передачи информации в локальной сети связи и разработка алгоритмов ее решения путем сведения исходной задачи к задаче раскраски инциденторов (теорема 1).

3) Вывод необходимого и достаточного условий для решения варианта исходной задачи с двумя сеансами (теоремы 2 и 3).

4) Доказательство гипотезы Визинга-Мельникова о раскраске смешанных мультиграфов [35] в двух частных случаях (теоремы 5 и 6).

Список литературы диссертационного исследования кандидат физико-математических наук Пяткин, Артем Валерьевич, 1999 год

Литература

1. Визинг В.Г. Об оценке хроматического класса р~графа // Дискретный анализ. Сб.науч.тр. Новосибирск, Ин-т математики СО АН СССР, 1964. Вып.З. С. 25-30.

2. Визинг В.Г. Хроматический класс мулътиграфов // Кибернетика. 1965. N 3. С. 29-39.

3. Визинг В.Г. Критические графы с данным хроматическим классом // Дискретный анализ. Сб.науч.тр. Новосибирск, Ин-т математики СО АН СССР, 1965. Вып.5. С. 9-17.

4. Визинг В.Г. Дистрибутивная раскраска вершин графа// Дискретный анализ и исследование операций. Новосибирск, 1995. Том 2, N 4, С. 3-12.

5. Гэри М., Джонсон Д. Вычислительные машины и труднорешае-мые задачи. М.: Мир, 1982.

6. Захаров Г.П. Возможности создания широкополосных цифровых сетей электросвязи // Электросвязь, 1992, N 8.

7. Зыков A.A. Теория конечных графов. Новосибирск: Наука, Сибирское Отделение, 1969.

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

9. Карп Р. Сводимость комбинаторных проблем // Кибернетический сборник. М.: Мир, 1975, Вып. 12, С. 16-58

10. Кристофодес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978.

11. Кук С. Сложность процедур вывода теорем // Кибернетический сборник. М.: Мир, 1975. Вып. 12. С. 5-15

12. Лазарев В.Г. Интеллектуальные цифровые сети. Справочник. М.: Финансы и Статистика, 1996.

13. Сердюков А.И., Михайлова И.П. К задаче о камнях// В кн.: Вычислительные методы и программирование. Сборник трудов. Новосибирск, 1975. С. 158-168.

14. Bollobas В., Hind Н. A new upper bound for the list chromatic number// Discrete Math., 74 (1989), p. 65-75.

15. Castanga F., Prins G. Every generalized Petersen graph has a Tait coloring// Pacific J. Math. 40 (1972) p.53-58.

16. Dantzig G.B. Discrete-variable extremum problems// Operations Res. 5, 1957, p. 266-277.

17. Fiorini S., Wilson R.J. Edge-coloring of graphs. Pitman Publishing Ltd, London, 1977.

18. Fischetti M. Worst-case analysis of an approximation scheme for the sub set-sum problem/ / Oper. Res. Lett., 1986, v.5, no. 6, p.283-284.

19. Fischetti M., Martello S. Worst-case analysis of the differencing method for the partition problem// Math. Programming, 1987, v. 37, no.

1, p. 117-120.

20. Fischetti M. A new linear storage, polinomial-time approximation scheme for the subset-sum problem// Discr. Appl. Math., 1990, v.26, no. 1, 61-78.

21. Fisher D.G. The European Route to Integrated Broadband Communications // Proceedings of 2nd IEE National Conference on Telecommunications, York, April, 1989.

22. Galvin F. The list chromatic number of a bipartite multigraph// J. Combin. Theory, Ser. B, 63 (1995), p. 153-158

23. Goldner E-H., Hermann H., Scholtz J. Broadband Communication on the Test Bench// Telcom Report International, 1995, v.18, no. 1.

24. Holyer I. The NP-completeness of edge-coloring // SIAM J. Comput., 1981, v.10, no.4, p. 718-720.

25. Ibarra O.H., Kim C.E. Fast Approximation Algorithms for the Knapsack and Sum of Subset Problem,// J. Assoc. Comp. Mach., v. 22, no. 4, October 1975, p. 463-468.

26. Jensen T.R., Toft B. Graph coloring problems. John Wiley & Sons, Inc., 1995.

27. Johnson D.S. Approximation algorithms for combinatorial problems// Journal of Computer and System Sciences, 9 (1974), p. 256-278.

28. Karmarkar N., Karp R.M. The differencing method of set partitioning// Report No. UCB/CSD 82/113, Computer Science Division, University of California, Berkley, 1982.

29. Kostochka A.V. List edge chromatic number of graphs with large

girth// Discrete Math., 101 (1992), p. 189-201. //

30. König D. Uber Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre// Math. Ann. 77, 1916, p. 453-465.

31. Lai T.-C. Worst-case analysis of greedy algorithms for the unbounded knapsack, subset-sum and partition problems // Oper. Res. Lett., 1993, v. 14, no. 4, p. 215-220.

32. Lawler E.L. Fast approximation algorithms for knapsack problems// Mathematics of Operations Research, 4 (1979), 339-356.

33. Lovasz L., Plummer M.D. Matching theory. Budapest, 1986

34. Martello S., Toth P. Worst-case analysis of greedy algorithms for the subset-sum problem// Math. Programming, v. 28 (1984), no. 2, p.198-205.

35. Melnikov L.S., Vizing V.G. The edge chromatic number of the directed/mixed multigraph// J. Graph Theory, to appear.

36. Meredith G.H.J. Regular n-valent, n-connected, non-Hamiltonian, non-edge-colourable graphs// J. Comb. Theory (B) 14 (1973), p. 55-60.

37. Petersen J. Die theorie der regulären graphen// Acta math., 15 (1891), p. 193-220.

38. Ringel G. Färbungsprobleme auf Flächen und Graphen. VEB Deutscher Verlag der Wissenschaphten, 1959.

39. SahniS.K. Algorithms for Scheduling Independent Tasks// J. Assoc. Comp. Mach., v. 23, no. 1, January 1976, p. 116-127.

40. Shannon C.E. A theorem on coloring the lines of a networks// J. Math. Phys., 28, 1949, p. 148-151.

41. Watkins E. A theorem of Tait colorings with an application to the generalized Petersen graphs// J. Comb. Theory (B) 6 (1969), p. 152-164.

42. Пяткин А.В. Некоторые задачи оптимизации расписания передачи сообщений в локальной сети связи// Дискретный анализ и исследование операций. Новосибирск, 1995. Том 2. N 4. С. 74-79.

43. Пяткин А.В. Задачи поиска оптимального расписания передачи данных в локальной сети связи// Второй сибирский конгресс по прикладной и индустриальной математике (INPRIM-96). Тезисы докладов. Новосибирск, 1996. С. 141.

44. Шамардин Ю.В., Пяткин А.В. О точности одного алгоритма разбиения множества// Дискретный анализ и исследование операций. Новосибирск, 1997. Том 4. N 1. С. 79-87.

45. A.V.Pyatkin Some optimization problems of scheduling the transmission of messages in a local communication network// A. D. Korshunov (ed.), Operations Research and Discrete Analysis, Kluwer Academic Publishers, Netherlands, 1997, p. 227-232.

46. A.V.Pyatkin Proof of Melnikov-Vizing conjecture for multigraphs with maximum degree at most 3/ / Discrete Math. 185 (1998), p. 275-278.