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

Автор(и)

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

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-02-13

Номер

Розділ

Математика