МЕТОДИ АВТОМАТИЧНОЇ ГЕНЕРАЦІЇ ГРАФІВ ЗІ ЗВ’ЯЗАНИМИ ВЕРШИНАМИ

Руслан Олександрович Хліста

Анотація


У статті запропоновані алгоритми автоматичної генерації: зв’язного неорієнтованого дерева та простого зв’язного неорієнтованого графа. Для алгоритму генерації зв’язного неорієнтованого дерева на вхід обчислювального пристрою подається кількість вершин, на виході буде отримана матриця суміжності дерева у вигляді двовимірного масиву цілих чисел. Для алгоритму генерації графів на вхід подається матриця суміжності дерева, на виході буде отримано матриця суміжності неорієнтованого графа. Алгоритми призначені для систем автоматичної генерації задач та тестових завдань з дискретної математики, математичної логіки та інформатики. Також розроблені алгоритми можуть бути застосовні для дослідження переміщення мобільного агенту по вершинах графа, моделювання роботи інформаційних мереж та інших завдань, які використовують апарат графів.

 

An algorithm of automatic generation of: a connected undirected tree and a simple connected undirected graph. For the algorithm for generating the tree of an undirected connected to the input of the computing device is supplied number of vertices, the output is obtained by the adjacency matrix of a tree as a two-dimensional array of integers. For the algorithm for generating graphs the input is the adjacency matrix of a tree, the output is obtained by the adjacency matrix of an undirected graph. The algorithms are designed for automatic generation of systems problems and test tasks on discrete mathematics, mathematical logic and computer science. Algorithms are also designed to be useful for the study of the mobile agent vertices of the graph, modeling of information networks and other applications that use graphs apparatus.


Повний текст:

PDF

Посилання


Dudek G., Jenkin M. Computational Principles of Mobile Robotics – Cambridge: Cambridge University Press, 2010. – 391 p.

Kuipers B. The Spatial Semantic Hierarchy // Artificial Intelligence. – 2000. – Vol. 119. – P. 191-233.

Rodionov S. and Choo H. «On Generating Random Network Structures: Trees», Lecture Notes in Computer Science. – 2003. – Vol. 2658. – Р. 879-887.

Rodionov S. and Choo H. «On Generating Random Network Structures: Connected Graphs», Lecture Notes in Computer Science. – 2003. – Vol. 2658. – Р. 483-491.

Waxman B.M. «Routing of Multipoint Connections», IEEE JSAC. – 1993. – Vol. 9. – Р. 1617-1622.

Грунский И.С. Диагностика местоположения мобильного робота на основе топологической информации о среде / И.С. Грунский, С.В. Сапунов // Искусственный интеллект. – 2011. – № 2. – С. 15-25.

Касьянов В.Н. Графы в программировании: обработка, визуализация и применение / В.Н. Касьянов, В.А. Евстигнеев – СПб.: БХВ-Петербург, 2003. – 1104 c.

Кормен Т.Х. Алгоритмы: построение и анализ / Кормен Т.Х. – М.: Изд. дом «Вильямс», 2005. – [2-е изд.] – 1296 с.

Сапунов С.В. Определение положения робота в топологической среде / Сапунов С.В. // Искусственный интеллект. – 2008. – № 4. – С. 558-565.

Хаггарти Р. Дискретная математика для программистов / Хаггарти Р. – М.: Техносфера, 2003. –320 с.


Посилання

  • Поки немає зовнішніх посилань.