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

    Содержание

    Введение……………………………………………………………………….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. Основные понятия комбинаторики 

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

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