цидентні. Кількість використовуваних значень повинно бути мінімально. p align="justify"> Програма повинна бути зручною у використанні. Введення графа повинен здійснюватися через графічний інтерфейс. Повинна бути передбачена правка структури графа на будь-якому етапі роботи з програмою. Розглянутий граф неорієнтоване і не має петель. br/>
3. Практична частина
.1 Розроблений алгоритм
Розроблений алгоритм працює на основі операцій з матрицею суміжності.
Даний алгоритм реалізується наступним чином:
За основу береться матриця суміжності M для даного графа G.
Потім створюється масив A, в кожному рядку якого міститься безліч вершин A [i]. першим елементом цієї множини є вершина Xi0, номер якої збігається з номером рядка. Решта членів цієї множини - всі вершини даного графа G, суміжні першій вершині з цієї множини. p align="justify"> Далі з цим масивом A проводяться наступні маніпуляції:
Безліч вершин A [i] в ​​кожному рядку проглядається, починаючи з другого елементу Xi1 цієї множини A [i], і по матриці суміжності M встановлюється, суміжно чи дана вершина Xij всім попереднім вершин з безлічі A [ i], починаючи з першої - Xi0. Якщо виявляється, що одна з вершин Xij при розгляді не суміжні з іншими вершинами Xik (k = 0, j-1) цієї множини A [i], то вона видаляється з цієї множини. Триває розгляд решти вершин Xij до тих пір, поки множина не розглянутих вершин чи не стане порожнім. Таким чином, з даного безлічі вершин A [i], суміжних з першою вершиною цієї множини - Xi0 будуть видалені всі ті вершини, які не суміжні всім іншим вершин цієї множини A [i]. Таким чином, залишилося безліч вершин A [i] буде максимальним повним подграфом від першої вершини цієї множини Xi0. p align="justify"> Після розгляду одного безлічі A [i] в ​​масиві A розглядаються наступні, за тією ж схемою. З них також видаляються вершини. У кінцевому счече буде отриманий масив A, в кожній i-й рядку якого буде міститися максимально повний підграф A [i], можливий від i-й вершини Xi0. p align="justify"> На наступному кроці алгоритму буде створений ще один масив B, що містить безліч цілих чисел. Кожен i-й елемент B [i] цієї множини B являє собою кількість вершин у відповідному максимально повному підграфі A [i]. Наприклад якщо 3-й елемент даної множини дорівнює 5, це означає, що максимально повний підграф, побудований від 3-ей вершини складається з 5 вершин, включаючи 3-ю. безліч вершин {X30 .. X34}, які складають цей подграф A [3] є мнжеством вершин в 3 рядку масиву A.
Після того, як були створені масиви A і B, створюється лінійний список С, кожен елемент якого містить безліч вершин X, складових унікальний найбільший повний підграф графа G.
Очевидно, що масив A буде містити в собі одіаковие безлічі вершин. Єдиною відмінністю цих множин один...
