Моделювання процесу формування територіальних громад як задачі розбиття графу

Автор(и)

  • Василь Володимирович Литвин Національний університет «Львівська політехніка» вул. Степана Бандери, 12, м. Львів, Україна, 79013, Україна https://orcid.org/0000-0002-9676-0180
  • Дмитро Ілліч Угрин Чернівецький факультет Національного технічного університету «Харківський політехнічний інститут» вул. Головна, 203А, м. Чернівці, Україна, 58000, Україна https://orcid.org/0000-0003-4858-4511
  • Андріан Мирославович Фітьо Національний університет «Львівська політехніка» вул. Степана Бандери, 12, м. Львів, Україна, 79013, Україна https://orcid.org/0000-0002-5939-0854

DOI:

https://doi.org/10.15587/1729-4061.2016.60848

Ключові слова:

розбиття графу, генетичний алгоритм, NP-повна задача, територіальна громада, населений пункт

Анотація

Запропоновано підхід до формування територіальних громад на основі розбиття графу на окремі підграфи. Розроблено математичну модель такої задачі. Запропоновано використати генетичні алгоритми для розв’язування задачі формування територіальних громад. Апробовано запропонований підхід. Сформовані територіальні громади задовольняють основним обмеженням.

Біографії авторів

Василь Володимирович Литвин, Національний університет «Львівська політехніка» вул. Степана Бандери, 12, м. Львів, Україна, 79013

Доктор технічних наук, професор

Кафедра інформаційних систем та мереж

Дмитро Ілліч Угрин, Чернівецький факультет Національного технічного університету «Харківський політехнічний інститут» вул. Головна, 203А, м. Чернівці, Україна, 58000

Кандидат технічних наук, доцент

Кафедра інформаційних систем

Андріан Мирославович Фітьо, Національний університет «Львівська політехніка» вул. Степана Бандери, 12, м. Львів, Україна, 79013

Кафедра інформаційних систем та мереж

Посилання

  1. Zakon Ukrai'ny Pro dobrovil'ne ob’jednannja terytorial'nyh gromad. Available at: http://zakon5.rada.gov.ua/laws/show/157-19
  2. Yevstignyeev, V. A. (1985). Application of graph theory in programming. Moscow: Nauka, 352.
  3. Swami, M., Thulasiraman, K. (1984). Graphs, Networks and Algorithms. Moscow: Nauka, 256.
  4. Lytvyn, V., Shakhovska, N., Pasichnyk, V., Dosyn, D. (2012). Searching the Relevant Precedents in Dataspaces Based on Adaptive Ontology. Computational Problems of Electrical Engineering, 2 (1), 75–81.
  5. Dosyn, D., Lytvyn, V. (2012). Planning of Intelligent Diagnostics Systems Based Domain Ontology. The VIIIth International Conference Perspective Technologies and Methods in MEMS Design, Polyana, Ukraine, 103.
  6. Lytvyn, V., Dosyn, D., Medykovskyj, M., Shakhovska, N. (2011). Intelligent agent on the basis of adaptive ontologies construction. Signal Modelling Control. Available at: http://it.p.lodz.pl/
  7. Montes-y-Gómez, M., Gelbukh, A., López-López, A. (2000). Comparison of Conceptual Graphs. Lecture Notes in Artificial Intelligence, 1793, 548–556. doi: 10.1007/10720076_50
  8. Lytvyn, V. (2013) Design of intelligent decision support systems using ontological approach. An international quarterly journal on economics in technology, new technologies and modelling processes, 2 (1), 31–38.
  9. Feldmann, A., Foschini, L. (2012). Balanced Partitions of Trees and Applications. Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, 100–111.
  10. Alzate, C., Suykens, J. A. K. (2010). Multiway Spectral Clustering with Out-of-Sample Extensions through Weighted Kernel PCA. IEEE Transactions on Pattern Analysis and Machine Intelligence, 32 (2), 335–347. doi: 10.1109/tpami.2008.292
  11. Kurve, N., Griffin, J., Kesidis, A. (2011). A graph partitioning game for distributed simulation of networks. Proceedings of the 2011 International Workshop on Modeling, Analysis, and Control of Complex Networks, 9–16.
  12. Chevalier, C., Pellegrini, F. (2008). PT-Scotch: A tool for efficient parallel graph ordering. Parallel Computing, 34 (6-8), 318–331. doi: 10.1016/j.parco.2007.12.001
  13. Meyerhenke, H. (2013). Shape Optimizing Load Balancing for MPI-Parallel Adaptive Numerical Simulations. 10th DIMACS Implementation Challenge on Graph Partitioning and Graph Clustering, 67–82.
  14. Meyerhenke, H., Monien, B., Sauerwald, T. (2009). A new diffusion-based multilevel algorithm for computing graph partitions. Journal of Parallel and Distributed Computing, 69 (9), 750–761. doi: 10.1016/j.jpdc.2009.04.005

##submission.downloads##

Опубліковано

2016-02-27

Як цитувати

Литвин, В. В., Угрин, Д. І., & Фітьо, А. М. (2016). Моделювання процесу формування територіальних громад як задачі розбиття графу. Eastern-European Journal of Enterprise Technologies, 1(4(79), 47–52. https://doi.org/10.15587/1729-4061.2016.60848

Номер

Том 1 № 4(79) (2016): Математика та кібернетика - прикладні аспекти

Розділ

Математика та кібернетика - прикладні аспекти

Ліцензія

Авторське право (c) 2016 Василь Володимирович Литвин, Дмитро Ілліч Угрин, Андріан Мирославович Фітьо

Creative Commons License

Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.

Закріплення та умови передачі авторських прав (ідентифікація авторства) здійснюється у Ліцензійному договорі. Зокрема, автори залишають за собою право на авторство свого рукопису та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons CC BY. При цьому вони мають право укладати самостійно додаткові угоди, що стосуються неексклюзивного поширення роботи у тому вигляді, в якому вона була опублікована цим журналом, але за умови збереження посилання на першу публікацію статті в цьому журналі.

Ліцензійний договір – це документ, в якому автор гарантує, що володіє усіма авторськими правами на твір (рукопис, статтю, тощо).
Автори, підписуючи Ліцензійний договір з ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР», мають усі права на подальше використання свого твору за умови посилання на наше видання, в якому твір опублікований. Відповідно до умов Ліцензійного договору, Видавець ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР» не забирає ваші авторські права та отримує від авторів дозвіл на використання та розповсюдження публікації через світові наукові ресурси (власні електронні ресурси, наукометричні бази даних, репозитарії, бібліотеки тощо).
За відсутності підписаного Ліцензійного договору або за відсутністю вказаних в цьому договорі ідентифікаторів, що дають змогу ідентифікувати особу автора, редакція не має права працювати з рукописом.
Важливо пам’ятати, що існує і інший тип угоди між авторами та видавцями – коли авторські права передаються від авторів до видавця. В такому разі автори втрачають права власності на свій твір та не можуть його використовувати в будь-який спосіб.