ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 8770
Скачиваний: 13
6
методов теоретического исследования и практического решения
широкого класса задач на графах.
4. Теория игр во многих случаях существенно выгадывает,
когда ее построение ведется на языке теории графов.
5. Графы широко используются в математической лингвисти-
ке, теории кодирования, в машиностроении, физике, химии и пр.
Среди задач комбинаторной теории выделяются следующие
группы задач.
1. Задачи на размещение. Эта группа задач рассматривает
способы расположения на плоскости объектов, обладающих
свойством дальнодействия.
2. Задачи о покрытиях и заполнениях. В них отыскивают
числа и способы возможных покрытий заданной плоской фигуры
площадками определенных форм и размеров или заполнений за-
данных пространственных фигур меньшими телами заданных
форм и размеров.
3. Задачи о маршрутах. К ним относятся задачи о комми-
вояжере. Как правило, это задачи на оптимизацию.
4. Комбинаторные задачи теории графов. В теории графов
особенно велика роль задач и методов комбинаторного характера. В
этой связи можно отметить задачу раскраски графов, рассечение
ребер графов, перечисление графов определенной структуры и др.
5. Перечислительные задачи. В таких задачах речь может
идти, например, о числе электрических цепей, составляемых из
данного набора элементов при соблюдении определенных пра-
вил, о числе возможных блоков электронных вычислительных
устройств, составленных из набора элементов или структур этих
элементов и др.
В задачах комбинаторного характера исследуются дискрет-
ные множества. Как правило, эти множества конечные. Особен-
ностью комбинаторных исследований является то, что в них пре-
имущественное внимание уделяется двум видам операций: отбо-
ру подмножеств и упорядочению элементов. Эти операции и яв-
ляются комбинаторными.
В комбинаторных задачах различают три вида проблем:
а) перечислительные задачи, т.е. подсчет числа возможных
решений;
7
б) проблема существования решений, т.е. теоретическая
возможность;
в) выработка алгоритмов отыскания нужного решения (вы-
борки, расположения), удовлетворяющих условиям задачи.
Несмотря на кажущуюся ограниченность, с логической точ-
ки зрения, класса комбинаторных задач, последние оказываются
весьма различными как по характеру, так и по методам решения.
Это объясняется разнообразием как самих множеств, так и произ-
водимых из них выборок.
Задачи теории графов и комбинаторики, как правило, про-
сты и наглядны по своей постановке. Их можно решать по от-
дельности, без построения общих теорий и обладая достаточным
запасом, если не таланта, то хотя бы терпения и свободного вре-
мени. В связи с этим имели место попытки подвести целиком
теорию графов под какие-либо из уже сложившихся разделов ма-
тематики.
Эти попытки оказались несостоятельными. Правда, аппарат
алгебры нередко удается использовать здесь не только как вычис-
лительное средство, но и как орудие использования, однако в изу-
чении графов слишком большую роль играет чисто комбинаторное
искусство, недостаточно охваченное алгебраической наукой. Тео-
рии графов нужен свой специфический аппарат, прочно опираю-
щийся на алгебру и насквозь пронизанный комбинаторикой.
Основные обозначения
Перечислим обозначения, которые будут использованы в
последующем. Понятия трактуются чисто содержательно безот-
носительно к выбору системы аксиом.
x
∈Α – «элемент х принадлежит А».
x
∉Α – «элемент х не принадлежит А».
Α⊆Β – «А есть подмножество множества В».
Α⊂Β – «Α⊆Β и Α≠Β».
xy
– упорядоченная пара элементов х,y.
y
x~ –
неупорядоченная пара элементов х,y.
∅ – пустое множество.
8
A
–
количество элементов (мощность) множества А
(кар
-
динальное
число
множества
A
).
B
A
∪ – объединение множеств А и В.
U
n
I
i
i
A
∈
– объединение множеств А
i
, где
i пробегает индексное
множество I.
Α
∩
Β
– пересечение множеств А и В.
∩
n
I
i
i
A
∈
–
пересечение множеств А
i
, где i пробегает индексное
множество I.
A\B – множество тех элементов множества А, которые не
принадлежат множеству В (при этом не предполагается, что обя-
зательно
Β⊆Α
).
M
¬ – «не М» (логическое отрицание высказывания М).
Μ&Ν – «М и N» (конъюнкция высказываний М и N).
i
M
n
i 1
&
=
–
конъюнкция
высказываний
М
1
,
М
2
, . . . ,
М
n
.
Μ∨Ν
– «
М
или
N» (
дизъюнкция
высказываний
М
,N,
до
-
пускающая
их
одновременную
истинность
).
i
M
n
i 1
=
∨
–
дизъюнкция
высказываний
М
1
,
М
2
, . . . ,
М
n
.
Μ⇒Ν
– «
из
М
следует
N»;
если
М
,
то
N (
логическое
след
-
ствие
,
или
импликация
).
Μ⇔Ν
– «
М
равнозначно
N» (
необходимое
и
достаточное
условие
,
логическая
равносильность
).
∀
x
∈ΑΜ
(x) – «
для
любого
элемента
х
множества
А
истинно
высказывание
М
(
х
)
об
этом
элементе
» (
логическая
формула
с
квантором
общности
по
элементу
).
∀Χ⊆ΑΜ
(
Χ
)
– «
для
любого
подмножества
Х
множества
А
истинно
высказывание
М
(X)
об
этом
подмножестве
«(
логическая
формула
с
квантором
общности
по
множеству
).
∃
x
∈ΑΜ
(
x
)
– «
существует
хотя
бы
один
такой
элемент
х
в
множестве
А
,
что
высказывание
М
(
х
)
об
этом
элементе
истинно
«(
логическая
формула
с
квантором
существования
по
элементу
).
9
∃
Χ∈ΑΜ
(
X
)
–
«
существует
такое
подмножество
X
множест
-
ва
А
,
что
высказывание
М
(X)
об
этом
подмножестве
истинно
»
(
логическая
формула
с
квантором
общности
по
множеству
).
Q
(
x
)
– «
элемент
х
обладает
свойством
Q «(
одноместный
предикат
).
R(x,y) – «
элемент
х
находится
в
отношении
R
к
элементу
y».
P(x,u,y) – «
упорядоченная
тройка
элементов
х
, u, y
находит
-
ся
в
отношении
Р
» (
трехместный
предикат
).
{x/M(x)} –
множество
всех
тех
элементов
х
,
для
которых
ис
-
тинно
высказывание
М
(
х
).
10
1
ТЕОРЕТИЧЕСКИЕ
ОСНОВЫ
КОМБИНАТОРНОГО
АНАЛИЗА
1.1
Основные
определения
Объектом
исследования
в
комбинаторном
анализе
и
теории
графов
являются
дискретные
множества
и
их
элементы
.
Множество
S,
состоящее
из
n
элементов
,
будем
называть
n-
множеством
S.
Элементы
n-
множества
обозначаются
строчными
латинскими
буквами
a, b, c, d,....
Если
любой
элемент
а
∈Α
оказы
-
вается
также
элементом
другого
множества
S,
то
А
есть
подмно
-
жество
множества
S,
А
⊆
S.
Если
А
⊆
S
и
S
⊆А
,
то
оба
множества
равны
,
А
=S.
Если
А
⊆
S,
но
А
≠
S,
то
А
есть
собственное
подмножество
множества
S,
Α⊂
S.
Основными
операциями
над
множествами
являются
операции
объединения
и
пересечения
:
объединение
(
сумма
) F=S
∪
T,
пересе
-
чение
G=S
∩
T.
Если
некоторые
множества
T
i
∩
T
j
=
∅
при
всех
i, j =
=1,2,... r, i
≠
j,
то
М
=
Т
1
∪Т
2
∪
...
∪
Т
r
называют
разбиением
множества
М
на
непересекающиеся
подмножества
,
или
просто
разбиением
.
Кроме
операций
объединения
и
пересечения
мы
будем
упот
-
реблять
декартово
(
или
прямое
)
произведение
множеств
: S
×
T,
т
.
е
.
множество
всех
упорядоченных
пар
вида
(
а
,
в
),
где
а
∈
S,
в
∈Т
.
Кардинальное
или
мощность
число
произведения
,
очевидно
,
равно
произведению
кардинальных
чисел
множеств
-
сомножите
-
лей
.
Прямое
произведение
,
распространенное
на
случай
k-
сомножителей
,
представляет
множество
всех
упорядоченных
k-
выборок
,
в
которых
каждый
из
элементов
принадлежит
одному
из
множеств
-
сом
-
ножителей
.
Опыт
выполнения
комбинаторных
операций
отбора
под
-
множеств
привел
к
двум
логическим
правилам
−
правилу
суммы
и
правилу
произведения
.
Часто
удается
разбить
все
изучаемые
комбинации
на
несколько
классов
,
причем
каждая
комбинация
входит
в
один
и
только
один
класс
.
Ясно
,
что
в
этом
случае
общее
число
комбинаций
равно
сумме
чисел
комбинаций
во
всех
клас
-
сах
.
Это
утверждение
называется
правилом
суммы
.