а. У багатьох випадка граф ЗРУЧНИЙ задаваті у вігляді матріці суміжності (вершин) або матріці інцідентності.
В Теорії графів Класичним способом представлення графа служити матриця інцідентності. Матриця інцідентності - це матриця А з n рядками, что відповідають вершинам, и m стовпцямі, что відповідають ребрам. Для орієнтованого графу стовпець, что відповідає дузі, містіть - 1 в рядку, что відповідає х, 1 у рядку, что відповідає вершині у, и нулі у всех других рядках.
На рис. 6 збережений орієнтований граф и его матриця інцідентності.
Рис. 6
З алгорітмічною точки зору матриця інціденцій є, Можливо, найбільш Невдалий способом представлення графа. По-перше, ВІН потребує mn комірок памяті, причому більшість ціх комірок зайняті нулями. Незручно такоже и доступ до ІНФОРМАЦІЇ. Відповідь на Елементарна питання типу чи існує ребро {x, y}?, До якіх вершин ведуть ребра Із x? потребуються в гіршому випадка перебору усіх стовпців матріці, а відповідно, m кроків.
КРАЩИЙ способом представлення графа є матриця суміжності, что візначається як матриця B [] розмірності nxn, де 1, ЯКЩО існує ребро, что Йде Із вершини х у вершину у, і 0 - в протилежних випадка.
орієнтований граф и его матриця суміжності зображені на рис. 7.
Рис. 7
Основною ПЕРЕВАГА матріці суміжності є тією факт, что за один крок можна отріматі відповідь на питання чи існує ребро Із х в у?. Недоліком є ??тією факт, что Незалежності від кількості ребер обєм зайнятої памяті Рівний.
Більш Економні у відношенні памяті (особливо у випадка нещільніх графів, коли m набагато менше) є метод представлення графу помощью списку пар, Які відповідають его ребрах (списку інцідентності). Пара відповідає дузі, ЯКЩО граф орієнтований, и ребру у випадка неорієнтованого графу. Очевидно, что обєм памяті в цьом випадка складає 2m. Незручністю являється велика кількість кроків (порядку m в гіршому випадка), Необхідна для Отримання множини вершин, до якіх ведуть ребра з даної вершини.
Список інцідентності, что відповідає графу на рис. 6., Збережений на рис. 8.
Рис. 8
3. Завдання для найбільш Потік
3.1 Постановка задачі
Нехай задана мережа, яка Складається з множини вершин Е і множини дуг, Які з'єднують деякі впорядковані парі вершин, взятих з Є. Припустиме, что вона являє собою симетричний граф, тоб, ЯКЩО дуга () захи до мережі, то до неї входити и симетрично дуга (), хочай в дійсності Такої дуги может и НЕ бути. Для візначеності прісвоюємо вершин мережі наступні номери:. Кожна вершина, характерізується інтенсівністю. Вершини, для якіх> 0 назіваються ДЖЕРЕЛО, вершини, для якіх <0 - стоками, а Інші проміжковімі. За шляхах мережі Направляється однорідна Речовини (газ, Рідина, транспорт) Із джерела в стоки. Кожній дузі () в мережі поставлених у відповідність число Яке назівається Пропускна здатністю дуги. Під Пропускна здатністю дуги розуміють максимальну кількість Речовини, якові вона может Пропустити за Одиниця годині. Нехай и тоді Е0 - єдине джерело, - єдиний СТІК, а - проміжкові вершини мережі.
Ставиться завдання візначіті для заданої мережі максимальну величину потоку Із джерела, в СТІК. Під потоком в мережі будемо розуміті сукупність потоків по всех дугах мережі, де - Потік по дузі, Рівний кількості Речовини, яка переміщується по ній за Одиниця годині. Від...
