Матричне подання операцій над графами

Автор(и)

  • Н. А. Якімова Одеський національний університет імені І. І. Мечникова, Україна
  • М. Є. Клішин Одеський національний університет імені І. І. Мечникова, Україна

DOI:

https://doi.org/10.18524/2519-206X.2022.1-2(39-40).294314

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

орiєнтований та неорiєнтований граф, матриця сумiжностi, матриця iнцидентностi, операцiї над графами, елементарнi логiчнi операцiї, булева матриця, багатозначна логiка

Анотація

Теорія графів має широке розповсюдження з практичної точки зору. Графи оточують нас у повсякденному житті (наприклад, карти доріг та шляхів), а також відіграють важливу роль в наукових дослідженнях (наприклад, електросхеми). Для побутового застосування, безумовно, найзручнішим є геометричний спосіб подання графів. Але для комп'ютерної обробки інформації це не є раціональним. В цих випадках використовується матричне подання графів у вигляді матриць суміжності або матриць інцидентності. Тому все більшого значення набувають дослідження, присвячені саме цій темі. В даній статті розглядається можливість виконання операцій над матрицями, якими подано графи. Ці методи мають свої особливості та обмеження. Вони також розглянуті в даній статті. Для кожної операцій запропонований варіант обробки як матриці суміжності, так і матриці інцидентності для орієнтованих та неорієнтованих графів, показано відмінності такої обробки в залежності від виду графу.

Посилання

Gvozdinskaya, N. A., Dudar, Z.V., Poplavskiy, S. A., Shabanov-Kushnarenko, Y. P. (1998). O logicheskikh matritsakh [On logical matrix]. Problemy bioniki, Vol. 48, P. 12–22.

Yakimova, N. A. (2019). Predykatni logichni matritzi [Predicative logical matrices]. Visnyk Odes’kogo Natzional’nogo universitetu. Researches in Mathematics and Mechanics, Vol. 24, No. 2(34), P. 67–74.

Shaporev, S. D. (2005). Matematicheskaya logika [Mathematical logic]. St-Peterburg: BHV-Peterburg, 416 p.

Yakimova, N. A. (2021). Dyskretna matematyka. Chastyna 1. Teoriya mnozhin. Teoriya grafiv [Discrete Math. Part 1. Set theory. Graf theory]. Odessa: ONU im. I. I. Mechnikova, 102 p.

Zykov, A. A. (2007). Lektzii z algebry [Lectures on algebra]. Odessa: Astroprint, 400 p.

Kapitonova, Yu. V., Kryvyy, S. L., Letychevskiy, O. A., Lutzhkiy, G. M. and Pechurin, M. K. (2002). Osnovy dyskretnoi matematyky [Foundation of Discrete Mathematics]. Kyiv: Naukova dumka, 578 p.

##submission.downloads##

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

2024-03-15

Номер

Том 27 № 1-2(39-40) (2022)

Розділ

Математика

Ліцензія

Авторське право (c) 2022 2022

Creative Commons License

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

Автори, які публікуються у цьому журналі, погоджуються з наступними умовами:

  1. Автори залишають за собою право на авторство своєї роботи та передають журналу право першої публікації цієї роботи на умовах ліцензії Attribution-NonCommercial 4.0 International (CC BY-NC 4.0).
  2. Автори мають право укладати самостійні додаткові угоди щодо неексклюзивного розповсюдження роботи у тому вигляді, в якому вона була опублікована цим журналом (наприклад, розміщувати роботу в електронному сховищі установи або публікувати у складі монографії), за умови збереження посилання на першу публікацію роботи у цьому журналі.
  3. Політика журналу дозволяє і заохочує розміщення авторами в мережі Інтернет (наприклад, у сховищах установ або на особистих веб-сайтах) роботи, оскільки це сприяє виникненню продуктивної наукової дискусії та позитивно позначається на оперативності та динаміці цитування опублікованої роботи (див. The Effect of Open Access).