Избранные главы дискретной математики (стр. 4 из 7)
Скорость сходимости этого алгоритма пропорциональна
. Это означает буквально то, что не более, чем через 
сравнений, мы либо найдем нужное значение, либо убедимся в его отсутствии.§6 Теория графов
Теория графов — раздел дискретной математики, изучающий свойства графов. Первая работа по теории графов принадлежит Леонарду Эйлеру. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов. Но термин «граф» впервые ввел в 1936 году венгерский математик Денеш Кениг.
Графами называются схемы, состоящие из точек и соединяющих эти точки отрезков прямых или кривых.
Таким образом, ребро определяется парой вершин. Два ребра, у которых есть общая вершина, называются смежными (или соседними).
Графы, в которых не построены все возможные ребра , называются неполными графами. В противном случае граф называется полным.
Если полный граф имеет n вершин, то количество ребер будет равно
.Граф называется ориентированным (или орграфом), если некоторые ребра имеют направление. Это означает, что в орграфе некоторая вершина может быть соединена с другой вершиной, а обратного соединения нет. Геометрически граф часто изображают точками плоскости, причем соседние вершины соединены дугами (для орграфа некоторые дуги имеют направление, что обычно отмечают стрелкой).
Помимо этого, в теории графов рассматриваются также мультиграфы – это такие графы, в которых могут быть петли (т. е. некоторая вершина соединена сама с собой ребром) или некоторые пары вершины могут быть соединены между собой несколькими ребрами.
Маршрут в графе – это последовательность соседних (смежных) вершин. Ясно, что можно определить маршрут и как последовательность смежных ребер (в этом случае ребра приобретают направление). Заметим, что в маршруте могут повторяться вершины, но не ребра. Маршрут называется циклом, если в нем первая вершина совпадает с последней.
Путь в графе (иногда говорят простой путь) – это маршрут без повторения вершин (а значит, и ребер).
Контур – это цикл без повторения вершин, за исключением первой вершины, совпадающей с последней.
Последовательности вершин (рис. 1): 1–2–3–4–2–5 не простой путь, а маршрут; последовательности 1–2–3–4–7–5 и 1–2–5 – простые пути; 1–2–3–4–2–5–6–1 –это цикл (но не контур); 1–2–5–6–1 – это контур.Рис.2
Граф называется связным, если любые две его вершины можно соединить маршрутом (или путем). На рис.2 изображен связный граф.
Ребро, при удалении которого граф перестает быть связным, иногда называют мостом или перешейком.
Следующее определение имеет смысл только для графов или мультиграфов без петель (но не для орграфов).
Степень вершины – это число ребер, входящих в эту вершину. Вершина называется висячей, если ее степень равна единице.
Кликой в неориентированном графе называется подмножество вершин, каждые две из которых соединены ребром графа. Иными словами, это полный подграф первоначального графа. Размер клики определяется как число вершин в ней.
Двудольный граф или биграф — это математический термин теории графов, обозначающий граф, множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет какую-то вершину из одной части с какой-то вершиной другой части, то есть не существует ребра, соединяющего две вершины из одной и той же части.
Применение теории графов
· Теория графов находит применение, например, в геоинформационных системах (ГИС). Существующие или вновь проектируемые дома, сооружения, кварталы и т. п. рассматриваются как вершины, а соединяющие их дороги, инженерные сети, линии электропередачи и т. п. — как рёбра. Применение различных вычислений, производимых на таком графе, позволяет, например, найти кратчайший объездной путь или ближайший продуктовый магазин, спланировать оптимальный маршрут.
· В химии (для описания структур, путей сложных реакций[1], правило фаз также может быть интерпретировано как задача теории графов); компьютерная химия — сравнительно молодая область химии, основанная на применении теории графов. Теория графов представляет собой математическую основу хемоинформатики. Теория графов позволяет точно определить число теоретически возможных изомеров у углеводородов и других органических соединений.
· В информатике и программировании
· В коммуникационных и транспортных системах. В частности, для маршрутизации данных в Интернете.
· В экономике
· В логистике
§7 Комбинаторика
Термин "комбинаторика" был введён в математический обиход Лейбницем.
В 1666 году Лейбниц опубликовал "Рассуждения о комбинаторном искусстве". В своём сочинении Лейбниц, вводя специальные символы, термины для подмножеств и операций над ними находит все k -сочетания из n элементов выводит свойства сочетаний.
Элиаким Гастингс Мур (1862-1932) ввёл термин тактическая конфигурация в статье "Tactical memoranda", понимая под этим термином систему n множеств, содержащих, соответственно, a1, a2, … , anэлементов.
Термин "тактика" ввёл в математику английский математик Джеймс Джозеф Сильвестр (1814-1897) в 1861 году. Сильвестр определял тактику как раздел математики, изучающий расположение элементов друг относительно друга. В сфере этого раздела находится, по мнению Сильвестра, теория групп, комбинаторный анализ и теория чисел.
Комбинаторика (Комбинаторный анализ) — раздел математики, изучающий дискретные объекты, множества (сочетания, перестановки, размещения и перечисление элементов) и отношения на них (например, частичного порядка). Комбинаторика связана со многими другими областями математики — алгеброй, геометрией, теорией вероятностей, и имеет широкий спектр применения, например в информатике и статистической физике.
Условно в комбинаторной теории можно выделить следующие три большие части (см. схему):
· Теорию конфигураций, включающую блок - схемы, группы подстановок, теорию кодирования.
· Теорию перечисления, содержащую производящие функции, теоремы обращения и исчисление конечных разностей.
· Теорию порядка, включающую конечные упорядоченные множества и решётки, матрицы и теоремы существования, подобные теоремам Холла и Рамсея.
Теория конфигураций является традиционным и наиболее разработанным разделом комбинаторики. Теория конфигураций рассматривает задачи выбора и расположения элементов некоторого, обычно конечного, множества, в соответствии с заданными правилами. Перечислительная комбинаторика основным методом исследования провозгласила метод производящих функций, используя который было доказано громадное число комбинаторных тождеств.
В комбинаторике производящая функция последовательности {an} — это формальный степенной ряд
Зачастую производящая функция последовательности чисел является рядом Тейлора некоторой аналитической функции, что может использоваться для изучения свойств самой последовательности. Однако, в общем случае производящая функция не обязана быть аналитической.
Элементарными комбинаторными конфигурациями являются сочетания, размещения, перестановки. Для подсчёта числа этих конфигураций используются правила суммы и произведения.
Примерами комбинаторных конфигураций являются:
· Размещением из n элементов по k называется упорядоченный набор из k различных элементов некоторого n-элементного множества.
· Перестановкой из n элементов (обычно чисел 1,2,…,n) называется всякий упорядоченный набор из этих элементов. Перестановка также является размещением из n элементов по n.
· Сочетанием из n по k называется набор k элементов, выбранных из данных n элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений.
Основные свойства сочетаний:
1.Условились, что
2.
3.
4.
· Композицией числа n называется всякое представление n в виде упорядоченной суммы целых положительных чисел.
· Разбиением числа n называется всякое представление n в виде неупорядоченной суммы целых положительных чисел.
Правило суммы:
Если элемент A можно выбрать m способами, а элемент B можно выбрать k способами, то выбор элемента A или B можно осуществить m + k способами.
Правило суммы можно перефразировать на теоретико-множественном языке. Обозначим через | A | число элементов множества A, через A
B - объединение множеств A и B, через A 
B - декартово произведение множеств A и B. Тогда для непересекающихся множеств A и B выполняется равенство: