Про часову складність алгоритму розкладання графів на різних структурах даних
Для представлення графів у вигляді матриць суміжності та натуральних арифметичних графів проведено оцінку часових складностей алгоритму розкладання графів за допомогою їх кістяків, здійснено порівняння цих складностей. Предложен алгоритм декомпозиции графов с помощью их остовов. Рассмотрено два спос...
Saved in:
| Published in: | Компьютерная математика |
|---|---|
| Date: | 2012 |
| Main Authors: | , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2012
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/84688 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Про часову складність алгоритму розкладання графів на різних структурах даних / Т.О. Гришанович, О.О. Провотар // Компьютерная математика: сб. науч. тр. — 2012. — № 1. — С. 60-68. — Бібліогр.: 7 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859764300489424896 |
|---|---|
| author | Гришанович, Т.О. Провотар, О.О. |
| author_facet | Гришанович, Т.О. Провотар, О.О. |
| citation_txt | Про часову складність алгоритму розкладання графів на різних структурах даних / Т.О. Гришанович, О.О. Провотар // Компьютерная математика: сб. науч. тр. — 2012. — № 1. — С. 60-68. — Бібліогр.: 7 назв. — укр. |
| collection | DSpace DC |
| container_title | Компьютерная математика |
| description | Для представлення графів у вигляді матриць суміжності та натуральних арифметичних графів проведено оцінку часових складностей алгоритму розкладання графів за допомогою їх кістяків, здійснено порівняння цих складностей.
Предложен алгоритм декомпозиции графов с помощью их остовов. Рассмотрено два способа представления графов: матрица смежности и натуральные арифметические графы. Проведено оценку временной сложности данного алгоритма для этих способов, приведено их сравнение.
An algorithm of decomposition of graphs using their skeletons is proposed. Adjacency matrix and natural arithmetic graphs with three generatrices are considered. Time complexity of decomposition algorithms for these data structures is evaluated.
|
| first_indexed | 2025-12-02T04:50:36Z |
| format | Article |
| fulltext |
Компьютерная математика. 2012, № 1 60
Инструментальные
средства
информационных
технологий
Для представлення графів у вигля-
ді матриць суміжності та нату-
ральних арифметичних графів
проведено оцінку часових складно-
стей алгоритму розкладання гра-
фів за допомогою їх кістяків,
здійснено порівняння цих складно-
стей.
Т.О. Гришанович,
О.О. Провотар, 2012
УДК 519.1
Т.О. ГРИШАНОВИЧ, О.О. ПРОВОТАР
ПРО ЧАСОВУ СКЛАДНІСТЬ
АЛГОРИТМУ РОЗКЛАДАННЯ
ГРАФІВ НА РІЗНИХ СТРУКТУ-
РАХ ДАНИХ
Вступ. Значна частина практичних задач, що
виникають при формуванні розкладів, транс-
портуванні, плануванні перевезень, часто
можуть бути представлені як задачі теорії
графів, тісно пов’язані з так званою «задачею
розфарбування» [1].
Розфарбуванням вершин графа G=(V, U) у
k кольорів (або k-розфарбуванням) називають
таке розбиття множини V на k підмножин,
при якому жодні дві суміжні вершини не
мають однакового кольору.
Незважаючи на те, що розкладання графів
за їх вершинами є достатньо відомою зада-
чею, для якої отримано значну кількість ре-
зультатів, вона і на даний час залишається
предметом активних наукових досліджень.
Зокрема, у праці «Розкладання графів» [2]
були запропоновані наступні способи розк-
ладання графів: індуктивний, розкладання за
незалежними множинами, розкладання за
кістяками, розкладання за узагальненими
циклами та променями.
У роботі [3] описано алгоритм розкладан-
ня графів за допомогою їхніх кістяків (на ос-
нові запропонованого методу). У даній робо-
ті досліджується оцінка часової складності
такого алгоритму для двох способів пред-
ставлення графів: матриця суміжності та чис-
лові, зокрема, натуральні арифметичні графи.
Метод проведення оцінки складності
алгоритму. Часова складність алгоритму, як
функція від розміру вхідних даних, є однією
із важливих мір складності алгоритму. Для
того, щоб виконати її обчислення, слід ви-
ЕФЕКТИВНЫЕ МЕТОДЫ РАЗРАБОТКИ СИСТЕМ ДИСТАНЦИОННОГО ОБУЧЕНИЯ
Компьютерная математика. 2005, №2 61
значити час, необхідний для виконання кожної із команд.
ПРО ЧАСОВУ СКЛАДНІСТЬ АЛГОРИТМУ РОЗКЛАДАННЯ ГРАФІВ НА РІЗНИХ СТРУКТУРАХ ...
Компьютерная математика. 2012, № 1 63
Для обчислення складності алгоритму будемо використовувати логарифмі-
чний ваговий критерій. Нехай l(i) – логарифмічна функція на цілих числах, яка
задається наступними рівностями:
log 1, якщо 0,
( )
1 якщо 0.
i i
l i
, i
+ ≠
=
=
Такий критерій базується на припущенні, що ціна виконання команди
(її вага) прямо пропорційна довжині її операндів [4].
Для обчислення кількості операцій алгоритм розкладання графів розбито на
окремі фрагменти (складові частини алгоритму): задання графа, побудова кістяка,
відшукання максимального степеня графа, відшукання мінімальної відстані між
двома вершинами, відшукання кореневої вершини, перевірка кістяка на нормаль-
ність, виправлення кістяка на нормальний та побудова розфарбування графа.
Програмна реалізація та складність алгоритму для представлення
графа у вигляді матриці суміжності
Задання графа. На вході програма отримує кількість вершин графа n та
матрицю суміжності – matrix. Якщо вершини із номерами i та j не з’єднані між
собою ребром, то на перехресті і-го та j-го рядків розміщується число 0, у про-
тилежному випадку – число 1 [1].
for i := 1 to n do
for j := 1 to n do
read (matrix [j, i]);
color [i]:= i.
Масив color використовується як допоміжна структура у процедурі відшу-
кання мінімального кістяка графа (сама процедура описана далі). Будемо вважа-
ти, що змінні i та j набувають максимального значення n, тому покладемо
l(i) = l(j) = l(n).
Задання графа у такому випадку вимагає часу 1 ( )(11 10)t l n n= − +
1 5 1 5( ( ) ( ) 1) ( ) ( ) 3n l M l M l M l M+ + − − − + , де 1 5( ), ( )l M l M – час доступу до
масивів matrix та color, відповідно.
Відшукання максимального степеня – складова частина алгоритму, що
використовується для визначення хроматичного числа графа.
r, max: integer // r – хроматичне число графа, max – допоміжна змінна.
r: = 0;
for i: = 1 to n do
max: = 0;
for j: = 1 to n do
if matrix [i, j] = 1 then max: = max + 1;
if max > r then r: = max.
Середнє значення змінних r та max становить (n – 1). У такому випадку мо-
жна вважати, що ).((max))( nllrl == Час виконання такого фрагменту становить
2 1( )(14 12) ( ) 3.t l n n nl M= − + +
Т.О. ГРИШАНОВИЧ, О.О. ПРОВОТАР
Компьютерная математика. 2012, № 1 64
Побудова кістяка. Для реалізації даного фрагменту обрано алгоритм Пріма –
Краскала. Детальний опис цього алгоритму та значення його часової складності
наводиться в [1].
Відшукання мінімальної відстані між вершинами (алгоритм Дейкстри).
Значна кількість джерел [1, 4] дають досить детальний опис, навіть із готовим
вихідним кодом на мові програмування, алгоритму Дейкстри, тому програмної
реалізації у даній роботі наводити не будемо. Час виконання такого алгоритму
обчислено в [1].
Визначення кореневої вершини. Згідно з означенням, кореневою називають
ту вершину, максимальна відстань від якої до усіх вершин графа є мінімальною
серед таких відстаней.
for i: = 1 to n do
dist [i]: = 0;
for j: = 1 to n do
Dejkstr (n; ks; i, j; length; weight; path);
if (dist [i] < length) and (i<>j) then dist[i]:= length;
min: = dist [1];
for i: = 2 to n do
if min > dist [i] then
min: = dist[i];
sourse: = i;
4 9( )(23 12) (5 ( ) 1) 2t l n n l M n= − + + − − , де 9( )l M – час доступу до масиву
dist. Номер елемента масиву відповідає вершині графа, значення елемента –
максимальній відстані від цієї вершини кістяка до всіх інших.
Побудова допоміжного масиву norm. Такий фрагмент алгоритму будує
масив, що містить інформацію про те, чи перебувають вершини кістяка графа у
відношенні часткового порядку. Масив записів norm має структуру: v_b, v_e –
елементи цілого типу, що відповідають номерам вершин, закінченням ребра,
v_norm – величина логічного типу, що набуває значення ІСТИНА у тому випад-
ку, коли вершини, номери яких містяться у значеннях величин v_b та v_e, порів-
нювані у частковому порядку, заданому кореневою вершиною, та значення ХИ-
БНО – у протилежному випадку. Таким чином після побудови кожного кістяка
графа будується масив norm. У тому випадку коли масив містить хоча б один
елемент із значенням змінної v_norm ХИБНО, відбувається побудова нового кіс-
тяка. У протилежному випадку будується розфарбування графа.
a: = 0;
for a: = 1 to n do
h:= 0;
h1: = false;
for i: = 2 to n do
for j: = 2 to n do
if (matrix [i, j]<>0) and (matrix [i, j]<>1000) and (j > i) then
dejkstr (nn, ks, 1, i, l1, k1, path);
ПРО ЧАСОВУ СКЛАДНІСТЬ АЛГОРИТМУ РОЗКЛАДАННЯ ГРАФІВ НА РІЗНИХ СТРУКТУРАХ ...
Компьютерная математика. 2012, № 1 65
dejkstr (nn, ks, 1, j, l2, k2, path1);
for p: = 0 to n do
h1: = false;
if path1[p] = i then
h1: = true;
h: = h+1;
norm [h].v_b: = i; norm [h].v_e: = j; norm [h]. v_norm: = 1;
if h1 = false then
h: = h+1;
norm [h].v_b: = i; norm [h].v_e: = j; norm [h].v_norm: = 0.
Середнє значення змінних h, i, j, p становить n, тому будемо вважати, що
l(h) = l(i) = l(j) = l(p) = (n). Час виконання такого алгоритму становить 5t =
1 7 6( )(30 2) (16 2 ( ) ( ) 5 ( )) 2l n n n l M l M l M= − − − − − + , де )(),(),( 761 MlMlMl –
час доступу до масивів matrix, norm та path, відповідно.
Виправлення кістяка на нормальний. Такий фрагмент здійснює видален-
ня ребер між вершинами, що не перебувають у відношенні часткового порядку,
та додає ребра у кістяк таким чином, щоб виконувався частковий порядок, зада-
ний кореневою вершиною.
if (norm [i].v_b<>0) and (norm [i].v_norm = 0) then
k3: = 0;
dejkstr (nn, ks, 1, norm [i].a11, l1, k1, path);
dejkstr (nn, ks, 1, norm [i].a12, l2, k2, path1);
if k1 < =K2 then
j: = norm [i].a12;
for p: = 1 to n do
dejkstr (nn, ks, 1, p, l1, k3, path);
if (matrix [p, j] <> 0) and (matrix [p, j] <> 1000) and (ks [p, j] <> 0)
and (k3 < = k1–1) then
ks [p, j]: = 1000; ks [j, p]: = 1000;
ks [norm [i].v_b, norm [i].v_e]: = 1;
ks [norm [i].v_e, norm [i].v_b]: = 1;
norm [i].v_norm: = true;
else
j: = norm [i].v_e;
for p: = 1 to n do
begin
dejkstr (nn, ks, 1, p, l1, k2, path);
if (matrix [p, j] <> 0) and (matrix [p, j] <> 1000) and (ks [p, j] <> 0)
and (k3 < = k1–1) then
ks [p, j]: = 1000; ks [j, p]: = 1000;
ks [norm [i].v_b, norm [i].v_e]: = 1;
ks [norm [i].v_e, norm [i].v_b]: = 1;
norm [i].v_norm: = true;
Т.О. ГРИШАНОВИЧ, О.О. ПРОВОТАР
Компьютерная математика. 2012, № 1 66
2
6 6 5 4( )(2 43 43) (12 ( ) 4 ( ) 6 ( ) 30)t l n n m n m l M l M l M= + + − + + + − −
6 5 412 ( ) 4 ( ) 30 6 ( ).l M l M l M− − − −
Побудова розфарбування. Результатом виконання розфарбування є масив
hi, де номер елемента відповідає номеру вершини, а його значення – кольору.
for i: = 1 to n do
dejkstr (nn, ks, 1, i, l1, k1, path);
hi [i]: = k1 mod a.
Час виконання становить 2
6 1 1( )( 6 2) ( ( ) 2) ( ) 2t l n n n n l M l M= + − + − − + .
Врахувавши кількість виконань кожного із фрагментів, отримаємо наступне
значення часової складності алгоритму розкладання графа за допомогою його
кістяків для представлення графа у вигляді матриці суміжності:
2
4 3 5( )(24 32 43 47) (2 ( ) 3 ( ) ( )l n n n n nl M nl M nl MT m= + + − + + + +
8 4 3 7 6 1 6 52 ( ) 2 ( ) 2 ( ) ( ) 5 ( ) ( ) 18) (12 ( ) 4 ( )l M l M l M l M l M l M m l M l M+ − − − − − + + + +
4 8 3 2 6 1 5 46 ( ) 30) 30 2 ( ) 3 ( ) ( ) 12 ( ) ( ) ( ) 6 ( )l M l M l M l M l M l M l M l M+ − − + + − − − − − .
Програмна реалізація та складність алгоритму для представлення
графа у вигляді натурального арифметичного графа з трьома твірними.
Під натуральним арифметичним графом (NA-графом) будемо розуміти такий
граф, означення якого наведено у [5]. Оцінку часової складності будемо прово-
дити аналогічним до попереднього випадку чином.
Задання графа. Для збереження графа використовується змінна n – кіль-
кість вершин (n ≥ 1), множина твірних – масив U, кількість твірних – р, значен-
ня твірної – а.
read (n);
for p: = 1 to р do
read (IntegerSet [p]);
Тоді задання арифметичного графа вимагає часу 1 7( ) [ ( )t l n p l M= + +
( ) ( ) 1]l p l a+ + − , де l(M7) – час відшукання масиву твірних [6].
Побудова кістяка графа (алгоритм пошуку в глибину). У роботі [6] де-
тально описано даний алгоритм та проведено обчислення часу його виконання.
Перевірка вершин на суміжність – допоміжний алгоритм, що використо-
вується при відшуканні мінімальної відстані між вершинами p1 та p2.
function Connected (p1, p2: integer): boolean;
Result: = false;
if (p1 <> p2) then
for k: = 0 to Length(IntegerSet) – 1 do
if p1 + p2 = IntegerSet [k] then
Connected: = true.
ПРО ЧАСОВУ СКЛАДНІСТЬ АЛГОРИТМУ РОЗКЛАДАННЯ ГРАФІВ НА РІЗНИХ СТРУКТУРАХ ...
Компьютерная математика. 2012, № 1 67
Дотримуючись тих же припущень, що і для попереднього фрагменту алго-
ритму, часова оцінка для алгоритму перевірки вершин на суміжність у NA-графі:
3 7( )(2 1) (2 ( ) ( ) 4) ( ) 2.t l n p p l p l M l p= + + + − − +
Визначення мінімальної відстані між вершинами. Для реалізації цієї час-
тини алгоритму використано алгоритм обходу графа в ширину [1].
function BuildWay (p1, p2: integer): boolean;
var
Q: array of integer; // допоміжний масив, що використовується для позна-
чення вершин
Used: array of boolean; // масив використаних вершин
Levels: array of integer; // кількість рівнів дерева, його глибина
Position, Length, Point: integer; // Position – номер вершини, що розглядаєть-
ся, Length – довжина «пройденої» відстані, Point – номер вершини, що розмі-
щена наступною
i: integer; // лічильник
begin
for i: = 1 to n do
Used [i]: = false;
Used [p1]: = true;
Levels [p1]: = 0;
Q [1]: = p1; // формування черги
Position: = 1;
Length: = 1;
while (Position < = Length) and not (Q [Position] = p2) do
for i: = 1 to n do
if not Used [i] and Connected (Q [Position], i) then
Inc (Length);
Q [Length]: = i;
Levels [i]: = Levels[Q [Position]] +1;
Used [i]: = true;
Inc (Position);
Distance : = 0;
if (Q [Position] = p2) then
Result : = true;
ShortestWay: = p2;
while not (p2 = p1) do
Point: = p2;
for i: = 1 to n do
if Used [i] and Connected (p2, i) and (Levels [i] < Levels [Point]) then
Point: = i;
ShortestWay: = ShortestWay + Point;
Inc (Distance); // змінна, в якій зберігається значення відстані
p2: = Point;
Т.О. ГРИШАНОВИЧ, О.О. ПРОВОТАР
Компьютерная математика. 2012, № 1 68
else
Result : = false;
ShortestWay: = '';
End.
Час відшукання мінімальної відстані між двома заданими вершинами становить:
4 4 2 1( )(4 4 23 22) (4 ( ) 4 ( ) 2 ( )t l n np p n n l M l M l M= − + − + + + +
7 4 2 1 72 (2 ( ) ( 4) 7) 3 ( 3 ( ( 2 (2 ( ) ( 4) 7.) ) ) ) )p l p l M l M l M l M p l p l M+ + − − − − − − + − +
Відшукання кореневої вершини.
for i: = 1 to n do
min_dist: = 0;
source: = 0;
for j: = 1 to n do
max_dist: = 0;
if max_dist < Distance then
max_dist: = Distance
A_sourse [i]: = max_dist;
if min_dist > A_ source [i] then
min_dist: = A_source [i];
source:=i
Час виконання:
5 4 4( )(10 1) ( 6) 4.t l n n n t t= − + − − +
Виправлення кістяка на нормальний.
for i: =1 to n do
for j: = i+1 to (n –1) do
for p: = 1 to 3 do
if (i+j) = u [p] then
if ((Tree [i] ≠ j) or (Tree [j] ≠ i)) then
if BuildWay (source, i) ≥
BuildWay (source, j) then
for f: = 1 to n do
if (T [f] = j or T [j] = f) and BuildWay (source, f) = (BuildWay (source, j) – 1)
then T [j]: = i
else
for f: = 1 to n do
if (T [f] = i or T [i] = f) and BuildWay(source, f) = (BuildWay (source, i) – 1)
then T [i]: = j
Тут Tree – масив, що містить кістяк графа.
6 7 4 4 1( )(26 11) ( ( ) 4 3 ( ) 10) ( ) 2 ( ) 8.t l n n n l M t l p l p t l M= − + + − − − − − −
ПРО ЧАСОВУ СКЛАДНІСТЬ АЛГОРИТМУ РОЗКЛАДАННЯ ГРАФІВ НА РІЗНИХ СТРУКТУРАХ ...
Компьютерная математика. 2012, № 1 69
Обчислення степенів вершин графа та внесення їх до масиву Degrees.
for i: = 1 to n do
k: = 0;
for j: = 1 to n do
for p: = 1 to 3 do
if (i+j = u [p]) and (i <> j) then k: = k+1;
Degrees [i]: = k;
7 7( )(4 7 2) (3 ( ) ( ) 3) ( ( ) 3) ( ) 2.t l n n p p l p l M n l a l p= + − + + − + − − +
Побудова розфарбування графа.
for i: = 1 to n do
color [i]: = BuildWay (i, source) mod degree [i]
8 4 7( )(5 1) ( ( ) (a) 3) 1.t l n n n t l M l= − + + + − +
Врахувавши кількість виконань кожного із фрагментів, отримаємо наступне
значення часової складності алгоритму розкладання графа за допомогою його
кістяків:
7 3 2( )(138 12 9 19p 43) (2 ( ) 5 ( ) 27 ( )T l n n np m n l M l M l M= + + + + + + − −
4 1 7 2 4 130 ( ) 12 ( ) 18 (2 ( ) ( ) 4) (4 ( ) 4 ( ) 2 ( )l M l M p l p l M n l M l M l M− − − + − − + + +
7 7 4 72 (2 ( ) ( ) 11)) (15 ( ) 8 ( ) 29) ( ( ) 2 ( ) ( )p l p l M p l p l M m l M l M l p+ + − + + − + + + −
4 2 17) 9 ( ) 9 ( ) 2 ( ) ( ) 21,l M l M l M l p− + + + − −
де n – кількість вершин графа, m – кількість ребер, р – кількість твірних.
Висновок. Алгоритм декомпозиції графів за допомогою їхніх кістяків від-
носиться до наближених алгоритмів розкладання, які не завжди знаходять точ-
ний розв’язок, але є більш ефективними. Проведена оцінка часової складності
демонструє значну перевагу представлення графів у вигляді числових. Час ви-
конання описаного алгоритму залежить від кількості вершин в обох випадках.
Якщо для матриць суміжності отримали поліноміальне значення складності, то
для натуральних арифметичних таке значення є лінійним. Але для випадку чис-
лових графів наявність у значенні складності таких множників числа n,
як 138, свідчить про те, що цей алгоритм доцільно використовувати для графів
з великою кількістю вершин, тоді як матриці суміжності варто застосовувати
для графів з малою їх кількістю.
Т.А. Гришанович, А.А. Провотар
О ВРЕМЕННОЙ СЛОЖНОСТИ АЛГОРИТМА ДЕКОМПОЗИЦИИ ГРАФОВ
НА РАЗЛИЧНЫХ СТРУКТУРАХ ДАННЫХ
Предложен алгоритм декомпозиции графов с помощью их остовов. Рассмотрено два способа
представления графов: матрица смежности и натуральные арифметичиские графы. Проведе-
но оценку временной сложности данного алгоритма для этих способов, приведено их
сравнение.
Т.О. ГРИШАНОВИЧ, О.О. ПРОВОТАР
Компьютерная математика. 2012, № 1 70
T.А. Grishanovich, А.А. Provotar
ON TIME COMPLEXTY OF THE DECOMPOSITION OF GRAPHS ALGORITHM
FOR DIFFERENT DATA STRUCTURES
An algorithm of decomposition of graphs using their skeletons is proposed. Adjacency matrix and
natural arithmetic graphs with three generatrices are considered. Time complexity of decomposition
algorithms for these data structures is evaluated.
1. Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и
применение. – СПб.: БХВ-Петербург, 2003. – 1104 с.
2. Протасова К.Д. Розкладання графів: дис. ... канд. фіз.-мат. наук / Київський національ-
ний у-т ім. Тараса Шевченка. – К., 2006. – 122 с.
3. Гришанович Т.О. Алгоритм розкладання графів за допомогою їхніх кістяків // Теоретична
електротехніка. – Львів: ЛНУ ім. І. Франка, 2009. – Вип. 60. – С. 12–20.
4. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов:
пер. с англ. А.О. Слисенко. – М.: Мир, 1979. – 536 с.
5. Донец Г.А., Шулинок И.Э. Об общем представлении числовых графов // Теорія
оптимальних рішень. – 2004. – № 3. – С. 11–18.
6. Донец Г.А., Неженцев Ю.И. Об оценке сложности алгоритмов в арифметических графах
// Методы решения задач нелинейного и дискретного программирования. – 1991. –
С. 79–87.
7. Донец Г.А., Шулинок И.Э. О хроматическом числе натуральных арифметических графов
с тремя образующими // Теорія оптимальних рішень. – 2008. – № 7. – C. 50–60.
Получено 10.10.2011
Про авторів:
Гришанович Тетяна Олександрівна,
аспірантка факультету кібернетики
Київського національного університету ім. Тараса Шевченка,
grtanja@rambler.ru
Провотар Олександр Олександрович,
бакалавр факультету кібернетики
Київського національного університету ім. Тараса Шевченка.
|
| id | nasplib_isofts_kiev_ua-123456789-84688 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | ХХХХ-0003 |
| language | Ukrainian |
| last_indexed | 2025-12-02T04:50:36Z |
| publishDate | 2012 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Гришанович, Т.О. Провотар, О.О. 2015-07-12T17:39:24Z 2015-07-12T17:39:24Z 2012 Про часову складність алгоритму розкладання графів на різних структурах даних / Т.О. Гришанович, О.О. Провотар // Компьютерная математика: сб. науч. тр. — 2012. — № 1. — С. 60-68. — Бібліогр.: 7 назв. — укр. ХХХХ-0003 https://nasplib.isofts.kiev.ua/handle/123456789/84688 519.1 Для представлення графів у вигляді матриць суміжності та натуральних арифметичних графів проведено оцінку часових складностей алгоритму розкладання графів за допомогою їх кістяків, здійснено порівняння цих складностей. Предложен алгоритм декомпозиции графов с помощью их остовов. Рассмотрено два способа представления графов: матрица смежности и натуральные арифметические графы. Проведено оценку временной сложности данного алгоритма для этих способов, приведено их сравнение. An algorithm of decomposition of graphs using their skeletons is proposed. Adjacency matrix and natural arithmetic graphs with three generatrices are considered. Time complexity of decomposition algorithms for these data structures is evaluated. uk Інститут кібернетики ім. В.М. Глушкова НАН України Компьютерная математика Инструментальные средства информационных технологий Про часову складність алгоритму розкладання графів на різних структурах даних О временной сложности алгоритма декомпозиции графов на различных структурах данных On time complexty of the decomposition of graphs algorithm for different data structures Article published earlier |
| spellingShingle | Про часову складність алгоритму розкладання графів на різних структурах даних Гришанович, Т.О. Провотар, О.О. Инструментальные средства информационных технологий |
| title | Про часову складність алгоритму розкладання графів на різних структурах даних |
| title_alt | О временной сложности алгоритма декомпозиции графов на различных структурах данных On time complexty of the decomposition of graphs algorithm for different data structures |
| title_full | Про часову складність алгоритму розкладання графів на різних структурах даних |
| title_fullStr | Про часову складність алгоритму розкладання графів на різних структурах даних |
| title_full_unstemmed | Про часову складність алгоритму розкладання графів на різних структурах даних |
| title_short | Про часову складність алгоритму розкладання графів на різних структурах даних |
| title_sort | про часову складність алгоритму розкладання графів на різних структурах даних |
| topic | Инструментальные средства информационных технологий |
| topic_facet | Инструментальные средства информационных технологий |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84688 |
| work_keys_str_mv | AT grišanovičto pročasovuskladnístʹalgoritmurozkladannâgrafívnaríznihstrukturahdanih AT provotaroo pročasovuskladnístʹalgoritmurozkladannâgrafívnaríznihstrukturahdanih AT grišanovičto ovremennoisložnostialgoritmadekompoziciigrafovnarazličnyhstrukturahdannyh AT provotaroo ovremennoisložnostialgoritmadekompoziciigrafovnarazličnyhstrukturahdannyh AT grišanovičto ontimecomplextyofthedecompositionofgraphsalgorithmfordifferentdatastructures AT provotaroo ontimecomplextyofthedecompositionofgraphsalgorithmfordifferentdatastructures |