я на своєму місці і вихідний масив А розділений на дві невпорядковані частини, бар'єром між якими є елемент A [k]. Подальші дії очевидні - незалежно сортувати отримані частини з тієї ж логікою до тих пір, поки не залишаться частини масиву, що складаються з одного елемента, тобто поки не буде відсортований весь масив. h2> Графи.
Подання графа в пам'яті комп'ютера
Визначимо граф як кінцеве безліч вершин V і набір Е невпорядкованих і впорядкованих пар вершин і позначимо G = (V, E). Потужності множин V і Е будемо позначати літерами N і М Неупорядкована пара вершин називається ребром, а впорядкована пара - дугою. Граф, що містить тільки ребра, називається неорієнтованим; граф, який містить лише дуги, - орієнтованим, або орграфом. Вершини, з'єднані ребром, називаються суміжними. Ребра, що мають загальну вершину, також називаються суміжними. Ребро і будь-яка з його двох вершин називаються інцидентними. Кажуть, що ребро (u, v) з'єднує вершини і та v. Кожен граф можна представити на площині безліччю точок, відповідних вершин, які з'єднані лініями, відповідними ребрах. У тривимірному просторі будь граф можна представити таким чином, що лінії (ребра) НЕ будуть перетинатися.
Способи опису. Вибір відповідної структури даних для представлення графа має принципове значення при розробці ефективних алгоритмів. При вирішенні задач використовуються наступні чотири основних способи опису графа: матриця інціденцій; матриця суміжності; списки зв'язку та переліки ребер. Ми будемо використовувати тільки два: матрицю суміжності і перелік ребер.
Матриця суміжності - це двовимірний масив розмірності N * N. 1, вершина з номером i суміжно з вершиною з номером j, 0, вершина з номером i НЕ суміжно з вершиною з номером j
Для зберігання переліку ребер необхідний двовимірний масив R розмірності М * 2. Рядок масиву описує ребро. h3> Досяжність
Шляхом (або орієнтованим маршрутом) орієнтованого графа називається послідовність дуг, в якій кінцева вершина всякої дуги, відмінною від останньої, є початковою вершиною наступної.
Простий шлях - це шлях, в якому кожна дуга використовується не більше одного разу.
Елементарний шлях - це шлях, в якому кожна вершина використовується не більше одного разу.
Якщо існує шлях з вершини графа v в вершину i, то говорять, що i досяжна з v. p> Матрицю досяжності визначимо наступним чином:
1, якщо вершина i досяжна з v і
R [v, u] = 0, при недосяжності
Безліч R (v) - це безліч таких вершин графа G, кожна з яких може бути досягнута з вершини v. Позначимо через F (v) безліч таких вершин графа G, які досяжні з v з використанням шляхів довжини 1. T2 (v) - це Г (Г (у)), тобто з використанням шляхів довжини 2 і так далі. У цьому випадку:
R (v) = {v} UГ (v) UГ 2 (v) U. .. UГ p (v).
При цьому р - деякий кінцеве значення, можливо, досить велика.
Прик...
