Решение комбинаторных уравнений

 

В комбинаторике тоже могут решаться уравнения, особенностью которых является то, что неизвестная принадлежит множеству натуральных чисел. Например, уравнения вида , xÎN, где N – множество натуральных чисел или вида:

, xÎN (решите!).

При решении комбинаторных уравнений часто необходимо уметь выполнять действия с факториалами типа:

,

или:

.

Например, в задаче о сравнении пар записей в базе данных из n записей:

, – что и требовалось доказать.

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

 

 

Рис. 11. Основные комбинации

 

Комбинаторные задачи могут быть решены, например, системой компьютерной математики Matematica (3,4) фирмы Wolfram Research,Inc. –пакет расширения «Дискретная математика» (DiscreteMath) – комбинаторика и ее функции (Combinatorica, CombinatorialFunctions): функции перестановок и сочетаний и др.

 

ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ

Способы задания графов

 

Совокупность множества М с заданным на нем бинарным отношением ТÌМ² [9] называется графом

G=<M,T>,

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

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

 

Рис. 12. Пример графа «звезда»

 

М={1,2,3,4,5},

Т={(1,3),(1,4),(2,4),(2,5),(3,1),(3,5),(4,2),(4,1),(5,3),(5,2}).

Множество линий-ребер в Т задается обозначением пары (i,j), где i,j – инцидентные вершины, отношение Т – «быть связанным».

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

Первые серьезные результаты теории графов связаны с решением задач построения электрических цепей (Г. Кирхгоф) и подсчета числа химических соединений с различными типами молекулярных связей (А. Кэли). Изобразите в виде графа молекулу

В 30-е годы ХХ века благодаря трудам Д. Кенига [19] теория графов стала развиваться как самостоятельный раздел математики.

Широкое развитие теория графов получила с 50-х годов ХХ века в связи с появлением такой науки, как кибернетика. Графы применяют при анализе функционирования систем. С отдельными компонентами изучаемой системы удобно связывать вершины графа, а с парами взаимодействующих компонент – его ребра. Такой граф называют структурным графом системы.

В некоторых задачах существенно направление ребер графа. Направленные ребра называют дугами, а содержащий их граф – ориентированным (орграфом). Таковым графом может быть изображена диаграмма Хассе. Соответственно граф с неориентированными ребрами называется неориентированным.

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

Рассмотрим предложенную фон Нейманом архитектуру ЭВМ, которая состоит из множества устройств М={а,b,c,d,e}, где а – устройство ввода, b – арифметическое устройство (процессор), с – устройство управления, d – запоминающее устройство, е – устройство вывода [9-10].

Информационный обмен между этими устройствами задается графом (рис. 13).

 

Рис. 13. Граф, описывающий архитектуру

фон Неймановской ЭВМ

 

Вершины графа на рис. 13 для удобства изображены кружками, а не точками, как на рис. 11.

Граф можно задать так называемой матрицей смежности, каждой i-ой строке (j-му столбцу) которой однозначно сопоставляют элемент множества М, между которыми выполняется отношение смежности. Две вершины, инцидентные одному ребру, смежны. Два ребра, инцидентные одной вершине, тоже смежны. Тогда каждая клетка b_ij взаимно однозначно соответствует элементам множества М×М=М². Клетку b_ij, которая соответствует элементу, принадлежащему бинарному отношению ТÌМ², отмечают, например, единицей, а в остальные клетки записывают нули.

Рассмотрим матрицу смежности В для графа, изображенного на рис. 13. Устройства i,j находятся в отношении Т, если из устройства i информация поступает в устройство j.

Граф можно задать и с использованием перечисления его дуг, как это сделано на рис. 13:

М={а,b,с,d,е},

Т={(а,b),(а,с),(а,d),(b,с),(b,е),(b,d),(с,а),(с,b),(с,d),(с,е),(d,с),(d,b),(d,е),(е,с)}.

Граф можно задать в виде так называемого фактор-множества, представленного парами «элемент множества М – подмножество М, представляющее собой окрестность единичного радиуса этого элемента»:

[<a,{b,c,d}>,<b,{c,d,е}>,<c,{a,b,d,e}>,<d,{b,c,e}>,<e,{c}>].

Ориентированный граф может быть задан и матрицей инцидентности А размерностью n×m: A=||a_ij||, где n=|M|, m=|Т|, у которой

если вершина ai является концом дуги tj; если вершина ai является началом дуги tj; если вершина ai не инцидентна дуге tj, , .

 

 

Так, для ориентированного графа (рис. 14) матрица инцидентности имеет вид:

 

Рис. 14. Некоторый ориентированный граф

 

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

Для графов с кратными ребрами в матрице смежности указывают кратность ребер, например, для графа, изображенного на рис. 15, матрица смежности представляется в виде:

Такой граф называют мультиграфом.

 

Рис. 15. Некоторый ориентированный мультиграф

 

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

Представим в виде графа некоторые бинарные отношения [9]. Отношение Т в множестве М рефлексивно, как мы уже знаем, если для каждого элемента mÎМ справедливо (m,m)ÎТ. На графе это изображается петлей (рис. 16а). На матрице смежности графа с рефлексивным отношением все элементы, лежащие на главной диагонали отмечены единицами.

Отношение во множестве М называется симметричным, если из (m_i,m_j)ÎТ следует (m_i,m_j)ÎМ, m_i¹m_j (рис. 16б). Матрица смежности симметричного отношения симметрична относительно главной диагонали.

Отношение Т в множестве М называется транзитивным, если из (m_i,m_j)ÎТ, (m_i,m_k)ÎТ следует (m_i,m_k)ÎТ m_i, m_j,m_kÎМ, m_i¹m_j, m_i¹m_k, m_j¹m_k (рис. 16в).

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

 

Рис. 16. Изображения бинарных отношений в виде графа

а) рефлексивное отношение, б) симметричное отношение,

в) транзитивное отношение

 

Характеристики графов

 

Подграфом G_А графа G=<М,Т> называется граф, в который входит лишь часть вершин графа G, образующих множество А, вместе с ребрами (дугами), их соединяющими.

Так, карта шоссейных дорог Пермской области является подграфом графа «Карта шоссейных дорог Российской Федерации» [18].

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

Так, карта главных дорог России – подграф карты шоссейных дорог России [18].

Если две вершины соединены ребром, то говорят, что каждая вершина инцидентна этому ребру, а соответствующие вершины – смежны (две вершины, инцидентные одному ребру – смежны). Два ребра, инцидентные одной вершине, также смежны.

Маршрут – чередующаяся последовательность вершин и ребер, в которой два соседних элемента инцидентны [26].

Если начальная вершина маршрута равна конечной, то маршрут замкнут, иначе открыт.

Если все ребра различны, то маршрут называется цепью.

Если все вершины (а, значит и ребра) различны, то маршрут называется простой цепью.

Замкнутая цепь – цикл.

Граф без циклов называется ациклическим.

В ориентированном графе цепь называется путем, а цикл – контуром.

Степенью вершины х, обозначаемой deg(х), называют число ребер, инцидентных ей. Если degх=1, то вершина х тупиковая, если degх=0, то вершина изолированная.

Если G – неориентированный граф с n вершинами и m ребрами, а degj – степени j-й вершины, то сумма степеней вершин равна удвоенному количеству ребер:

.

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

Деревья. Лес.

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

Связный граф, не имеющий циклов (ациклический), называется деревом (рис. 17).

Рис. 17. Граф-дерево

 

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

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

В теории графов доказывается, что число различных деревьев, которые можно построить на m вершинах, равно m^m-2. Много деревьев – это лес.

Цикломатическое число.

Пусть G – неориентированный связный граф, имеющий n вершин и m ребер.

Цикломатическим числом связного графа G с n вершинами и m ребрами называется число

n(G)=m-n+1.

Это число имеет интересный физический смысл: оно равно наибольшему числу независимых циклов в графе [18]. При расчете электрических цепей цикломатическое число используется для определения числа независимых контуров.

Рассмотрим примеры подсчета числа независимых циклов.

В графе, состоящем из одной вершины и одного ребра, один цикл (рис. 18а).

В графе, состоящем из одной вершины и трех ребер, три цикла (рис. 18б).

В графе, состоящем из двух вершин и двух ребер, один цикл (рис. 18в).

В графе, состоящем из двух вершин и пяти ребер, четыре цикла (рис. 18г).

В графе, состоящем из трех вершин и трех ребер, один цикл (рис. 18д).

В графе, состоящем из трех вершин и четырех ребер, два цикла (рис. 18е).

В графе, состоящем из четырех вершин и четырех ребер, один цикл (рис. 18ж).

В графе, состоящем из четырех вершин и пяти ребер, два цикла (рис. 18з).

В графе, состоящем из четырех вершин и шести ребер, три цикла (рис. 18и).

Цикломатическое число дерева равно нулю.

Рис. 18. Примеры циклов в графах

 

Плоские (планарные) графы.

Граф называется плоским (планарным), если он может быть изображен на плоскости так, что все пересечения ребер являются вершинами (без пересечения рёбер).

Аналогично можно ввести понятие объемного, т.е. трехмерного графа и т.д.

Хроматическое число графа.

Граф G называют р-хроматическим, где р – натуральное число, если его вершины можно раскрасить р различными цветами так, чтобы никакие две смежные вершины не были раскрашены одинаково. Наименьшее число р, при котором граф является р-хроматическим, называют хроматическим числом графа и обозначают l(G). Если l(G)=2, то граф называют бихроматическим. Необходимым и достаточным условием бихроматичности является отсутствие в графе циклов нечетной длины.

Граф на рис. 19а – бихроматический, его вершины «раскрашены» двумя «цветами», обозначенными 0,1.

Рис. 19. Примеры раскраски графов

 

Граф на рис. 19б можно «раскрасить» тремя цветами, например, черным (ч), красным (к) и белым (б).

Изоморфизм графов.

Как мы убедились, граф может быть задан различными способами. Он может быть изображен на чертеже, задан матрицей инцидентности, списком ребер или матрицей смежности, фактор-множеством и т.д. Вид чертежа зависит от формы линий и взаимного расположения вершин [24]. Иногда не так легко понять, одинаково ли графы, изображенные разными чертежами. Вид матриц и списка ребер зависит от нумерации вершин и ребер графа. Строго говоря, граф считается полностью заданным, если нумерация его вершин зафиксирована; графы, отличающиеся только нумерацией вершин, называются изоморфными.

Например, графы, изображенные на рис. 20, изоморфны [24].

 

Рис. 20. Изоморфные графы а) и б), отличающиеся

только перенумерацией вершин 5®1, 1®5

 

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

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

Если после одной из этих перестановок возникнет матрица, совпадающая с заданной, то сравниваемые графы изоморфны. Для этого требуется максимум n! перестановок, где n – число вершин графа.

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

Если какие-то из этих параметров различны, то эти графы различны. Однако если все параметры у двух графов совпали, это не гарантирует изоморфности, то есть это необходимое, но не достаточное условие [24].

Так, на рис. 21 приведены два графа, у которых эти параметры совпадают, и, тем не менее, они различны [24].

 

Рис. 21. Пример неизоморфных графов а) и б)

 

На рис. 22 приведен граф, изоморфный графу «пятиконечная звезда» (см. рис. 12).

Рис. 22. Граф, изоморфный графу «пятиконечная звезда»

 

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

Псевдограф содержит и ребра, и дуги.

Тривиальный граф содержит только одну вершину.

Иногда граф задают в виде множества образов Г или прообразов Г^-1.

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

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

Множество внешней устойчивости, содержащее наименьшее число вершин, называют наименьшим внешне устойчивым множеством, а число элементов этого множества – число внешней устойчивости графа.

Операции над графами.

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

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

Используются и такие операции, как удаление вершины, удаление ребра, добавление вершины, добавление ребра.

В настоящее время в ЭВМ графы чаще всего задаются списками смежности и массивом указателей на эти списки [26].

Задачи на графах могут быть решены, например, системой компьютерной математики Matematica (3,4) фирмы Wolfram Research,Inc. – пакет расширения «Дискретная математика» (DiscreteMath) – представление графов, создание графов, свойства графов, алгоритмическая теория графов.