О классе графов, обладающих сильными перемешивающими свойствами
Автор: Исаев М.И., Исаева К.В.
Журнал: Труды Московского физико-технического института @trudy-mipt
Рубрика: Математика, информатика, управление, экономика
Статья в выпуске: 3 (19) т.5, 2013 года.
Бесплатный доступ
Рассматриваются три свойства перемешиваемости графа: большая алгебраическая связность, большая константа Чигера (изопериметрическое число) и большой спектральный зазор между 1 и вторым по величине собственным значением матрицы переходных вероятностей случайного блуждания по графу. В работе доказывается эквивалентность данных свойств (в некотором смысле). Получены оценки вероятности, что случайный граф обладает указанными свойствами перемешиваемости. Кроме того, приведены асимптотические формулы для числа эйлеровых ориентаций и числа эйлеровых циклов в неориентированном простом графе.
Алгебраическая связность, изопериметрическое число, матрица лапласа, эйлеровы циклы и ориентации
Короткий адрес: https://sciup.org/142185927
IDR: 142185927
Список литературы О классе графов, обладающих сильными перемешивающими свойствами
- Biggs N.L., Lloyd E.K., Wilson R.J. Graph Theory//Clarendon Press, Oxford. -1976. -P. 1736-1936.
- Brightwell G., Winkler P. Note on Counting Eulerian Circuits//Proceedings of the 7th ALENEX and 2nd ANALCO 2005, ALENEX/ANALCO 2005. Vancouver, BC, C Demetrescu. R. Sedgewick and R. Tamassia (eds.). -2005. -P. 259-262. -e-print: arXiv:cs/0405067.
- P. Chebulu, M. Cryan, R. Martin, Exact counting of Euler tours for generalized series-parallel graphs//Journal of Discrete Algorithms. -2012. -V. 10. -P. 110-122.
- Isaev M.I. Asymptotic behaviour of the number of Eulerian circuits//Electronic Journal of Combinatorics. -2011. -V. 18(1). -P. 219.
- Исаев М.И. Асимптотическое поведение числа эйлеровых ориентаций в графах//Математические заметки. -2013. -Т. 93. -В. 6. -C. 828-843.
- Fiedler M. Algebraic connectivity of graphs//Czech. Math. J. -1973. -V. 23(98). -P. 298-305.
- Fiedler M. Laplacian of graphs and algebraic connectivity//Combinatorics and Graph Theory. -1989. -V. 25. -P. 57-70.
- Kirchhoff G. Uber die Aufl¨osung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Str¨ome gef¨uhrt wird//Ann. Phys. Chem. -1847. -V. 72. -P. 497-508/Translated by J. B. O’Toole in I.R.E. Trans. Circuit Theory, CT-5. -1958. -V. 4.
- Lovasz L. Random walks on graphs: A survey//Combinatorics, Paul Erd¨os is eighty. -1993. -V. 2. -P. 1-46.
- Mihail M., Winkler P. On the number of Eulerian orientations of a graph//Algorithmica. -1996. -V. 16. -P. 402-414.
- McKay B.D., Robinson R.W. Asymptotic enumeration of eulerian circuits in the complete graph//Combinatorics, Probability and Computing. -1998. -V. 7(4). -P. 437-449.
- McKay B.D. The asymptotic numbers of regular tournaments, eulirian digraphs and eulirian oriented graphs//Combinatorica. -1990. -V. 10(4). -P. 367-377.
- Mohar B. Isoperimetric numbers of graphs//J. Combin. Theory Ser. B. -1989. -V. 47. -P. 274-291.
- Mohar B. The Laplacian spectrum of graphs//Graph Theory, Combinatorics, and Applications. -1991. -V. 2/Ed. Y. Alavi, G. Chartrand, O. R. Oellermann, A. J. Schwenk. -P. 871-898.
- P. Tetali, S. Vempala, Random sampling of Euler tours//Algorithmica. -2001. -V. 30. -P. 376-385.
