Понятие задачи выбора

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

Пример 1. Есть множество камней, для каждого из которых задана масса. Нужно ответить на вопрос, можно ли разделить данное множество на две равные по массе части. 

Пример 2 (Задача коммивояжера). Коммивояжер (агент по сбыту), отправляясь из своего города, должен ровно по одному разу посетить n -1 заданных городов и вернуться назад, затратив при том минимальную сумму на поездку. Какой маршрут ему выбрать, если затраты на проезд между городами заданы. 

Пример 3. Заданные n масс m ₁, m ₂,..., m_n, требуется распределить в пространстве, в точках M ₁, M ₂,…, M_n, так, чтобы их центр тяжести был максимально близок к фиксированной точке M ₀. 

Для задач выбора характерно:

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

2) каждому варианту сопоставлена числовая характеристика (вес камней в какой либо части, стоимость проезда по маршруту и т.д.).

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

Варианты выбора называются траекториями. Числовая характеристика варианта называется его функционалом.

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

Удобным языком для описания задач выбора и алгоритмов их решения является теория графов.

Пусть V - непустое множество, V ^{2} - множество всех его двухэлементных подмножеств.

Пара (V, E), где Е Í V ^{2}, называется графом (неориентированным графом).

Элементы множества V называют вершинами графа, а элементы множества E – ребрами.

Ориентированным графом (орграфом), называется пара (V, E ¢), где E ¢Í V ´ V.

То есть в ориентированном графе важен порядок вершин составляющих ребро. Обычно в ориентированных графах вместо термина «ребро» используют термин «дуга». [7]

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

Две вершины u и v называются смежными, если множество { u, v } является ребром (дугой), и не смежными в противном случае. Также, в этом случае говорят, что u и v являются концевыми вершинами ребра e ={ u, v }. Для дуги e =(u, v) концевую вершину u называют началом, a v - концом дуги.

Ребра (дуги) называются смежными, если они имеют общую концевую вершину.

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

Ребро e ={ v, v } или дуга e =(v, v) называется петлей.

Ребра e ₁={ u, v }, e ₂={ u, v },..., е_k ={ u, v } называются кратными.

Дуги e ₁=(u, v), e ₂=(u, v),..., е_k =(u, v) называются параллельными.

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

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

Циклом называется цепь, у которой начальная и конечная вершины совпадают.

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

Граф называется связным, если для каждой пары вершин найдется соединяющий их маршрут.

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

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

Граф Н называется подграфом (или частью) графа G, если VH Í VG, ЕН Í EG. Если Н - подграф графа G, то говорят, что Н содержится в G. Подграф Н называется остовным подграфом (или фактором), если VH = VG. Если множество вершин подграфа Н есть U (VH = U), а множество его ребер совпадает с множеством всех ребер графа G, оба конца которых принадлежат U, то Н называется подграфом, порожденным (или индуцированным) множеством U.

Покрывающим (или остовным) деревом графа G называется дерево, являющееся подграфом графа G и содержащее все его вершины.

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

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

Данный граф G однозначно задается матрицей размера n ´ n, где n – число городов, a_i,j - стоимость проезда между городами i и j (которая, вообще говоря, может отличаться от числа a_j,i). При отсутствии дороги между городами i и j полагаем a_i,j =¥.

В теории графов такую матрицу называют матрицей весов.

Не взвешенные графы задаются матрицей смежности, которая получается из матрицы весов если каждый элемент а_ij равный ¥ заменяется на 0 - нет дуги (i, j) (ребра { i, j }), а каждый элемент а_ij не равный ¥ заменяется на 1 - есть дуга (i, j) (ребро { i, j }). Для неориентированных графов матрица смежности будет симметрична относительно главной диагонали.

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

Не взвешенные графы иногда удобно задавать с помощью матрицы инцидентности , размера n ´ m, где n - число вершин, m - число ребер (дуг).

Для неориентированных графов элементы матрицы инцидентности определяется следующим образом:

Для орграфов: