§ 9. Связность в орграфах

В неориентированном графе две вершины либо связаны, либо не связаны, тогда как в орграфе отношение связности узлов несимметрично. Поэтому необходимо это понятие определить по-другому.

Рассмотрим орграф . Пусть – узлы этого графа.

Определение 1.22. Говорят, что два узла и сильно связаны в орграфе G, если существует путь как из в , так и из в . Говорят, что два узла и односторонне связаны в орграфе G, если существует путь либо из в , либо из в . Говорят, что два узла и слабо связаны в орграфе G, если они связаны в графе , являющимся основанием орграфа G.

Если все вершины в орграфе сильно связаны, то орграф называется сильно связанным (рис. 1.35):

Рис. 1.36. Сильно связанный орграф.

Если все вершины в орграфе односторонне связаны, то орграф называется односторонне связанным (рис. 1.36):

Рис. 1.36. Односторонне связанный орграф.

Если все вершины в орграфе слабо связаны, то орграф называется слабо связанным (рис. 1.37):

Рис. 1.37. Слабо связанный орграф.

Заметим, что сильная связность влечет за собой одностороннюю связность, которая в свою очередь влечет слабую связность. Обратное утверждение неверно.

Определение 1.23. Компонентой сильной связности орграфа G называется его максимальный сильно связанный подграф.

Каждый узел орграфа может принадлежать только одной компоненте сильной связности. Если узел не связан с другими, то он сам образует свою компоненту сильной связности.

Глава 2. Алгоритмы § 1. Сложность алгоритмов

В жизни мы часто встречаемся с необходимостью решения одинаковых или похожих задач. Конечно, можно каждый раз творчески подходить к этому процессу, строя решение в каждом конкретном случае. Однако мало у кого есть время и желание заново выводить формулу нахождения корней квадратного уравнения или суммы членов арифметической прогрессии. Необходимо иметь готовые решения для разных классов задач, а значит, существует необходимость в автоматизации вычислительных процессов, т. е. в построении алгоритмов.

Приведем два определения алгоритма. Первое определение введено А. А. Марковым [9]:

«Алгоритм – это точное предписание, определяющее вычислительный процесс, ведущий к искомому результату».

Второе определение принадлежит А. Н. Колмогорову и В. А. Успенскому [7]:

«Алгоритмом принято называть систему вычислений, которая для некоторого класса математических задач из записи А «условий» задачи позволяет при помощи однозначно определенной последовательности операций, совершаемых «механически», без вмешательства творческих способностей человека, получить запись В «решения» задачи».

Таким образом, можно дать следующее описание алгоритма.

Алгоритм – это такая процедура, которая:

1. Применяется к строго определенным исходным данным. Если ее использовать с другим типом данных, то она будет не в состоянии их обработать или выдаст неверный или даже абсурдный результат, не поддающийся анализу.

2. Разбита на отдельные простые шаги.

3. Обработка состояния на каждом шаге осуществляется однозначным способом и зависит лишь от свойств обрабатываемых данных.

4. Процесс длится до тех пор, пока не будет подан сигнал о получении «решения» или невозможности его получения.

Построенный алгоритм в конечном счете предполагает создание программы для ЭВМ. Алгоритмы можно строить разными способами, например, можно разработать такие, которые перебирали бы всевозможные варианты и выбирали подходящий для конкретной задачи. Однако подобный подход нельзя назвать целесообразным. Необходимо иметь более оптимальные способы решения и уметь оценивать трудоемкость различных алгоритмов.

Рассмотрим некоторую абстрактную вычислительную машину, которая может выполнять элементарные операции. К элементарным относятся арифметические операции, операции сравнения, пересылки и операции условной и безусловной передачи управления. Каждая из них выполняется за единицу времени. Таким образом, время работы программы на данной вычислительной машине совпадает с числом выполненных элементарных операций.

Под трудоемкостью (или сложностью) алгоритма будем понимать время работы соответствующей программы на определенной вычислительной машине.

Обычно трудоемкость алгоритмов в задачах на графах оценивается в зависимости от числа вершин или ребер графа.

Пусть – длина входа решаемой задачи (например, число вершин графа) и пусть функция f каждому натуральному числу n ставит в соответствие время работы алгоритма в худшем случае. Тогда f(n) – максимальное время работы алгоритма, или его трудоемкость.

Замечание 2.1. Часто «худшие» случаи для работы алгоритма являются нетипичными, а время работы алгоритма для типичных задач оказывается существенно меньше, чем его формальная трудоемкость. Примером может служить широко используемый для решения задач линейного программирования алгоритм симплекс-метода.

Определение 2.1. Говорят, что неотрицательная функция f(n) не превосходит по порядку функцию g(n), и пишут , если существует такая константа , что

для всех .

Определение 2.2. Говорят, что неотрицательная функция f(n) одного порядка с функцией g(n) и пишут , если существуют константы

такие, что

для всех .

Определение 2.3. Говорят, что неотрицательная функция f(n) является бесконечно малой по отношению к функции g(n) и пишут , если

при .

Определение 2.4. Говорят, что неотрицательная функция f(n) эквивалентна функции g(n), и пишут , если

при .

В дальнейшем будем оценивать трудоемкость алгоритмов во введенных терминах. Если сложность алгоритма равна О(1), то время его работы не зависит от длины входа. Если трудоемкость составляет О(n), то алгоритм называют линейным. Такая трудоемкость означает, что алгоритм является неулучшаемым. Если трудоемкость составляет , где – константа, то алгоритм называют полиномиальным. Такие алгоритмы принято считать эффективными. Однако существует большой класс задач, для которых не найдено полиномиальных алгоритмов. Рассмотрим такие задачи более подробно.