Помощь в написании студенческих работ
Антистрессовый сервис

Аналитический подход к задачам перечисления графов со спектральными ограничениями

Диссертация: Аналитический подход к задачам перечисления графов со спектральными ограничениями
ДиссертацияПомощь в написанииУзнать стоимостьмоей работы

Во второй половине двадцатого столетия бурный прогресс вычислительной техники и кибернетики обусловил интенсивное развитие всей дискретной математики, и, в частности, интерес к алгоритмическим аспектам перечисления графов (см.,). После 1970;х много внимания уделялось асимптотическим оценкам и взаимосвязи между задачами перечисления и теорией случайных графов. Для более подробной информации… Читать ещё >

Аналитический подход к задачам перечисления графов со спектральными ограничениями (реферат, курсовая, диплом, контрольная)

Содержание

  • Глава 1. Некоторые задачи перечисления графов: проблемы и методы их решения
    • 1. 1. Проблемы алгоритмического решения задач перечисления
    • 1. 2. Эйлеровы ориентации
      • 1. 2. 1. Постановка задачи
      • 1. 2. 2. Приближенный вероятностный алгоритм
      • 1. 2. 3. Случай полного графа. Представление в виде интеграла
    • 1. 3. Эйлеровы циклы
      • 1. 3. 1. Постановка задачи. Случай полного графа
      • 1. 3. 2. Ориентированные графы. Представление в виде интеграла
      • 1. 3. 3. Вероятностные интерпретации
    • 1. 4. Подграфы с заданной последовательноствю степеней вершин
      • 1. 4. 1. Постановка задачи. Представление в виде интеграла
      • 1. 4. 2. Случай полного графа
      • 1. 4. 3. Случай произвольного графа. Наивная гипотеза
    • 1. 5. Общая схема доказательства основных результатов
  • Глава 2. Асимптотические оценки многомерных интегралов гауссовского типа
    • 2. 1. Интегралы гауссовского типа. Обозначения и предположения
    • 2. 2. Матрицы с асимптотическим диагональным доминированием. 35 2.2.1. Свойства обратной матрицы
      • 2. 2. 2. Определитель возмущенной матрицы
      • 2. 2. 3. Главные миноры
    • 2. 3. Некоторые функции над полиномами
      • 2. 3. 1. Высота и четная высота
      • 2. 3. 2. Функция ха
    • 2. 4. Асимптотические оценки
      • 2. 4. 1. Формулировка результатов
      • 2. 4. 2. Вспомогательные утверждения. Основная лемма
      • 2. 4. 3. Редукция полиномов
      • 2. 4. 4. Доказательство асимптотических оценок
  • Глава 3. Графы со спектральными ограничениями
    • 3. 1. Класс графов с сильными перемешивающими свойствами
      • 3. 1. 1. Перемешивающие свойства графов
      • 3. 1. 2. Доказательство эквивалентности
      • 3. 1. 3. Примеры
      • 3. 1. 4. Пути и разрезы
      • 3. 1. 5. Свойства матрицы Лапласа
    • 3. 2. Класс существенно недвудольных графов
      • 3. 2. 1. Недвудольность и апериодичность
      • 3. 2. 2. Примеры
      • 3. 2. 3. Нечетные пути
      • 3. 2. 4. Свойства беззнаковой матрицы Лапласа
    • 3. 3. Сильная перемешиваемость и существенная недвудольность случайного графа
    • 3. 4. Комбинаторный смысл миноров матрицы Лапласа и определителя (^-матрицы
  • Глава 4. Аналитический подход на примере некоторых задач перечисления графов
    • 4. 1. Эйлеровы ориентации
      • 4. 1. 1. Асимптотическая формула
      • 4. 1. 2. Основная часть интеграла
      • 4. 1. 3. Оценка незначительных частей
    • 4. 2. Эйлеровы циклы
      • 4. 2. 1. Асимптотическая формула
      • 4. 2. 2. Приведение к интегралу гауссовского типа
      • 4. 2. 3. Основная часть интеграла
      • 4. 2. 4. Оценка незначительных частей
    • 4. 3. Подграфы с заданной последовательностью степеней вершин
      • 4. 3. 1. Асимптотическая формула
      • 4. 3. 2. Основная часть интеграла
      • 4. 3. 3. Оценка незначительных частей
      • 4. 3. 4. Наивная гипотеза

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

Впервые понятие «граф» ввел в 1936 году венгерский математик Кениг Д. Однако первая работа [39] по теории графов была написана еще в 1736 году Эйлером Л., в которой он не только решил популярную в то время «задачу о Кенигсбергских мостах», но и получил критерий существования в графе специального маршрута (эйлерова цикла, как теперь его называют).

Хотя Эйлер Л. и рассматривал задачи подсчета некоторых типов триангулированных многоугольников на плоскости, все же существенные шаги в теории перечисления графов были сделаны лишь в девятнадцатом столетии. В своих работах, опубликованных в 1857—1889 гг., Кэли А. получил формулы для количества деревьев трех типов: помеченных, корневых и обычных, а также связанных с ними химических структур. Ещё ранее Кирхгоф Г. в [61] нашел в неявной форме число остовных деревьев заданного графа, а значит, в частности, число помеченных деревьев.

В настоящее время перечисление графов представляет собой развитую теорию, занимающую существенное место в области комбинаторного анализа. В книге [76] собраны известные результаты о подсчете помеченных деревьев и свойствах случайных деревьев. В монографии [52] приведено большое количество разнообразных задач перечисления непомеченных графов с определенными свойствами. Для задач такого типа используется алгебраический подход, основанный на теории перечисления Пойа (см., например, [78]). Принцип включения и исключения, обращение Мёбиуса, а также многие другие известные методы, используемые в перечислительной комбинаторике, подробно изложены в [84].

Во второй половине двадцатого столетия бурный прогресс вычислительной техники и кибернетики обусловил интенсивное развитие всей дискретной математики, и, в частности, интерес к алгоритмическим аспектам перечисления графов (см. [24], [58], [89]). После 1970;х много внимания уделялось асимптотическим оценкам и взаимосвязи между задачами перечисления и теорией случайных графов. Для более подробной информации о применении этого вероятностного подхода см., например, [22], [71].

Аналитические методы, безусловно, относятся к числу наиболее мощных методов комбинаторного анализа. Они основываются на точном описании перечисляемых комбинаторных объектов с помощью производящих функций. Эти функции интерпретируются как аналитические объекты, то есть как отображения комплексной плоскости в себя. Их особенности определяют (асимптотически) коэффициенты производящих функций и позволяют получить оценки членов исходных последовательностей. В книге [44] тщательно изложены основные известные на настоящее время аналитические методы, а также рассмотрены как классические, так и современные приложения этого подхода.

Хотя теория перечисления графов интенсивно развивается уже более 50 лет, интерес к этой области перечислительной комбинаторики не пропал, о чем говорят многочисленные работы последних лет: [18], [20], [21], [23], [25], [34], [45], [50], [68].

В данной работе результаты из [67], [69], [70] об асимптотике числа эйлеровых ориентации, эйлеровых циклов и помеченных подграфов с заданной последовательностью степеней вершин в полных графах обобщаются для существенно более широких классов графов со спектральными ограничениями. На примере этих классических задач продемонстрирована универсальность аналитического подхода для решения проблем перечисления графов.

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

ЗАКЛЮЧЕНИЕ

В заключение сформулируем основные результаты работы.

1. Аналитический подход, использованный в работах [67], [69], [70] для случая полного графа, адаптирован для существенно более широких классов графов со спектральными ограничениями. Получены новые явные асимптотические формулы для эйлеровых ориентаций, эйлеровых циклов и помеченных подграфов с заданной последовательностью степеней вершин.

2. Получены новые свойства классов графов со спектральными ограничениями. В частности, доказано, что в некотором вероятностном смысле практически все графы принадлежат рассматриваемым классам.

3. При условии асимптотического диагонального доминирования соответствующей матрицы квадратичной формы получена асимптотика интеграла гауссовского типа с полиномиальным возмущением в показателе экспоненты.

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

• Рассмотренные задачи являются классическими задачами теории перечисления графов. Новые асимптотические формулы позволяют оценить искомый ответ практически для всех графов (в некотором вероятностным смысле).

• Рассмотренные задачи считаются трудными в теории сложности вычислений, поэтому полученные легковычислимые явные формулы представляют особый интерес с алгоритмической точки зрения.

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

Автор выражает благодарность научному руководителю к.ф.-м.н. доценту Тарасову С. П. за постановки задач и постоянное внимание к работе, а также профессору McKay B.D. за обсуждение работы и ряд ценных замечаний.

Работа поддержана грантом РФФИ № 11−01−398а.

Показать весь текст

Список литературы

  1. БЕКЛЕМИШЕВ Д. В. Дополнительные главы линейной алгебры// М.: Наука, 1983. 335 с.
  2. ИСАЕВ М. И. Асимптотика числа эйлеровых циклов в плотных графах// Труды 53-й научной конференции МФТИ «Современные проблемы фундаментальной и прикладной математики», Управление и прикладная математика, М.: МФТИ, 2010, Т. 1, С. 72−73.
  3. ИСАЕВ М. И. Асимптотика числа подграфов с заданными степенями вершин в недвудольных графах// Тезисы международной конференции «Алгебра и комбинаторика», посвященной 60-летию А. А. Махнева, Екатеринбург: изд. «УМЦ- УПИ», 2013, С. 58−60.
  4. ИСАЕВ М. И. Оценка числа подграфов с заданными степенями вершин// Тезисы международной конференции «Дискретная оптимизация и исследование операций», Новосибирск: изд. Ин-та математики, 2013, С. 106.
  5. ИСАЕВ М. И. Асимптотическое поведение числа эйлеровых ориентаций в графах// Математические заметки, 2013, Т. 93, В. 6, С. 828−843.
  6. ИСАЕВ М.И., ИСАЕВА К.В. О классе графов, обладающих сильными перемешивающими свойствами// Труды Московского Физико-Технического Института, 2013, Т. 5, № 3, С. 44−54.
  7. ЛАНДО С.К., Звонкин А. К. Графы на поверхностях и их приложения// Москва: МЦНМО, 2010, 480 с.
  8. ЛАНКАСТЕР П. Теория матриц// М.: Наука, Гл. ред. физ.-мат. лит., 1973, 280 с.
  9. ФЕЛЛЕР В. Введение в теорию вероятностей и ее приложения// М.: Мир, 1967, в 2-х томах.
  10. ЧЕБОТАЕВ П.Ю., ШАМИС Е. В. Матричная теорема о лесах и измерение связей в малых социальных группах// Автомат, и телемех., 1997, В. 9, С. 125−137.
  11. Aardenne-Ehrenfest Т., Bruijn N.G. Circuits and trees in oriented linear graphs// Simon Stevm, 1951, V. 28, P. 203−217.
  12. ANSTEE R. An algorithmic proof of Tutte’s /-factor theorem// J. Algorithms, 1985, V. 6, P. 112−131.
  13. Arenas A., Diaz-Guilera A., Kurths J., Moreno Y., Zhou C. Synchronization in complex networks// Physics Reports, 2008, V. 469, Iss. 3, P. 93−153.
  14. Barvinok A, H artig an J. An asymptotic formula for the number of non-negative integer matrices with prescribed row and column sums// Transactions of the American Mathematical Society, 2012, V. 364, P. 4323−4368.
  15. Barvinok A, Hartigan J. The number of graphs and a random graph with a given degree sequence// Random Structures and Algorithms, 2013, V. 42, Iss. 3, P. 301—348.
  16. Chebulu P., Cryan M., Martin R. Exact counting of Euler tours for generalized series-parallel graphs// Journal of Discrete Algorithms, 2012, V. 10, P. 110−122.
  17. Chung F., Spectral Graph Theory// (CBMS Regional Conference Series in Mathematics, N. 92), American Mathematical Society, 1997, 207 p.
  18. Cvetkovic D., Rowlinson P., SlMIC S.K. Signless Laplacians of finite graphs// Linear Algebra and its Applications, 2007, V. 423, Iss. 1,, P. 155−171.
  19. Cvetkovic D., Simic S.K. Towards a spectral theory of graphs based on the signless Laplacian, I// Publ. Inst. Math. (Beograd), 2009, V. 85(99), P. 19−33.
  20. Cvetkovic D., Simic S.K. Towards a spectral theory of graphs based on the signless Laplacian, II// Linear Algebra Appl., 2010, V. 432, P. 2257−2272.
  21. Cvetkovic D., slmic s.k. Towards a spectral theory of graphs based on the signless Laplacian, III// Appl. Anal. Discrete Math., 2010, V. 4, P. 156−166.
  22. CREED P. Counting and sampling problems on Eulerian graphs// PhD thesis, University of Edinburgh, 2010.
  23. Das K.C. On conjectures involving second Largest signless Laplacian eigenvalue of graphs// Linear Algebra Appl., 2010, V. 432, P. 3018−3029.
  24. Dyer M., Goldberg L.A., Greenhill C., Jerrum M. On the relative complexity of approximate counting problems// APPROX 2000, Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization, 2000, P. 108−119.
  25. ERDOS P., GALLAI T. Graphs with given degrees of vertices// Mat. Lapok, 1960, V. 11, P. 264−274.
  26. Erdos P., Renyi A. On random graphs I// Publ. Math. Debrecen. 1959, V. 6., P. 290−297.
  27. Euler L. Solutio problematis ad geometriam situs pertinentis// Comm. Acacl. Sci. Imperialis Petropolitane, 1736, V. 8, P. 128−140.
  28. FALLATA S., Fan Y.-Z. Bipartiteness and the least eigenvalue of signless Laplacian of graphs// Linear Algebra and its Applications, 2012, V. 436, Iss. 9, P. 3254−3267.
  29. Fellows M.R. Parameterized Complexity: The Main Ideas and Some Research Frontiers// Algorithms and Computation, Lecture Notes in Computer Science, 2001, V. 2223, P. 291−307.
  30. Fiedler M. Algebraic connectivity of graphs// Czech. Math. J., 1973, V. 23(98), P. 298−305.
  31. FIEDLER M. Laplacian of graphs and algebraic connectivity// Combinatorics and Graph Theory, 1989, V. 25, P. 57−70.
  32. Flajolet P., SedqeyviCK R. Analytic Combinatorics// Cambridge University Press, 2009, 824 p.
  33. Flum j., grohe M. The Parameterized Complexity of Counting Problems// SIAM Journal on Computing archive, 2004, V. 33, Iss. 4, P. 892−922.
  34. Ford L.R., Fulkerson D.R. Flows in Networks// Princeton University Press, Princeton, NJ, 1962, 194 p.
  35. Geelen J., Gerards B., Reed B., Seymour P., Vetta A. On the odd-minor variant of Hadwiger’s conjecture// Journal of Combinatorial Theory, Series B, 2009, V. 99, P. 20−29.
  36. Greenhill C., McKay B.D. Random dense bipartite graphs and directed graphs with specified degrees// Random Struct. Alg., 2009, V. 35, P. 222−249.
  37. Haemers W., Spence E. Enumeration of cospectral graphs// Eur. J. Combm., 2004, V. 25, P. 199−211.
  38. Harary F., palmer E. Graphical Enumeration// Academic Press, New York, 1973, 271 p.
  39. Jaeger F., Vertigan D.L., Welsh D.J.A. On the Computational Complexity of Jones and Tutte Polynomials// Math. Proc. Cambridge Philos. Soc, 1990, V. 108(35), 35−53.
  40. Jerrum M., Sinclair A., Vigoda E. A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries// J. ACM, 2004, V. 51, P. 671−697.
  41. LOVASZ L. Random walks on graphs: A survey// Combinatorics. Paul Erdos is eighty, V. 2 (Keszthely, 1993), Janos Bolyai Math. Soc., 1996, V. 2 of Bolyai Soc. Math. Stud., P. 353−397.
  42. LYONS A. Polynomial-Time Approximation of the Permanent// Course project for MATH 100: Markov Chain Monte Carlo (Topics in Probability Theory). Instructor: Peter Winkler, 2011, 7 p.
  43. McKay B.D. Applications of a technique for labelled enumeration// Congressus Numerantium, 1983, V. 40, P. 207−221.
  44. McKay B.D. The asymptotic numbers of regular tournaments, eulerian digraphs and eulerian oriented graphs// Combinatorica, 1990, V. 10, N. 4, P. 367−377.
  45. McKay B.D. Subgraphs of dense random graphs with specified degrees// Combinatorics, Probability and Computing, 2011, V. 20, P. 413−433.
  46. McKay B. D, robinson r.w. Asymptotic enumeration of eulerian circuits in the complete graph// Combinatorics, Probability and Computing, December 1998, V. 7, N. 4, P. 437−449.
  47. McKay B. D, WORMALD N.C. Asymptotic enumeration by degree sequence of graphs of high degree// European J. Combin, 1990, V. 11, P. 565−580.
  48. McKay B. D, wormald N.C. Asymptotic enumeration by degree sequence of graphs with degrees o (n1//2)//, Combinatorica, 1991, V. 11, Iss. 4, P. 369−382.
  49. MENGER K. Zur allgemeinen Kurventheorie// Fund. Math. 10, 1927, P. 96−115.
  50. Mihail M, Winkler P. On the number of Eulerian orientations of a graph// Algorithmica, 1996, V. 16, P. 402−414.
  51. MOHAR B. Isoperimetric numbers of graphs// J. Combin. Theory, Ser. B, 1989, V. 47, P. 274−291.
  52. MOHAR B. The Laplacian spectrum of graphs// Graph Theory, Combinatorics, and Applications, 1991, V. 2, Ed. Alavi Y, Chartrand G, Oellermann O. R, Schwenk A. J, P. 871−898.
  53. SCHRIJVER A. Bounds on the number of Eulerian orientations// Combinatorica, 1983, V. 3, P. 375−380.
  54. SCHRIJVER A., SEYMOUR P. Packing Odd Paths// Journal of Combinatorial Theory, Series B, 1994, V. 62, Iss. 2, P. 280−288.81. slmon B. The P (4>)2 Euclidian (Quantum) Field Theory// Princeton Univ. Press, 1974, 392 p.
Заполнить форму текущей работой

Сессия? Спокойно!