История комбинаторики и машинное представление графов

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

   По  поводу отношения на множестве говорят, что оно:

• (а) рефлексивно, если для каждого ,
• (б) транзитивно, если для произвольных ,
• (в) симметрично, если для произвольных ,
• (г) антисимметрично, если для произвольных

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

   Если  функция (отображение) сопоставляет каждому элементу элемент , то будем писать (такая функция может трактоваться как отношение с тем свойством, что для каждого существует в R точно одна пара вида , для наших же целей достаточно, однако, интуитивного понятия функции). Для произвольных определим

: существует такое , что

(вместо ) будем просто писать

   Если , то будем говорить о функции из на . Функция называется обратимой (взаимно однозначной), если для произвольных .

   Мы  часто будем использовать понятие  графа. Под неориентированным графом (или короче графом) будем донимать такую произвольную пару , что

   Ориентированным графом будем называть такую произвольную пару , что и в обоих случаях множества и будем называть соответственно множеством вершин и множеством ребер графа . Граф обычно изображается на плоскости в виде множества точек, соответствующих вершинам, и соединяющих их линий, соответствующих ребрам. Линия, изображающая ребро , или , соединяет точки, изображающие вершины , причем во втором случае стрелка обозначает направление от к (рис. 1.1).

   В контексте  определенного графа будем часто использовать обозначения вместо и соответственно. Если ребро е имеет вид или , то будем говорить, что ребро е инцидентно вершинам и , в то время как вершины и смежны между собой. Степень вершины определим как число ребер, инцидентных ей. Вершину нулевой степени будем называть изолированной (например, вершина на рис. 1.1, а). Путем в графе назовем последовательность вершин , такую, что и (или , если граф — ориентированный), Вершины и будем называть соответственно началом и концом пути, а число — длиной пути. Путь, начало и конец которого совпадают, будем называть циклом. Если все вершины пути различны, то будем говорить об элементарном пути. Соответственно цикл будем называть элементарным, если вершины различны. Подграфом графа будем называть такой произвольный граф , что .

Рис. 1.1: а) неориентированный  граф б) неориентированный граф

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

  Будем говорить, что графы изоморфны, если существует такое взаимно однозначное отображение из на , что для произвольных имеем

в случае ориентированных  графов). Обычно изоморфные графы не различаются между собой.

   Для произвольного  вещественного числа мы будем употреблять обозначения соответственно для наибольшего целого числа, не превосходя

   щего , и для наименьшего целого числа, не меньшего , например ,

   Перейдем  теперь к понятиям, связанным с  алгоритмами. Алгоритмы будем обычно записывать на языке программирования, являющимся неформальной версией языка  Паскаль. Если реализация какого-либо фрагмента программы очевидна, но трудоемка и затемняет идею алгоритма, то такой фрагмент будем иногда заменять описанием на естественном языке. Мы будем также применять неформальные конструкции, такие как, например, циклы ( (выполнять команду для всех элементов множества в произвольной последовательности)), (поместить значение переменной в стек),

(считать элемент из вершины стека и принять его за значение переменной ), (включить в очередь в качестве последнего

элемента), (взять первый элемент из очереди и принять его в качестве значения переменной ) и т.д. Мы будем обычно опускать описания типов и переменных (иногда для избежания недоразумений будем помещать соответствующие пояснения в комментарий). Переменная, появляющаяся в процедуре, рассматривается как локальная для данной процедуры, исключая тот случай, когда в комментарии сказано что-либо иное. Строки программы нумеруются так, чтобы можно было указать на «цикл 17», «блок 9» и т.д.

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

нимать . Сложность алгоритма определяется тогда как функция , такая что

равно наибольшему числу шагов  алгоритма для произвольного  графа с вершинами. Можно также  считать размерностью задачи пару — тогдасложностью является функция двух переменных и равно наибольшему числу шагов, выполняемых алгоритмом для произвольного графа с вершинами и ребрами. Остается еще объяснить точнее, что мы понимаем под «шагом» алгоритма. Допустим, что наши программы транслируются на машинный язык типичной ЭВМ, имеющей в наборе своих команд команды переноса слова из памяти в буфер и наоборот, арифметические операции сложения, вычитания, умножения и деления, условные переходы, операции ввода-вывода, а также косвенной адресации, выполненной аппаратно (т.е. определение аргумента операции через адрес ячейки памяти, содержащей адрес этого аргумента). Выполнение любой из указанных выше команд мы и будем считать шагом алгоритма. Очевидно, что при таком определении шага сложность алгоритма зависит от конкретного вида машинных команд. Однако нас никогда не будет интересовать точная сложность алгоритма, а только асимптотическая сложность, т.е. асимптотическая скорость увеличения числа шагов алгоритма, когда размерность задачи неограниченно растет (чтобы можно было говорить о такой скорости роста, предполагаем, что объем памяти нашего компьютера неограниченный, а также, что каждая ячейка памяти может содержать произвольно большое целое число). Ясно, что при двух произвольных «разумных» способах трансляции соответствующие сложности различаются не более чем на мультипликативную постоянную, а их скорость роста одинакова.

   При сравнении скорости роста двух функций и (с неотрицательными значениями) очень удобны следующие обозначения:

• существуют константы , такие что для всех
• существуют константы , такие что для любого

   Конечно, тогда и только тогда, когда

Символы читаются соответственно: «порядка не более чем

    » и «порядка не менее чем ». Если сложность какого-либо алгоритма есть , то мы говорим, что этот алгоритм «затрачивает порядка времени». Подобным же образом определяются символы и для функции многих переменных, например: существуют константы , такие что для всех

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

4. Машинное представление графов

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

   Мы  будем рассматривать как ориентированные, так и неориентированные графы. Граф мы будем всегда обозначать , где обозначает множе

ство  вершин, а — множество ребер, причем для ориентированного графа и для неориентированного графа. Будем также использовать обозначения

     В теории графов классическим способом представления графа служит матрица инциденций. Это матрица строками, соответствующими вершинам, и m столбцами, соответствующими ребрам. Для ориентированного графа столбец, соответствующий дуге , содержит —1 в строке, соответствующей вершине в строке, соответствующей вершине , и нули во всех остальных строках (петлю, т.е. дугу вида , удобно представлять иным значением в строке , например, 2). В случае неориентированного графа столбец, соответ

а)