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

    Содержание

    Введение……………………………………………………………………….3

1. История комбинаторики…………………………………………………..4
2. Разделы комбинаторики ….…………………………………..…….….....7
3. Основные понятия………………………………………………………....8
4. Машинное представление графов………………………………………..13
5. Поиск в глубину в графе………………………………………………….17
6. Поиск в ширину в графе………………………………………………….20
7. Заключение………………………………………………………………..23
8. Список использованной литературы………….........................................24

     ВВЕДЕНИЕ 

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

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

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

анализа. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

1. История комбинаторики

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

Древний период

Комбинаторные мотивы можно заметить в символике  китайской «Книги Перемен» (V век  до н. э.). По мнению её авторов, всё в  мире комбинируется из различных  сочетаний мужского и женского начал, а также восьми стихий: земля, горы, вода, ветер, гроза, огонь, облака и небо[1]. Историки отмечают также комбинаторные  проблемы в руководствах по игре в  Го и другие игры. Большой интерес  математиков многих стран с древних  времён неизменно вызывали магические квадраты. 

Классическая  задача комбинаторики: «сколько есть способов извлечь m элементов из N возможных» упоминается ещё в сутрах древней  Индии (начиная примерно с IV века до н. э.).[2]. Индийские математики, видимо, первыми открыли биномиальные коэффициенты и их связь с биномом Ньютона[2]. Во II веке до н. э. индийцы знали, что  сумма всех биномиальных коэффициентов  степени n равна 2n. 

Античные греки также рассматривали  отдельные комбинаторные задачи, хотя систематическое изложение  ими этих вопросов, если оно и  существовало, до нас не дошло. Хрисипп (III век до н. э.) и Гиппарх (II век  до н. э.) подсчитывали, сколько следствий  можно получить из 10 аксиом; методика подсчёта нам неизвестна, но у Хрисиппа получилось более миллиона, а у  Гиппарха — более 100000[3]. Аристотель при изложении своей логики безошибочно  перечислил все возможные типы трёхчленных  силлогизмов. Аристоксен рассмотрел различные  чередования длинных и коротких слогов в стихотворных размерах.[3] Какие-то комбинаторные правила пифагорейцы, вероятно, использовали при построении своей теории чисел и нумерологии (совершенные числа, фигурные числа, пифагоровы тройки и др.).

Магический  квадрат на гравюре Дюрера «Меланхолия»

Средневековье 

В XII веке индийский  математик Бхаскара в своём основном труде «Лилавати» подробно исследовал задачи, связанные с перестановками и сочетаниями, включая перестановки с повторениями. 

В Западной Европе ряд глубоких открытий в области  комбинаторики сделали два еврейских  исследователя, Авраам ибн Эзра (XII век) и Леви бен Гершом (он же Герсонид, XIV век). Ибн Эзра обнаружил симметричность биномиальных коэффициентов, а Герсонид дал явные формулы для их подсчёта и применения в задачах вычисления числа размещений и сочетаний. 

Несколько комбинаторных  задач содержит «Книга абака» (Фибоначчи, XIII век). Например, он поставил задачу найти  наименьшее число гирь, достаточное  для взвешивания любого товара весом  от 1 до 40 фунтов. 
 

Новое время 

Джероламо Кардано  написал математическое исследование игры в кости, опубликованное посмертно. Теорией этой игры занимались также  Тарталья и Галилей. В историю  зарождавшейся теории вероятностей вошла переписка заядлого игрока шевалье де Мерэ с Пьером Ферма  и Блезом Паскалем, где были затронуты  несколько тонких комбинаторных  вопросов. Помимо азартных игр, комбинаторные  методы использовались (и продолжают использоваться) в криптографии —  как для разработки шифров, так  и для их взлома.

Треугольник Паскаля

Блез Паскаль  много занимался биномиальными  коэффициентами и открыл простой  способ их вычисления: «треугольник Паскаля». Хотя этот способ был уже известен на Востоке (примерно с X века), Паскаль, в отличие от предшественников, строго изложил и доказал свойства этого  треугольника. Наряду с Лейбницем, он считается основоположником современной  комбинаторики. Сам термин «комбинаторика»  придумал Лейбниц, который в 1666 году (ему было тогда 20 лет) опубликовал  книгу «Рассуждения о комбинаторном  искусстве». Правда, термин «комбинаторика»  Лейбниц понимал чрезмерно широко, включая в него всю конечную математику и даже логику[4]. Ученик Лейбница Якоб Бернулли, один из основателей теории вероятностей, изложил в своей книге «Искусство предположений» (1713) множество сведений по комбинаторике. 

В этот же период формируется терминология новой  науки. Термин «сочетание» (combination) впервые  встречается у Паскаля (1653, опубликован  в 1665 году). Термин «перестановка» (permutation) употребил в указанной книге  Якоб Бернулли (хотя эпизодически он встречался и раньше). Бернулли использовал  и термин «размещение» (arrangement). 

После появления  математического анализа обнаружилась тесная связь комбинаторных и  ряда аналитических задач. Абрахам  де Муавр и Джеймс Стирлинг нашли  формулы для аппроксимации факториала.[5] 

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

Задача о ходе коня

Задача о семи мостах, с которой началась теория графов

Построение греко-латинских  квадратов

Обобщённые перестановки 

Кроме перестановок и сочетаний, Эйлер изучал разбиения, а также сочетания и размещения с условиями. 

  Современное развитие

В начале XX века начала развиваться комбинаторная  геометрия: были доказаны теоремы Минковского  — Радона, Радона, Хелли, Юнга, Бляшке, а также строго доказана изопериметрическая теорема. На стыке топологии, анализа  и комбинаторики были доказаны теоремы  Борсука — Улама и Люстерника — Шнирельмана. Во второй четверти XX века были поставлены проблема Борсука  и проблема Нелсона — Эрдёша —  Хадвигера. В 1940-х годах оформилась теория Рамсея. Отцом современной  комбинаторики считается Пал  Эрдёш, который ввёл в комбинаторику  вероятностный анализ. Внимание к  конечной математике и, в частности, к комбинаторике значительно  повысилось со второй половины XX века, когда появились компьютеры. Сейчас это чрезвычайно содержательная и быстроразвивающаяся область  математики. 
 
 
 
 
 
 
 

2. Разделы комбинаторики

Перечислительная  комбинаторика

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

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

Типичным примером задач данного раздела является подсчёт количества перестановок. Другой пример — известная Задача о письмах.

Структурная комбинаторика

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

Экстремальная комбинаторика

Примером этого  раздела может служить следующая  задача: какова наибольшая размерность  графа, удовлетворяющего определённым свойствам.

Теория  Рамсея

Теория Рамсея изучает наличие регулярных структур в случайных конфигурациях элементов. Примером утверждения из теории Рамсея может служить следующее:

в группе из 6 человек  всегда можно найти трёх человек, которые либо попарно знакомы  друг с другом, либо попарно незнакомы.

В терминах структурной  комбинаторики это же утверждение  формулируется так:

в любом графе  с 6 вершинами найдётся либо клика, либо независимое множество размера 3. 
 

Вероятностная комбинаторика

Этот раздел отвечает на вопросы вида: какова вероятность  присутствия определённого свойства у заданного множества.

Топологическая  комбинаторика

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

3. Основные понятия комбинаторики 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

а)