Конструктивные описания графов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Аннотация.

ВВЕДЕНИЕ.

ГЛАВА 1. КОНСТРУКТИВНЫЙ ПОДХОД

К ПРЕДСТАВЛЕНИЮ ГРАФОВ.

§1. Определения основных понятий и обозначения.

§2. Свойства операций склейки.

§3. Структура замкнутых классов графов.

§4. Базисы классов всех графов, мультиграфов и простых графов.

ГЛАВА 2. ДИНАМИЧЕСКАЯ СТРУКТУРНАЯ

ХАРАКТЕРИЗАЦИЯ ГРАФОВ.

§1. Триангулированные графы.

§2. Планарные графы.

§3. Внешнейланарные графы.

§4. Максимальные планарные и внешнепланарные графы.

ГЛАВА 3. БАЗИСЫ ЗАМКНУТЫХ КЛАССОВ

ПЛАНАРНЫХ ГРАФОВ.

§1, Класс всех планарных графов.

§2. Внешнепланарные графы.

§3. Триангулированные планарные графы.

ГЛАВА 4. КАНОНИЧЕСКИЕ СУПЕРПОЗИЦИИ ГРАФОВ.

§1. Достаточные условия реализуемости графов каноническими Я-суперпозициями.

§2. Экономное кодирование помеченных графов.

§3. Экономное кодирование непомеченных графов.

ГЛАВА 5. ОПТИМАЛЬНЫЕ ЛИНЕЙНЫЕ

РАЗМЕЩЕНИЯ ГРАФОВ.

§1. Постановки задач и обзор результатов.

§2. Свойства минимальных плоских нумераций вершин деревьев.

§3. Алгоритм построения минимальной плоской нумерации вершин дерева.

ГЛАВА 6.ПРИБЛИЖЕННЫЕ РЕШЕНИЯ ЗАДАЧИ ПОСТРОЕНИЯ МИНИМАЛЬНОЙ НУМЕРАЦИИ

ВЕРШИН ДЕРЕВА.

§1. Верхняя оценка длины дерева при минимальной плоской нумерации.

§2, Асимптотика длины дерева при минимальной плоской нумерации.

§3. Об эффективности приближенных решений задачи построения минимальной нумерации вершин дерева.

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

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

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

Конструктивный подход основывается на совместном рассмотрении графов и их свойств, как схемы и функции соответствующего класса управляющих систем (УС). Такой подход к изучению УС в математической кибернетике был предложен С.В.Яблонским в 1959г [46]. Позднее он широко использовался при изучении различных классов УС, в частности для функциональных систем с операциями.

Диссертация состоит из введения, шести глав, приложения и списка

1. Берж К. Теория графов и ее применения. - Москва: Изд-во Иностранной литературы, 1962.

2. Геолецян Г.Г. Плоское размещение дерева с минимизацией длины // Вопр. радиоэлектроники, сер. ЭВТ. Вып. 6. 1975. - С. 67-91.

3. Гольдберг М.К., Клинкер И.А. Нумерации равномерного дерева, минимизирующая сумму длин ребер // Аннот. докл. семинара ИПМ ТРУ. 1975. N 10. - С. 65-71.

4. Гольдберг М.К., Клинкер И.А. Алгоритмы минимальной нумерации вершин дерева // Сообщения АН ГрССР. 1976. - Т. 81. N 3. - С. 553-558.

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

6. Джордж А. Лю Дж. Численное решение больших разреженных систем уравнений. Москва: Изд-во Мир, 1984.

7. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. Москва: Изд-во Наука, 1990.

8. Земляченко В.Н. Установление изоморфизма деревьев // Вопросы кибернетики. Москва: Изд-во Наука, 1973. - С. 54-60.

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

10. Иорданский М.А. Минимальные нумерации вершин деревьев // ДАН СССР. 1974. - Т. 218. N 2. - С. 272-275.

11. Иорданский М.А. Минимальные нумерации вершин деревьев // В сб. Проблемы кибернетики. Вып. 31. / Под ред. С. В. Яблонского. Москва: Изд-во Наука, 1976. - С. 109-131.

12. Иорданский М.А. О плоских размеп1;ениях деревьев // Тезисы докладов IV Всесоюзной конференции "Проблемы теоретической кибернетики". Новосибирск, 1977. - С. 137-138.

13. Иорданский М.А. Минимальные плоские размещения деревьев // Дискретный анализ. Вып. 33. Новосибирск: Изд-во ИМ СО АН СССР, 1979. - С. 3-30.

14. Иорданский М.А. Задачи размещения графов. I // Комбинаторно-алгебраические методы в прикладной математике. Межвуз. сб. научн. трудов / Под ред. Ал. А. Маркова. Горький: Изд-во Горьковского унта, 1980. - С. 62-77.

15. Иорданский М.А. Задачи размещения графов. II // Комбинаторно-алгебраические методы в прикладной математике. Межвуз. сб. научн. трудов / Под ред. Ал. А. Маркова. Горький: Изд-во Горьковского унта, 1983. - С. 26-45.

16. Иорданский М.А. Замкнутые классы планарных графов // Комбинаторно-алгебраические методы в прикладной математике.'Межвуз. сб. научн. трудов / Под ред. Ал. А. Маркова. Горький: Изд-во Горьковского ун-та, 1985. - С. 76-82.

17. Иорданский М.А. О минимаксных нумерациях вершин графов // Комбинаторно-алгебраические методы в прикладной математике. Межвуз. сб. научн. трудов / Под ред. Ал. А. Маркова. Горький: Изд-во Горьковского ун-та, 1986. - С. 60-73.

18. Иорданский М.А. О степенях вершин некоторых классов планарных графов // Комбинаторно-алгебраические методы в прикладной математике. Межвуз. сб. научн. трудов / Под ред. Ал. А. Маркова. Горький: Изд-во Горьковского ун-та, 1987. - С. 34-39.

19. Иорданский М.А. Оптимальные нумерации некоторых классов плоских триангуляции // Комбинаторно-алгебраические методы в прикладкой математике. Межвуз. сб. научн. трудов / Под ред. Ал. А. Маркова. Горький: Изд-во Горьковского ун-та, 1989. - С. 63-73.

20. Иорданский М.А. Некоторые вопросы анализа и синтеза графов // Труды первой международной конференции "Математические алгоритмы". Н.Новгород: Изд-во Нижегородского ун-та, 1994. - С. 33-38.

21. Иорданский М.А. Функциональный подход к задачам представления графов // Дискретный анализ и исследование операций. 1995. - Т. 2. N 1.- 0. 74-75.

22. Иорданский М.А. Динамическая структурная характеризация графов // Дискретный анализ и исследование операций. 1995. - Т. 2. N 3. - С. 76.

23. Иорданский М.А. Алгоритмические описания внепгнепланарных графов // Тезисы докладов второй международной конференции "Математические алгоритмы". Н.Новгород: Изд-во Нижегородского ун-та, 1995. - С. 24-25.

24. Иорданский М.А. Конструктивные описания планарных графов // Тезисы докладов XI Международной конференции "Проблемы теоретической кибернетики". Ульяновск, 1996. - Москва: Изд-во Российского государственного гуманитарного университета. - С. 76-78.

25. Иорданский М.А. Конструктивные описания графов // Дискретный анализ и исследование операций. 1996. - Т. 3. N. 4. - С. 35-63.

26. Иорданский М.А. Алгоритмические описания внепгнепланарных графов // Труды второй Международной конференции "Математические алгоритмы". Н.Новгород: Изд-во Нижегородского ун-та, 1997. - С. 78-82.

27. Иорданский М.А. Конструктивные описания графов и их приложения. // Труды II Международной конференции "Дискретные моделив теории управляющих систем" Москва: Изд-во Диалог-МГУ, 1997. - С. 63-64.

28. Иорданский М.А. Функциональный подход к представлению графов // Доклады РАН. 1997. - Т. 353. N. 3. - С. 303-305.

29. Иорданский М.А. Оптимизационные задачи поиска информации в базах знаний // В сб. трудов семинара по дискретной математике и ее приложениям. Москва: Изд-во механико-математического факультета МГУ, 1998. - С. 163-164.

30. Иорданский М.А. Об операциях над графами // Труды IV Международной конференции "Дискретные модели в теории управляющих систем"(Красновидово, 19-25 июня 2000 г.). Москва: Изд-во "МАКС Пресс", 2000. - С. 33-34.

31. Иорданский М.А. Конструктивные описания графов // Материалы XI Межгосударственной школы-семинара "Синтез и сложность управляющих систем"(Н.Новгород, 20-25 ноября 2000 г.). Москва: Изд-во механико-математического факультета МГУ, 2001. - С. 80-84.

32. Иорданский М.А. Оптимальные нумерации вершин графов // Сборник лекций, вьш.1. Москва: Изд-во механико-математического факультета МГУ, 2001. - С. 17-33.

33. Кесельман Д.Я. О нумерации вершин графа // В сб. Алгебра. Иркутск: Изд-во Иркутского ун-та, 1973. - С. 364-369.

34. Лепин В.В. Задача о профиле матриц и графов // Препринт АН БССР. Минск: Изд-во института математики, 1986. N 33(269).

35. Лепин В.В. Задача о фронте матриц и графов // Препринт АН БССР.- Минск: Изд-во института математики, 1987. N 15(285).

36. Лепин В.В. Минимальные по длине нумерации гиперграфов // Препринт АН БССР. Минск: Изд-во института математики, 1987. N 38 (308).

37. Ope О. Теория графов. Москва: Изд-во Наука, 1968.

38. Писсанецки С. Технология больших разреженных матриц. Москва: Изд-во Мир, 1988.

39. Сегерлинд Л. Применение метода конечных элементов. Москва: Изд-во Мир, 1979.

40. Тьюарсон Р. Разреженные матрицы. Москва: Изд-во Мир, 1977.

41. Харари Ф. Теория графов. Москва: Изд-во Мир, 1973.

42. Харари Ф., Палмер Э. Перечисления графов. Москва: Изд-во Мир, 1973.

43. Шейдвассер М.А. О длине и ширине размещений графов в решетках // В сб. Проблемы кибернетики. Вып.29 / Под ред. С. В. Яблонского.- Москва: Изд-во Наука, 1974. С. 63-102.

44. Шейдвассер М.А. Об оптимальной нумерации вершин дерева // Дискретный анализ. Вып. 17. Новосибирск: Изд-во ИМ СО АН СССР, 1970. - С. 56-74.

45. Яблонский C.B. Основные понятия кибернетики // В сб. Проблемы кибернетики. Вып. 2. / Под ред. А. А. Ляпунова и С. В. Яблонского.- Москва: Физматгиз, 1959. С. 7-38.

46. Яблонский C.B. Введение в дискретную математику. Москва: Изд-во Наука, 1986.

47. Alway G.G., Martin D.W. An algorithm for reducing the bandwidth of a matrix of simmetrical configuration // Comput. J. 1965. - V. 3. N 8.- P. 264-272.

48. Armstrong B.A. A hibrid algorithm for reducing matrix bandwidth. // Int. J.Number. Meth Eng. 1984. - V. 20. N 10. - P. 1929-1940.

49. Armstrong B.A. Near-minimal matrix profoles and wavefronts for testing nodal resequencing algorithms // Int. J. Number. Meth. Eng. 1985. -V. 21. N 10. - P. 1785-1790.

50. Bernstein A.J. Maximally connected arrays on the n-cube // SI AM J. Appl. Math. 1967. - V. 15. N 6. - P. 1485-1489.

51. Booth K.S. Lueker G.S. Testing for the consecutive ones property, interval graphs, and graph planarity using PQ tree algorithms // J. Comput. Syst. Sci. - 1976. - V. 13. - P. 335-379.

52. Chinn P.Z., Chvatalova J., Dewdney A.K., Gibbs N.E. The bandwidth problem for graphs and matrices a survey / / J . Graph Theory. - 1982.- V. 6. P. 223-254.

53. Chung F.R.K. On optimal linear arrangement algorithm for undirected trees // SIAM J. Comput. 1984. - V. 8. N 1. - P. 15-32.

54. Chvatal V. A remark on a problem of Harrary // Chechosl. Math. J.- 1970. V. 20(95). N 1. - P. 109-111.

55. Chvatalova J. Optimal labeling of a product of two path // Discrete Math.- 1975. V, 11. N 3-4. - P. 249-253.

56. Cuthill E., Mekee J. Reducing the bandwidth of sprarse symmetric matrices // Proc. 24-th Nat. Conf. ACM. 1969. - P. 157-172.

57. Dirac G. A, On rigid circuit graphs // Abh. Math Seminar Univ. Hamburg.- 1962. V. 25. N 1-2. - P. 71-75,

58. Everstine C.C. A comparision of three resequencing algorithms for the reduction of matrix profile and wave-front // Int. J. Numer. Meth. Eng.- 1979. V. 14. - P. 837-863.

59. Fehppa C.A. Solution of linear equatione with skyline-stored symmetric matrix // Comput. Structures. 1975. - V. 5. - P. 13-29.

60. Fitzgerald C.H. Optimal indexing of the vertices of graphs // Math. Comput. 1974. - V. 28. - P. 825-831.

61. Fulkerson D.R. Grose O.A. Incidence matrices and interval graphs // Pacific J. Math. 1965. - V. 15. - P. 835-853.

62. Gibbs N.E. Algorithm 509 A hybrid profile reduction algorithm // ACM Trans. Math. Software. - 1976. - V. 2. - P. 378-387.

63. Gibbs N.E., Poole W. G., Stockmeyer R. K. An algorithm for reducing the bandwidth and profile of a sparse matric // SI AM J. Numor. Anal. 1976. - V. 13. - P. 236-250.

64. Garey M.R.,Graham R.L.,Johnson D.S., Knuth D.E. Complexity results for bandwidth minimization // SI AM J. Appl. Math. 1978. - V. 34.- P. 477-495.

65. Gibbs N.B., Poole W. G., Stockmeyer P. K. A comparison of several bandwidth and profile reduction algorithms // ACM Trans, on Math. Software.- 1976. V. 2. - P. 322-330.

66. Gilmore P.C. Optimalal and suboptimal algorithms for the quadatic assignment problems / / J . Soc. Indust. Appl. Math. 1962. N 10. - P. 305-313.

67. Hanan M., Kurtzberg J.M. A review of the placement and quadratic assignment prolemens // SIAM Rev. 1972. - V. 14. N 2. - P. 324-342.69. 64. Happer L.H. A necessary condition on minimal cube numberings // J. Appl. Prob. 1967. - V. 4. N 2. - P. 397-401.

68. Harper L.H. Optimal assignements of numbers to vertices / / J . Soc.Indust. Appl. Math. 1964. - V. 12. N 1. - P. 131-135.

69. Harper L.H. Optimal numberings and isoperimetric problems on graphs // J. Comb. Theory. 1966. - V. 1. N 3. - P. 385-393.

70. Irons B.M. A frontal solution program for finite element analyais // Int. J. Numer. Meth. Eng. 1970. - V. 2. - P. 5-32.

71. Irons B.M., Ahmad S. Technques of finite elements // Chichester. 1980.

72. Kautz W.H. Optimized data encoding for digital computer // IRE Conv. Rec. 1954. - V. 4. - P. 47-56.

73. King LP. An automatic reordering scheme for simultaneous equations derived from network systems // Int. J. Numer. Meth. Eng. 1970. - V. 2.- P. 523-533.

74. Kotzig A. On decomposition of a tree into the minimal numbers of parths // Mat. Casop. 1967. - V. 17. N 1. - P. 76-78.

75. Kurtzberg J.M. On approximation methods for the assignment problems // J. Assoc. Comput. Mach. 1962. - N. 9. - P. 419-439.

76. Lawer E.L. The quadratic assignment problem // Manegement Sci. 1963.- N 9. P. 586-599.

77. Lebesgue H. Quelques consequences simple de la formule d'Euler / / J . Math. Pures Appl. 1940. - V.9. - P.27-43.

78. Lin J. W-H., Sherman A. H . Comparative analysis of the Cuthill- Mokee and the reverse Cuthill-Mokee ordering algorithms for sparse matrices / / SIAM J. Numer. Anal. 1975. - V. 13. N 2. - P. 198-213.

79. Lindsey J.H. Assignments of numbers to vertices // Amer. Math. Monthly. 1964. - V. 71. N 5. - P. 508-516.

80. Melosh R. J., Bamford R. M. Eifecient Solution of load-deflection equations. // ASGE J. Struct. Div. 1969. - V. 95. N ST4. - P. 661-676.

81. Munkres J. Algorithms for assignment and trasportation probles // J.Sos. Indust. Apple. Math. 1957. - N 5. - P. 32-38.

82. Papadimitrion C.H. The NP-completnes of the bandwidth minimization problem // Computing. 1976. - V. 16. - P. 263-270.

83. Sekanina M. On an ordering of the set of vertices of a connected graph // Publ. Fac. Sci. Univ. Brno, Tchecoslovaqui. 1960. - N 412. - P. 137-142.

84. Sekanina M. On an ordering of the vertices of graphs // Cas. pro pest math. 1963. - V. 8. - P. 265-282.

85. Sekanina M. On an algorithm for ordering of graphs // Canad. Math. Bull. 1971. - V. 14. N 2. - P. 221-224.

86. Shiloach Y. A minimum Hnear arrangement algorithm for undirected trees // SI AM J. Comput. 1979. - V. 8. N 1. - P. 15-32.

87. Sloan A.W. An algorithm for profile and wavefront reduction of sparse matrices // Int. J. Numer. Meth. Eng. 1986. - V. 23. N 2. - P. 239-251.

88. Snay R.A. Reducing the profile of sparse symmetric matrices // Bui. Geodesique. 1976. - V. 50. - P. 341-352.

89. Steiglitz K, Bernstein A.J. Optimal binary coding of orderded numbers // J. Soc. Indust. Appl. Math. 1965. - V. 13. N 2. - P. 441-443.

90. Veldhorst M. Approximation of the consecutive ones matrix augmentation problem // SIAM J. Comput. 1985. - V. 14. N 3. - P. 709-729.