ГЕНЕРАЦІЯ ВИПАДКОВИХ ГРАФІВ ІЗ ЗАДАНИМИ ВЛАСТИВОСТЯМИ
Ключові слова:
випадкові графи, алгоритми генерації графів, алгоритм Ердеша-Реньї, зв’язний граф, регулярний граф
Анотація
Досліджується проблема генерації графів для створення бази даних тестових задач. Розглядаються алгоритми генерації випадкових графів з різними властивостями. Для різних видів графів наводяться алгоритми генерації – (граф-генератори). Запропоновано граф-генератори для довільних дерев, для дерев з обмеженням на степені вершин, для довільних графів, для зв’язних графів, для графів з обмеженням на степені вершин, для регулярних графів, для графів із заданим числом ребер.
Посилання
1. Гэри М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон ; пер. А. Фридман. – М. : Мир, 1982. – 416 с.
2. Beasley J. E. OR-Library: distributing test problems by electronic mail / J. E. Beasley // Journal of the Operational Research Society. – 1990. – № 41. – P. 1069-1072.
3. Erdos P. Probabilistic methods in combinatorics / P. Erdos, J. Spencer. – New York : Academic Press, 1974. – P. 1375-1383.
4. Степанов В. Е. Комбинаторная алгебра и случайные графы / В. Е. Степанов // Теория вероятностей и ее применение. – 1969. – № 14:3. – С. 393-420.
5. Коваленко И. Н. К теории случайных графов / И. Н. Коваленко // Кибернетика. – 1971. – № 4. – С. 1-4.
6. Колчин В. Ф. Случайные графы / В. Ф. Колчин. – М. : ФИЗМАТЛИТ, 2004. – 2-е изд. – 256 c.
7. Erdös P. On the evolution of random graphs / P. Erdös, A. Rényi // Publ. Math. Debrecen. – 1959. – Vol. 6. – P. 290-297.
8. Barab´asi L.-A. Emergence of scaling in random networks / L.-A. Barab´asi, R. Albert // Science. – 1999. – № 286. – P. 509-512.
9. Райгородский А. М. Модели случайных графов и их применения / А. М. Райгородский // Труды МФТИ. – 2010. – Т. 2, № 4. – С. 130-140.
10. Берновский М. М. Случайные графы, модели и генераторы безмасштабных графов / М. М. Берновский, Н. Н. Кузюрин // Труды Института системного программирования РАН. – 2012. – Т. 22. – С. 419-432.
11. Кнут Д. Искусство программирования. T. 2. Получисленные методы / Д. Кнут. – М. : «Вильямс», 2007. – 3-е изд. – 832 с.
2. Beasley J. E. OR-Library: distributing test problems by electronic mail / J. E. Beasley // Journal of the Operational Research Society. – 1990. – № 41. – P. 1069-1072.
3. Erdos P. Probabilistic methods in combinatorics / P. Erdos, J. Spencer. – New York : Academic Press, 1974. – P. 1375-1383.
4. Степанов В. Е. Комбинаторная алгебра и случайные графы / В. Е. Степанов // Теория вероятностей и ее применение. – 1969. – № 14:3. – С. 393-420.
5. Коваленко И. Н. К теории случайных графов / И. Н. Коваленко // Кибернетика. – 1971. – № 4. – С. 1-4.
6. Колчин В. Ф. Случайные графы / В. Ф. Колчин. – М. : ФИЗМАТЛИТ, 2004. – 2-е изд. – 256 c.
7. Erdös P. On the evolution of random graphs / P. Erdös, A. Rényi // Publ. Math. Debrecen. – 1959. – Vol. 6. – P. 290-297.
8. Barab´asi L.-A. Emergence of scaling in random networks / L.-A. Barab´asi, R. Albert // Science. – 1999. – № 286. – P. 509-512.
9. Райгородский А. М. Модели случайных графов и их применения / А. М. Райгородский // Труды МФТИ. – 2010. – Т. 2, № 4. – С. 130-140.
10. Берновский М. М. Случайные графы, модели и генераторы безмасштабных графов / М. М. Берновский, Н. Н. Кузюрин // Труды Института системного программирования РАН. – 2012. – Т. 22. – С. 419-432.
11. Кнут Д. Искусство программирования. T. 2. Получисленные методы / Д. Кнут. – М. : «Вильямс», 2007. – 3-е изд. – 832 с.
Опубліковано
2016-12-20
Як цитувати
Козін, І. В., Батовський, С. Є., & Сардак, В. І. (2016). ГЕНЕРАЦІЯ ВИПАДКОВИХ ГРАФІВ ІЗ ЗАДАНИМИ ВЛАСТИВОСТЯМИ. Computer Science and Applied Mathematics, (2), 136-143. вилучено із http://journalsofznu.zp.ua/index.php/comp-science/article/view/1382
Розділ
Articles
ISSN 
