Содержание к диссертации
Введение
Глава 1. Свойства комитета системы множеств 23
1.1. Необходимое условие существования комитета 23
1.2. Критерий существования комитета системы одномерных выпуклых множеств 28
1.3. Условия допустимости 34
1.4. Редукция систем множеств 45
Глава 2. Разделение комитетом двух множеств 51
2.1. Критерий разделимости границ двух компактов в комитетом из 2п -f-1 членов 51
2.2. Разделение комитетом двух концентрических окружностей 55
2.3. Теорема о существовании разделяющего комитета 68
Глава 3. Построение комитета системы линейных неравенств 77
3.1. Метод исследования системы линейных неравенств 77
3.2. Процедура нахождения членов комитета 83
3.3. Системы на границе выпуклого т -угольника 98
3.4. Решение задачи о комитете из трех членов 117
3.5. Существование минимального комитета с числом членов, равным мощности системы 124
Заключение 134
Список литературы 135
- Критерий существования комитета системы одномерных выпуклых множеств
- Разделение комитетом двух концентрических окружностей
- Системы на границе выпуклого т -угольника
- Существование минимального комитета с числом членов, равным мощности системы
Введение к работе
Общая характеристика работы
В диссертационной работе изучается два взаимосвязанных круга задач теории несовместных систем неравенств: выяснение условий существования комитета несовместной, в общем случае бесконечной системы неравенств и нахождение методов построения комитета.
Актуальность темы
Исследование несовместных систем линейных неравенств является актуальным направлением в современной математике, поскольку такие системы часто возникают в практических задачах как следствие сложности изучаемых процессов и явлений. Так, например, к несовместной системе линейных неравенств сводится задача обучения распознаванию двух образов, заданных обучающими подмножествами Л и В в Rn, выпуклые оболочки которых имеют непустое пересечение, состоящая в нахождении так называемой разделяющей гиперплоскости, т.е. такой гиперплоскости {х Є Rn : (а,х) - а}, а Є Rn, а Є R, что А С {х : (а,х) > а} и В С {х : (а,х) < а}, где (, ) - скалярное произведение в Rn. Как известно, при условии, что сопуДПсопуБ Ф 0 \ разделяющей Л и В гиперплоскости не существует. Одним из подходов к решению этой задачи, получившим в распознавании образов практическое обоснование [12, 29, 31, 30, 43, 58], является построение некоторой кусочно-постоянной (относительно вектора х) функции вида: я /(g, ai,..., og, ai,..., aqi Лі,..., Лд+і| х) = ^ Л,- sgn ((о,-, х) - оц) + Л?+і, где q - натуральное число, щ,х Є Rn, &і,\і Є R, і = l,q, Xq+i Є R, a
1, если a > 0, sgn a = < -1, в случае, когда a ^ 0. 1 conv С означает выпуклую оболочку конечного множества С
Этот подход состоит в нахождении такого натурального q, совокупности векторов {аг}|=1> вещественных чисел {c*i}f=:i и коэффициентов {Лг}?=1, что Л С {х : f(x) > 0} и В С {ж : /(#) < 0}. При условии, что q -нечетно, Лі = ... = Xq — 1, a A^+i = 0, нахождение функции / сводится к построению комитета системы из |ЛиБ| строгих однородных линейных неравенств (с, г) > 0, с Є A'U (-#), 2 Є Rn+1, (0.1.1) где Л' = {[а, 1] : а Є Л], В' = {[Ь, 1] : b Є В}, \Л U | - мощность множества Л U Б, a z - вектор из п + 1 неизвестного. Точнее, комитетом системы (0.1.1) называется конечный набор (с возможными повторениями) векторов из Rn+1, такой, что каждому неравенству этой системы удовлетворяет более половины его членов. При этом сумма кратностей (повторений) элементов этого набора называется числом его членов. Комитет является обобщением понятия решения на случай несовместности системы (0.1.1). Если система (0.1.1) совместна, комитетом будет, например, набор из одного или нескольких элементов, являющихся решениями этой системы. Комитет с наименьшим для данной системы (0.1.1) числом членов, называется минимальным комитетом. С одной стороны, минимальный комитет соответствует функции / наиболее простого вида, с другой стороны его нахождение непосредственно связано при подходе к обучению распознаванию образов, разработанном В.Н. Вапником [2], с задачей минимизации емкости класса решающих правил (VC-dimension).
В рамках рассматриваемого подхода важными задачами являются нахождение условий существования комитета в общем случае бесконечной системы (ц,х) > 0, і 6 J, Cj,x Є Hn, (0.1.2) отыскание методов построения комитета этой системы с возможно меньшим числом членов, и, в частности, ее минимального комитета. Первые результаты в этом направлении принадлежат Вл.Д. Мазурову [29], который получил критерий существования комитета конечной системы (0.1.2), предложил метод отыскания ее комитета с числом членов, не превосходящим |Jj, и решил задачу о минимальном комитете системы (0.1.2) при п = 2. Далее, в совместной работе [54] М.Ю. Хачай и А.И. Рыбин разви- ли результаты Вл.Д. Мазурова, получили более сильную верхнюю оценку числа членов минимального комитета конечной системы строгих линейных неравенств, а в случае системы (0.1.2) М.Ю. Хачай [51] доказал точность найденной верхней оценки и предложил алгоритм построения комитета с не превосходящим ее числом членов. Вместе с тем задача о минимальном комитете в случае конечной двумерной системы строгих неоднородных линейных неравенств, а также конечной системы (0.1.2) при п > 2 остается нерешенной. В случае двумерной бесконечной системы (0.1.2) А.И. Кри-воногову удалось сформулировать [23] критерий существования комитета. Вопрос нахождения критерия существования комитета и построения минимального комитета бесконечной системы (0.1.2) при п > 2 также является нерешенным.
Комитетом аффинных функций, разделяющим два подмножества Л и В в Жп, называется такой конечный набор аффинных функций, что в любой точке из Л (соответственно из В) более чем половина функций этого набора принимает положительное значение (соответственно отрицательное значение). Задача нахождения условий существования разделяющего комитета и построения минимального по числу членов (функций) разделяющего комитета тесно связана с рассматриваемыми задачами, поскольку любой разделяющий комитет может быть преобразован [29] в комитет некоторой системы (0.1.2), рассматриваемой в Н"+1.
Опыт изучения задачи нахождения условий существования комитета несовместной системы линейных неравенств, имеющего заданное число членов, и построения ее минимального комитета выявил эффективность рассмотрения общей постановки этого вопроса - задачи о существовании и построении комитета или, более общо, р -комитета для произвольной системы неравенств fj(x) >0, j EJ,xeX, (0.1.3) где J и Х- - произвольные множества, 0 < р < 1. При этом, р-комитетом системы (0.1.3) называется конечный набор К (с возможными повторениями) элементов из X такой, что каждому неравенству системы (0.1.3) удовлетворяет более, чем р w(K) членов этого набора, где w(K) - сумма кратностей всех элементов, входящих в набор К. Вл.Д. Мазу- ровым [32], М.Ю. Хачаем [45] и автором данной работы [55] получен ряд необходимых условий существования комитета и р -комитета. Вместе с тем многие вопросы, касающиеся этой задачи, остаются нерешенными.
Цель работы — получение различных условий существования комитета системы нера- венств и нахождение методов его построения. Разработка подходов к решению этих задач как в общем случае, так и в случае, когда система неравенств является: a) конечной или бесконечной системой строгих однородных линейных неравенств в Rn, п > 2; b) конечной двумерной системой строгих неоднородных линейных неравенств; c) конечной системой неравенств, имеющих выпуклые множества ре шений аффинной размерности 1. — формулировка геометрического метода исследования систем линейных неравенств; — изучение задачи нахождения комитета аффинных функций, разделяю- щего два подмножества в R".
Методика исследований
В данной работе используется аппарат теории комитетов, выпуклого анализа, теории линейных неравенств, геометрии, теории чисел и теории множеств.
Научная новизна
В работе разработан оригинальный подход к изучению задачи построения комитета конечной двумерной системы строгих неоднородных линейных неравенств: предложена процедура нахождения членов ее минимального комитета. С помощью данного подхода получен критерий существо- вания комитета двумерной системы, состоящего из трех членов, и найден алгоритм построения такого комитета.
Предложен новый геометрический метод представления системы линейных неравенств в Нп в форме системы точек, основанный на известном преобразовании поляритета. При таком методе решение системы линейных неравенств сводится разделению двух точечных множеств гиперплоскостью, а нахождение комитета - к построению некоторого набора гиперплоскостей. В работе с использованием этого метода обоснован алгоритм построения минимального комитета для одного класса двумерных систем строгих неоднородных линейных неравенств.
В случае произвольной конечной системы неравенств получены необходимые условия существования комитета. С помощью этих условий доказан критерий существования комитета конечной системы неравенств в Ип, имеющих выпуклые множества решений аффинной размерности 1.
Рассмотрено два новых способа построения комитета аффинных функций, разделяющего два подмножества в IRn. С применением одного из них решен ряд задач о разделимости минимальным комитетом аффинных функций границ двух компактов в Нп, один из которых лежит внутри другого; с помощью другого способа получено достаточное условие существования комитета бесконечной системы строгих однородных линейных неравенств в lRn, п > 2.
Теоретическая и практическая значимость
Работа носит теоретический характер. Ее результаты могут быть полезны, в первую очередь, при дальнейшем изучении вопросов существования и построения комитета несовместной системы неравенств. Вместе с тем работа содержит важные утверждения, которые могут быть использованы в геометрии, теории совместных и несовместных систем линейных неравенств.
Структура и объем работы
Диссертация состоит из введения, трех глав, объединяющих 12 параграфов и содержащих 15 иллюстраций, заключения и списка литерату- ры. Главы разбиты на параграфы. Нумерация глав и параграфов в работе сквозная. Нумерация формул и утверждений тройная и однозначно указывает ссылку, сообщая главу, параграф и номер формулы. Общий объем работы - 141 страница. Библиография содержит 61 наименование.
Публикации
Результаты диссертационной работы опубликованы во всероссийских и международных журналах [16, 18, 19, 55, 57], а также в трудах и материалах международных, всероссийских и региональных конференций [14, 15, 17, 20, 21, 56].
Апробация
Результаты диссертационной работы представлялись на следующих конференциях и научных семинарах:
Всероссийская конференция " Математическое программирование и приложения", Екатеринбург (1999, 2003);
Международная конференция "Интеллектуализация обработки информации", Симферополь (2004);
Международная конференция "Распознавание образов и анализ изображений", Санкт-Петербург (2004);
Байкальская международная школа-семинар "Методы оптимизации и их приложения", Иркутск-Северобайкальск (2005);
Региональная молодежная конференция "Проблемы теоретической и прикладной математики", ИММ УрО РАН, Екатеринбург (2005); Научный семинар под руководством академика РАН И.И. Еремина, ИММ УрО РАН, Екатеринбург (2002, 2004, 2005).
Задача о комитете: краткий обзор
Впервые понятие комитета было введено Эйблоу и Кэйлором [50] для конечной системы строгих однородных линейных неравенств в Ип, а Ниль-соном [34] впоследствии был предложен итерационный метод построения комитета такой системы. Понятие комитета очевидным образом [29] рас- пространяется на случай произвольной, в общем случае бесконечной системы неравенств fj(x) > 0, з Є J, х Є X, где X и J - некоторые множества, a f3- - функция, заданная на X, j Є J. Комитетом этой системы называется конечный набор (с возможными повторениями) элементов множества X, такой, что каждому ее неравенству удовлетворяет более, чем половина членов этого набора. Сформулируем две задачи, решению которых посвящена данная работа. Первая из них состоит в выяснении условий существования комитета, или, точнее, комитета с числом членов, равным (или не превосходящим) заданного натурального числа q. Вторая задача состоит в нахождении некоторого комитета, и, в частности, комитета с наименьшим для данной несовместной системы числом членов, называемого минимальным. Далее, для краткости, будем называть эти две задачи соответственно задачей существования комитета и задачей построения комитета.
Приведем основные результаты, полученные для этих двух задач. Рассмотрим систему строгих однородных линейных неравенств (с3,х) > 0, j Є J, Cj,xe ИГ. (0.1.4)
Предположим, что \J\ < со. Вл.Д. Мазуров [29] установил критерий существования комитета системы (0.1.4), предложил алгоритм построения комитета этой системы с числом членов, не превосходящим числа ее неравенств, и, тем самым, указал верхнюю оценку числа членов минимального комитета. При условии, что любая подсистема системы (0.1.4), состоящая из п неравенств, является совместной, М.Ю. Хачай [51] предложил другой алгоритм построения комитета системы (0.1.4), на основе этого алгоритма указал более сильную, чем число неравенств, точную верхнюю оценку числа членов ее минимального комитета, показал [53], что при произвольной размерности п задача о минимальном комитете системы (0.1.4) является NP -трудной. Н.Г. Белецкий предложил [1] один эвристический итерационный метод построения комитета системы (0.1.4), который, как и упомянутый алгоритм Нильсона, не всегда находит комитет, однако в случае совместности системы (0.1.4), находит некоторое ее решение. А.И. Рыбин [40] свел задачу существования комитета системы (0.1.4) из q членов к существованию в некоторой другой системе строгих однородных линейных неравенств совместной подсистемы определенного вида, зависящего от q, и предложил вероятностный метод построения комитета системы (0.1.4).
Эти результаты могут быть переформулированы для задач существования и построения комитета функций [29], разделяющего некоторые два конечных подмножества Ли В, под которым понимается такой конечный набор функций из заданного класса J-^ что в любой точке из Л (соответственно из В) более чем половина функций этого набора принимает положительное значение (соответственно отрицательное значение). Пусть Т - класс линейных или аффинных функций. Как следствие упомянутых результатов Вл.Д. Мазуровым был получен [29] критерий разделения двух конечных подмножеств в IRn комитетом функций, дан алгоритм построения разделяющего комитета и указана верхняя оценка числа членов минимального (по числу функций) разделяющего комитета, равная \AU В\. Положим n'{!F) :=п, если Т - класс линейных функций, и n'(F) := п+1, в случае, когда Т - класс аффинных функций. При условии, что для любых двух подмножеств Л С Л и В' С В, \A'UB'\= n'(F), существует функция / Є F, такая, что Л' С {х : f(x) > 0} и В' С {х : f(x) < 0}, М.Ю. Хачаем в качестве следствия указана [48] точная верхняя оценка числа членов минимального комитета, разделяющего Л и В и дан соответствующий алгоритм построения разделяющего комитета.
Рассмотрим отдельно случай двумерной системы (0.1.4). Вл.Д. Мазуров [29] решил задачу построения минимального комитета конечной системы (0.1.4), предложив алгоритм его нахождения и указав точную верхнюю оценку числа его членов, равную числу неравенств системы (0.1.4). А.И. Кривоногов (см. [23] или книгу [29]) предложил другой алгоритм построения минимального комитета конечной системы (0.1.4), который ему удалось обобщить на случай бесконечной системы, и сформулировал критерий существования комитета бесконечной двумерной системы (0.1.4), указав на основе последнего некоторое достаточное условие существования комитета бесконечной системы строгих однородных линейных неравенств в И". Этот критерий можно переформулировать в форме критерия суще- ствования комитета линейных функций (соответственно, аффинных функций), разделяющего два произвольных, в общем случае бесконечных подмножества на плоскости (соответственно, два подмножества на прямой).
Рассмотрим более общий случай системы строгих линейных неоднородных неравенств (с,-, ж) > bj, j Є J, Cj,x Є R", bj Є IR. (0.1.5)
Пусть \J\ < со. Вл.Д. Мазуров [29] установил критерий существования комитета системы (0.1.5) и предложил способ построения комитета, состоящего из 2|J| —1 членов. Пусть к, q и г - некоторые натуральные числа. В совместной работе М.Ю. Хачай и А.И. Рыбин [54] при условии, что любая подсистема ранга А;, к < г, системы (0.1.5) ранга г имеет комитет не более, чем из q членов, указали верхнюю оценку числа членов минимального комитета этой системы, зависящую от &, q и |J|, и предложили способ построения комитета с числом членов, не превосходящим данной верхней оценки. В этой же работе, в условиях, когда любая подсистема системы (0.1.5) ранга г из к + 1 неравенства, к < г, является совместной, и при этом некоторая подсистема с индексным множеством Jq С J обладает комитетом не более, чем из q членов, они сформулировали еще одну верхнюю оценку числа членов минимального комитета, зависящую от A;, q, \J\ и \Jq\. В случае бесконечной системы (0.1.5) известно лишь некоторое необходимое условие существования комитета, полученное А.И. Кривоно-говым (см. [23] или книгу [29]).
Рассмотрим подробнее задачу о комитете конечной двумерной системы (0.1.5). Обозначим через Jq систему строгих однородных линейных неравенств, полученную из системы (0.1.5) заменой всех свободных коэффициентов последней нулевыми. В предположении, что существует комитет системы Jo? Вл.Д. Мазуров [29] предложил простой алгоритм, при котором минимальный комитет системы Jq преобразуется в комитет системы (0.1.5), и, тем самым указал точную верхнюю оценку числа членов минимального комитета последней, равную числу членов минимального комитета системы Jq. М.Ю. Хачай предложил [44] другой алгоритм построения комитета системы (0.1.5), основанный на свойствах некоторого гиперграфа, поставленного ей в соответствие, и указал более тонкую точ- ную верхнюю оценку числа членов минимального комитета, не превосходящую числа членов минимального комитета системы Jo, зависящую от структуры этого гиперграфа.
Рассмотрим, наконец, наиболее общий случай конечной системы линейных неравенств lj(x) > bj, j = 1,... , m, x Є X, (0.1.6) где X - произвольное вещественное линейное пространство, lj - линейный функционал, a bj Є R, j = l,m. При помощи разложения [49] X = L ф kerF, где L - некоторое конечномерное пространство, F(x) = [h(x),..., lm(x)], х Є X, и kerF - ядро линейного отображения F, Вл.Д. Мазуров свел [29] задачу существования и построения комитета системы (0.1.6) к той же задаче для некоторой конечной системы строгих линейных неравенств в IRn, п — dimL. С помощью этого разложения перечисленные выше результаты для конечных систем линейных неравенств в Rn можно перенести на более общий случай системы (0.1.6).
Приведем некоторые результаты, касающиеся задачи о комитете конечной системы нелинейных неравенств /іМ>0,і = 1,..,т)жЄІ, (0.1.7) где X - банахово пространство, fj - функционал над X, j = l,m. При условии, что для любого j существует производная Фреше /j(0) в точке 0 и fj(0) = 0, Вл.Д. Мазуров [29] доказал, что для существования комитета системы (0.1.7) достаточно существования комитета системы строгих однородных линейных неравенств f'j(0)(x) > 0, j = 1,..., m, х Є X, (0.1.8) и, пользуясь доказанным им критерием для систем линейных неравенств, получил достаточное условие существования комитета системы (0.1.7), указав при этом условии верхнюю оценку числа членов минимального комитета последней, равную числу ее неравенств. Следуя такой схеме перехода от системы (0.1.7) к системе (0.1.8), М.Ю. Хачай получил [59] более сильную, чем число неравенств, верхнюю оценку числа членов минимального комитета системы (0.1.7). Приведем еще один результат, касающийся существования комитета системы (0.1.7), который не вписывается в упомянутую схему. При X = К А.И. Рыбин [39] доказал, что для существования комитета системы (0.1.7) достаточно существования комитета некоторой другой системы т неравенств, такой, что множество решений ее j -го неравенства совпадает с некоторым, в общем случае невыпуклым открытым конусом Kj С Mn, j = I,..., т, и, в условиях, когда п = 2 и для любого j один из двух конусов Kj или JR2\Kj является выпуклым, получил критерий существования комитета такой системы.
Рассмотрим теперь самый общий случай - задачу о комитете системы неравенств fj(x)>0,j = l1...,m,xeX, (0.1.9) где X - произвольное множество. Пусть 0 < р < 1. Назовем р-комитетом системы (0.1.9) конечный набор К (с возможными повторениями) элементов из X, такой, что каждому неравенству системы (0.1.9) удовлетворяет более, чем р w(K) членов этого набора, где w(K) - сумма кратностей всех элементов, входящих в набор К. В частности, при р = \ имеем определение комитета. Пусть s - некоторое натуральное число, 1 ^ s ^ т. При условии, что совместна любая подсистема системы (0.1.9) из s неравенств, Вл.Д. Мазуров [29] доказал существование р -комитета при любом р < ^. Пусть то - мощность наибольшей по числу неравенств совместной подсистемы в системе (0.1.9). Л.П. Власов получил более точный результат [61]: если любые s неравенств системы (0.1.9) образуют совместную подсистему, то существует р -комитет этой системы для любого р < |, где сг - наименьшее натуральное число, для которого am — 5 [р] ^ то - s, k = [^-] , причем J ^ ^. При этом члены р -комитета имеют кратность 1.
Остановимся отдельно на необходимых условиях существования комитета. Вл.Д. Мазуров [32] и автор данной работы [55] получили необходимое условие существования р -комитета системы (0.1.9), состоящее в совместности некоторой ее подсистемы мощности большей, чем число тр. Пусть к и q - натуральные числа, к ^ q. М.Ю. Хачай [45], [46] получил необходимое условие существования комитета из q членов, состоящее в том, что некоторая подсистема системы (0.1.9) достаточно большой мощности, зависящей от A;, q и га, обладает комитетом из к членов.
Упомянем один комбинаторный метод исследования задачи о комитете. Задача существования комитета системы (0.1.9), состоящего из q членов, сведена М.Ю. Хачаем [44] к исследованию структуры некоторого гиперграфа, поставленного в соответствие этой системе, или точнее, к наличию в этом гиперграфе некоторого подгиперграфа определенного вида, зависящего от q. В терминах этого гиперграфа им был дан критерий существования комитета системы (0.1.9), состоящего из трех и из пяти членов.
Рассмотрим вопрос вычислительной сложности задачи о минимальном комитете системы (0.1.9). При условии, что для любого j — 1,..., т множество решений ее jr' -го неравенства является конечным, М.Ю. Хачай доказал [52] сводимость известной задачи о минимальном покрытии конечного множества к задаче о минимальном комитете системы (0.1.9), доказав тем самым NP -трудность задачи о минимальном комитете.
Упомянем также два общих метода построения комитета системы (0.1.9). Вл.Д. Мазуров [29] предложил метод построения минимального комитета системы (0.1.9), при котором вначале находятся так называемые максимальные по включению совместные подсистемы данной несовместной системы (0.1.9), затем вычисляется решение некоторой задачи целочисленного линейного программирования, и, наконец, найденный оптимальный вектор преобразуется в минимальный комитет системы (0.1.9). А.И. Рыбин [39] предложил эвристический алгоритм нахождения комитета системы (0.1.9) и указал условие, при котором этот алгоритм находит комитет, имея при этом полиномиальную вычислительную сложность.
К исследованию задач существования и построения комитета непосредственно примыкают задачи исследования структуры, определяемой максимальными совместными подсистемами несовместной системы. Д.Н. Гайна-нов, В.И. Новокшенов и Л.И. Тягунов [5], изучая свойства некоторого графа, поставленного в соответствие системе строгих однородных линейных неравенств, указали способ построения ее комитета, сводящийся к нахождению в этом графе некоторого цикла нечетной длины.
Близкой к задаче разделения двух конечных подмножеств Л и В в Rn комитетом аффинных функций является задача разделения этих двух множеств в следующем смысле: необходимо найти такой конечный набор гиперплоскостей, что для любых двух точек а. А и b Є В существует строго разделяющая их гиперплоскость этого набора. К.В. Рудаковым дана [36] верхняя и нижняя оценка минимального числа гиперплоскостей, достаточных для разделения в этом смысле любых двух конечных подмножеств Л и В, имеющих заданные мощности и удовлетворяющих условиям общего положения.
Функцию / , имеющую вид: f(q} au ..., aq, аь ..., aq\ х) = J^sgn ({au x) - a*), (0.1.10) где q - нечетно, щ,х Є Hn, a,-, А* Є R, і = 1,(/, Xq+i Є H, можно рассматривать как некий алгоритм а, который относит произвольный вектор х Є Кп к образу, заданному обучающим множеством Л, если f(x) > 0, и к образу, заданному множеством В, в случае, когда f{x) < 0. При этом классификация вектора х алгоритмом а зависит от того, к какому образу этот вектор относит большинство (т.е. не меньше, чем ^у- ) из алгоритмов (7i,..., aq] алгоритм о і относит вектор х Є Rn к образу, заданному множеством Л, если (ai,x) > о>і, и к образу, заданному множеством В, в случае, когда (щ, х) < а*, г = 1,..., q. Тогда, с одной стороны, алгоритм сг безошибочно классифицирует элементы обучающей информации Л U В, или, что то же самое, является корректным в смысле Ю.И. Журавлева, с другой стороны, каждый отдельный алгоритм о^ в силу упомянутого условия conv Л П conv В т^ 0, наоборот, является в этом смысле некорректным. Общей теории построения корректных алгоритмов на множестве некорректных алгоритмов посвящены работы Ю.И. Журавлева и К.В. Рудакова [9, 10, 11, 37].
Другим важным направлением, близким к теме исследований данной работы, является теория решения систем неравенств. В совместной монографии [8] И.И. Еремин и Вл.Д. Мазуров разработали методы решения широкого класса систем неравенств, основанных на применении так называемых фейеровских отображений.
Определения и задачи
Рассмотрим систему подмножеств Т> = {Dj}jej некоторого множества X, где J - необязательно конечное множество индексов. Конечную совокупность элементов множества X, которая может содержать повторяющиеся члены, будем называть набором. Число повторений заданного элемента в наборе назовем его кратностью в этом наборе. Наборы, отличающиеся только порядком записи их членов, отождествляются.
Рассмотрим некоторый набор К. Сумму кратностей всех элементов, входящих в К, назовем числом членов в наборе К и обозначим ее через w(K). Приведем два важных определения, данных в [29].
Определение 0.1.1. Пусть 0 ^ р < 1. Конечный набор К элементов множества X называется р -комитетом системы множеств Х>, если каждому ее множеству Dj принадлежит более, чем p-w(K) элементов набора К с учетом кратности.
В частности, при р — \ имеем определение комитета системы множеств.
Определение 0.1.2. Пусть О < р < 1. Конечный набор К элементов множества X называется слабым р -комитетом системы множеств Т>, если любому ее множеству Dj принадлежит не менее, чем р w(K) членов набора К с учетом кратности.
Любой слабый р -комитет системы множеств V является р' -комитетом этой системы при р' < р. Для системы неравенств fj(x) >0,j Є J,xeX, где fj : X —» IR, j Є J, p -комитетом (соответственно, слабым p-комитетом) является, по определению, р -комитет (соответственно, слабый р -комитет) системы множеств V = {Dj}jej, в которой множество Dj определено формулой: Dj = {х Є X : fj(x) > 0}, j Є J.
Рис. 0.1 На рис. 0.1 показана несовместная система четырех строгих линейных неравенств, каждое из которых изображено полуплоскостью своих решений. Три точки на рисунке образуют комитет этой системы: в полуплоскости решений каждого ее неравенства лежит две из трех точек. Кроме того, эта тройка точек образует слабый | -комитет данной системы.
Сформулируем задачи, рассматриваемые в работе. Пусть Т> — {Dj}jej, Dj С X, X - некоторое множество.
Задача 1 (Существование комитета). Яри каких условиях существует р -комитет, и, в частности, комитет системы множеств V ? Каковы условия существования комитета системы V с числом членов, равным q, где q -натуральное число?
Комитет с наименьшим для данной системы множеств числом членов называется минимальным комитетом [29].
Задача 2 (Построение комитета). Яри условии, что комитет системы множеств V существует, найти комитет этой системы, либо построить ее минимальный комитет.
В работе отдельно рассматриваются важные случаи этих двух задач, при которых система V является системой открытых полупространств-множеств решений неравенств некоторой системы (cj,x) > bjj Є J,Cj,x Є Un,bj Є R (0.1.11)
При этом для краткости будем называть их задачами 1 и 2 для системы линейных неравенств (0.1.11).
Отметим, что задача нахождения минимального комитета является с вычислительной точки зрения одним из наиболее трудных частных случаев задачи 2 и будет рассматриваться в работе отдельно. Сформулируем еще одно определение.
Определение 0.1.3 (Мазуров [29]). Комитетом аффинных функций, разделяющим два подмножества точек А и В пространства IRn, называется такой конечный набор аффинных функций, что в любой точке из Л (соответственно из В ) более чем половина функций этого набора принимает положительное значение (соответственно отрицательное значение).
Рис. 0.2 На рис. 0.2 показано два двухточечных множества, которые не могут быть разделены прямой. Разделяющий эти два множества комитет аффинных функций показан тремя полуплоскостями: каждая его аффинная функция fi, г = 1,2,3, изображена своим множеством уровня {h Є Н2 : fi{h) > 0}; в двух черных точках две из трех функций комитета положительны, а в двух серых точках две его функции отрицательны.
Критерий существования комитета системы одномерных выпуклых множеств
Приведем некоторые результаты, касающиеся задачи о комитете конечной системы нелинейных неравенств где X - банахово пространство, fj - функционал над X, j = l,m. При условии, что для любого j существует производная Фреше /j(0) в точке 0 и fj(0) = 0, Вл.Д. Мазуров [29] доказал, что для существования комитета системы (0.1.7) достаточно существования комитета системы строгих однородных линейных неравенств и, пользуясь доказанным им критерием для систем линейных неравенств, получил достаточное условие существования комитета системы (0.1.7), указав при этом условии верхнюю оценку числа членов минимального комитета последней, равную числу ее неравенств. Следуя такой схеме перехода от системы (0.1.7) к системе (0.1.8), М.Ю. Хачай получил [59] более сильную, чем число неравенств, верхнюю оценку числа членов минимального комитета системы (0.1.7). Приведем еще один результат, касающийся существования комитета системы (0.1.7), который не вписывается в упомянутую схему. При X = К А.И. Рыбин [39] доказал, что для существования комитета системы (0.1.7) достаточно существования комитета некоторой другой системы т неравенств, такой, что множество решений ее j -го неравенства совпадает с некоторым, в общем случае невыпуклым открытым конусом Kj С Mn, j = I,..., т, и, в условиях, когда п = 2 и для любого j один из двух конусов Kj или JR2\Kj является выпуклым, получил критерий существования комитета такой системы.
Рассмотрим теперь самый общий случай - задачу о комитете системы неравенств где X - произвольное множество. Пусть 0 р 1. Назовем р-комитетом системы (0.1.9) конечный набор К (с возможными повторениями) элементов из X, такой, что каждому неравенству системы (0.1.9) удовлетворяет более, чем р w(K) членов этого набора, где w(K) - сумма кратностей всех элементов, входящих в набор К. В частности, при р = \ имеем определение комитета. Пусть s - некоторое натуральное число, 1 s т. При условии, что совместна любая подсистема системы (0.1.9) из s неравенств, Вл.Д. Мазуров [29] доказал существование р -комитета при любом р . Пусть то - мощность наибольшей по числу неравенств совместной подсистемы в системе (0.1.9). Л.П. Власов получил более точный результат [61]: если любые s неравенств системы (0.1.9) образуют совместную подсистему, то существует р -комитет этой системы для любого р , где сг - наименьшее натуральное число, для которого am — 5 [р] то - s, k = [ -] , причем J . При этом члены р -комитета имеют кратность 1.
Остановимся отдельно на необходимых условиях существования комитета. Вл.Д. Мазуров [32] и автор данной работы [55] получили необходимое условие существования р -комитета системы (0.1.9), состоящее в совместности некоторой ее подсистемы мощности большей, чем число тр. Пусть к и q - натуральные числа, к q. М.Ю. Хачай [45], [46] получил необходимое условие существования комитета из q членов, состоящее в том, что некоторая подсистема системы (0.1.9) достаточно большой мощности, зависящей от A;, q и га, обладает комитетом из к членов. Упомянем один комбинаторный метод исследования задачи о комитете. Задача существования комитета системы (0.1.9), состоящего из q членов, сведена М.Ю. Хачаем [44] к исследованию структуры некоторого гиперграфа, поставленного в соответствие этой системе, или точнее, к наличию в этом гиперграфе некоторого подгиперграфа определенного вида, зависящего от q. В терминах этого гиперграфа им был дан критерий существования комитета системы (0.1.9), состоящего из трех и из пяти членов.
Рассмотрим вопрос вычислительной сложности задачи о минимальном комитете системы (0.1.9). При условии, что для любого j — 1,..., т множество решений ее jr -го неравенства является конечным, М.Ю. Хачай доказал [52] сводимость известной задачи о минимальном покрытии конечного множества к задаче о минимальном комитете системы (0.1.9), доказав тем самым NP -трудность задачи о минимальном комитете.
Упомянем также два общих метода построения комитета системы (0.1.9). Вл.Д. Мазуров [29] предложил метод построения минимального комитета системы (0.1.9), при котором вначале находятся так называемые максимальные по включению совместные подсистемы данной несовместной системы (0.1.9), затем вычисляется решение некоторой задачи целочисленного линейного программирования, и, наконец, найденный оптимальный вектор преобразуется в минимальный комитет системы (0.1.9). А.И. Рыбин [39] предложил эвристический алгоритм нахождения комитета системы (0.1.9) и указал условие, при котором этот алгоритм находит комитет, имея при этом полиномиальную вычислительную сложность.
К исследованию задач существования и построения комитета непосредственно примыкают задачи исследования структуры, определяемой максимальными совместными подсистемами несовместной системы. Д.Н. Гайна-нов, В.И. Новокшенов и Л.И. Тягунов [5], изучая свойства некоторого графа, поставленного в соответствие системе строгих однородных линейных неравенств, указали способ построения ее комитета, сводящийся к нахождению в этом графе некоторого цикла нечетной длины.
Близкой к задаче разделения двух конечных подмножеств Л и В в Rn комитетом аффинных функций является задача разделения этих двух множеств в следующем смысле: необходимо найти такой конечный набор гиперплоскостей, что для любых двух точек а. А и b Є В существует строго разделяющая их гиперплоскость этого набора. К.В. Рудаковым дана [36] верхняя и нижняя оценка минимального числа гиперплоскостей, достаточных для разделения в этом смысле любых двух конечных подмножеств Л и В, имеющих заданные мощности и удовлетворяющих условиям общего положения.
Функцию / , имеющую вид: где q - нечетно, щ,х Є Hn, a,-, А Є R, і = 1,(/, Xq+i Є H, можно рассматривать как некий алгоритм а, который относит произвольный вектор х Є Кп к образу, заданному обучающим множеством Л, если f(x) 0, и к образу, заданному множеством В, в случае, когда f{x) 0. При этом классификация вектора х алгоритмом а зависит от того, к какому образу этот вектор относит большинство (т.е. не меньше, чем у- ) из алгоритмов (7i,..., aq] алгоритм о І относит вектор х Є Rn к образу, заданному множеством Л, если (ai,x) О І, и к образу, заданному множеством В, в случае, когда (щ, х) а , г = 1,..., q. Тогда, с одной стороны, алгоритм сг безошибочно классифицирует элементы обучающей информации Л U В, или, что то же самое, является корректным в смысле Ю.И. Журавлева, с другой стороны, каждый отдельный алгоритм о в силу упомянутого условия conv Л П conv В т 0, наоборот, является в этом смысле некорректным. Общей теории построения корректных алгоритмов на множестве некорректных алгоритмов посвящены работы Ю.И. Журавлева и К.В. Рудакова [9, 10, 11, 37].
Разделение комитетом двух концентрических окружностей
Для краткости комитет аффинных функций, разделяющий два подмножества, будем называть разделяющим комитетом. Пусть Л и В - некоторые два подмножества в Rn. Рассмотрим две задачи: Задача 1 (Существование разделяющего комитета). При каких условиях существует комитет, разделяющий два подмножества А и В Задача 2 (Построение разделяющего комитета). Найти комитет, разделяющий два подмножества Л и В в Ип, либо построить минимальный разделяющий их комитет.
Как следует из предложения 0.1.1, получив решение задачи 1 (соответственно, задачи 2 ), заданной в IRn, можно получить решение задачи 1 (соответственно, задачи 2) для соответствующей системы строгих однородных линейных неравенств, заданной в Rn+1.
Глава 1 посвящена наиболее общей постановке задачи 1, в которой система Т и множество X являются произвольными. В 1.1 доказаны полезные свойства комитета в общем случае бесконечной системы множеств. Получено необходимое условие существования р -комитета конечной системы множеств, состоящее в непустоте пересечения всех множеств некоторой ее подсистемы мощности большей, чем тр.
С помощью этого условия в 1.2 дан критерий существования комитета конечной системы одномерных выпуклых множеств в Кп, и, в случае пустоты пересечения всех множеств такой системы, найден ее единственный минимальный комитет. В общем случае, однако, это условие не является достаточным.
В 1.3 указана нижняя оценка числа m(q), равного наименьшему из чисел min{D Є V : х Є D}\ по всем q-членным комитетам К произ-вольной конечной системы множеств V. С помощью этой оценки получено условие, которому должен удовлетворять каждый член комитета из q элементов, и тем самым указано необходимое условие существования такого комитета. Отметим, что данная оценка является точной в классе систем линейных неравенств, в случае, когда q - число членов минимального комитета.
В 1.4 для конечной системы множеств V приводится метод ее редукции к системе ТУ с меньшим числом множеств. При таком методе из системы Т исключается множество D Є V (называемое несущественным), входящее во все максимальные по включению подсистемы системы V с непустым пересечением, содержащие некоторое другое множество Е Т . При этом комитет системы V может быть преобразован в комитет системы Т с сохранением числа членов. В случае системы линейных неравенств в IRn даны признаки несущественности заданного неравенства в этой системе.
Глава 2 посвящена задачам 1 и 2 , где А и В - бесконечные подмножества в R". В 2.1 при некоторых, достаточно сильных ограничениях на множества А и В (разделимость граничной поверхностью некоторого выпуклого многогранника) предложен способ построения комитета, разделяющего эти два множества. При условии, что множества А и В являются границами двух компактов С\ и Сч соответственно, таких, что С\ С int С2, указана нижняя оценка числа членов разделяющего комитета, равная 2п + 1, и доказан критерий существования разделяющего комитета из 2гс + 1 членов. При условии, что число (п — 1) -мерных граней выпуклого многогранника, содержащего внутри С\ и лежащего в intC , с наименьшим числом (п — 1) -мерных граней, равно п 4-1 (соответственно, равно п + 2 ), с помощью данного способа построения комитета найден минимальный комитет, разделяющий А и В, который состоит из 2п+1 членов (соответственно, из 2п + 3 членов).
В 2.2 при помощи упомянутого способа решена задача о минимальном комитете, разделяющем две концентрических окружности радиусов г и Д, О г R. Найденное решение является минимальным комитетом, разделяющим соответствующие круг радиуса г и внешность круга радиуса R. В 2.3 дано достаточное условие существования комитета, разделяющего два бесконечных непересекающихся подмножества в К". Доказано достаточное условие существования комитета бесконечной системы строгих однородных линейных неравенств в R".
В главе 3 рассматриваются задачи 1 и 2 для систем линейных неравенств. В 3.1 предлагается представление произвольной системы строгих линейных неравенств в Ип в форме системы точек, являющейся объединением некоторых двух множеств точек Л и В, где В содержит нулевую точку. При этом решение системы сводится к построению гиперплоскости, строго разделяющей эти два множества, а нахождение комитета системы - к построению такого конечного набора аффинных функций, что в любой точке из Л (соответственно из В) более чем половина функций этого набора принимает положительное значение (соответственно отрицательное значение), причем в нулевой точке отрицательное значение принимают все функции этого набора.
В 3.2 предложена процедура нахождения членов комитета несовместной системы строгих неоднородных линейных неравенств на плоскости, которая состоит в отыскании решения некоторой ее максимальной по включению совместной подсистемы (МСП), называемой в работе отмеченной МСП. Показано что любой (в том числе минимальный) комитет, члены которого суть решения МСП, включает в себя некоторое решение каждой отмеченной МСП. Указаны точные верхние и нижние оценки числа отмеченных МСП в заданной несовместной системе. Доказано, что предложенная процедура, будучи примененной к совместной системе, находит некоторое ее решение.
В 3.3 решена задача о минимальном комитете для двух взаимосвязанных классов систем строгих линейных неравенств. В 3.4 дан критерий существования комитета несовместной двумерной системы строгих неоднородных линейных неравенств, состоящего из трех членов, и предложен алгоритм построения такого комитета.
Системы на границе выпуклого т -угольника
Если т = 4, то тройка точек (С, В, Е) удовлетворяет сформулированному в теореме свойству. Пусть Bj - произвольный отрезок, где j 4 (рис. 1.3). Применяя аналогичное рассуждение к четверкам отрезков {B1,B2,B3,Bj}, {BhB3,B4,Bj} и {Bi,B2,B4,Bj}, получаем, что Bj должен проходить хотя бы через одну из точек в каждой тройке (С, В, Е), (C,F,B) и (C,E,F). Если произвольный отрезок Bj (j 4) проходит через В, то исходя из условия неколлинеарности отрезков, ни одна из вершин треугольника ACEF не лежит на нем. Действительно, если хотя бы одна из вершин С, Е и F лежала на Bj, то этот отрезок был бы кол-линеарен либо отрезку )3, либо отрезку В\. Отсюда получаем, что Bj не может проходить через В. Аналогично, Bj не проходит ни через Е, ни через F. Значит, отрезок Bj должен проходить через точку С. Пусть Do ( EQ ) - крайние (на отрезке В\) точки пересечения отрезка В\ с другими отрезками. Тогда, очевидно, тройка (С, Д , #о) искомая. Следует отметить, что из наших рассуждений также вытекает, что какие-то т — 1 отрезков (в данном случае - В2,..., Вт ) имеют общую точку.
Пусть теперь система отрезков V содержит коллинеарные. Выделим некоторую максимальную (по включению) подсистему V(J ), попарно неколлинеарных отрезков (J \ = s т). Так как исходная система Т имеет комитет, то и ее подсистема D(J ) имеет комитет. Если все отрезки этой подсистемы имеют общую точку, то отрезки исходной системы Т также имеют общую точку. Положив Со, DQ И EQ равными последней, получаем искомую тройку точек.
Пусть теперь отрезки системы Т не имеют общей точки. Согласно доказанному на этапе 1, найдется такая тройка различных точек (Со, Do» о), что каждый отрезок подсистемы D(J ) либо проходит через [DO,EQ], либо проходит через Со и пересекает [DQ,EQ]. При этом С0, D0 и являются точками пересечения отрезков этой подсистемы и Со не лежит на отрезке [D0, EQ] (рис. 1.4). Так как система V имеет пустое пересечение, то подсистема D(J ) включает как отрезок, содержащий [DQ,EO], таки отрезки (не менее двух), проходящие через Со и пересекающие [DQ,EQ]. Точки Со, DQ и. EQ искомые. Пусть Dj - произвольный отрезок системы V. Он коллинеарен одному из отрезков подсистемы D(J ). Пусть i i,... ,Fs-i - точки пересечения отрезков этой подсистемы, проходящих через Со, с отрезком [DQ,EQ]. Возможны следующие случаи: Dj коллинеарен отрезку, проходящему через Со. Тогда Dj проходит через Со в силу условия попарного пересечения с другими отрезками подсистемы T (J ), проходящими через Со. Также у него есть точка пересечения с отрезком этой подсистемы, не проходящим через Со, которая совпадает с одной из точек {FkYfZ1 (b) Dj коллинеарен [DO,EQ]. Тогда Dj проходит через точки Do и EQ, поскольку Dj пересекается с отрезками подсистемы {J ), проходящими через Со- Таким образом, тройка (CQ,DQ,EQ) искомая.
Достаточность. Пусть существует такая тройка точек (Со, Do, Ео), что любое множество системы V либо содержит отрезок [DQ,EQ], либо содержит Со и пересекается с [DQ,EQ]. Если множества системы V имеют общую точку, то она является комитетом. Предположим, что такой точки нет. Тогда точки Со, Do и Ео попарно различны, и, кроме того, Со не лежит на прямой, проходящей через отрезок [Do,Eo] (рис. 1.5). Пусть К = {Со,...,Со,F\,...,Ft}, где F\,...,Ft - все попарно различные точки пересечения отрезка [D0,Eo] с множествами системы V, содержащими точку Со; точка Со имеет кратность t—1, а точки Fi,...,Ft -кратность 1. Оказывается, К - комитет системы Т . Пусть Dj - множество этой системы. Если оно содержит [Do, Ео], то сумма кратностей точек набора К, голосующих за Dj, равна t. В случае, когда множество содержит точку Со, пересекаясь с отрезком [DO,EQ], за Dj голосует точка Со с кратностью i-1 и точка пересечения Dj с отрезком [Do, Ео) с кратностью 1, т.е. сумма кратностей всех членов набора К, голосующих за Dj, равна t. Так как К состоит из 2t — 1 членов, то К - комитет системы D.
Если кратности всех членов комитета системы V равны 1, то комитет состоит из одного или трех членов. Такой комитет может иметь лишь система множеств V, содержащая не более чем три попарно неколлинеарных множества. Пусть система множеств V имеет пустое пересечение и (Со,Д),і?о) -тройка точек с рассматриваемым в теореме 1.2.1 свойством. Предложение 1.2.1. Система V имеет единственный минимальный комитет. Этот комитет имеет вид: и состоит из 2s — 3 членов, где s — мощность максимальной по включению подсистемы системы Т попарно неколлинеарных множеств, JFi,..., Fs-i - все различные точки пересечения отрезка [Do, EQ] с множествами системы Х , содержащими точку Со , точка Со имеет кратность 5 — 2, а точки F\,..., Fs-\ - кратность 1. Доказательство. Из доказательства теоремы 1.2.1 следует, что К является комитетом системы Т . Докажем, что это минимальный комитет. По следствию 1.1.1 точки множества L = {F\,..., Fs_i} входят с некоторой положительной кратностью в любой комитет системы V. Кроме того, против произвольного множества системы, содержащего точку Со и пересекающегося с отрезком [DQ,EO], голосуют некоторые s — 2 точек этого множества. Значит, К - минимальный комитет системы Т , состоящий из 25 — 3 членов. Следовательно, в любом минимальном комитете этой системы все точки множества L имеют кратность, равную 1. Аналогично, точка Со входит с некоторой положительной кратностью в каждый комитет системы V. Поскольку все члены произвольного минимального комитета этой системы, не принадлежащие множеству L, голосуют за каждое множество системы V, содержащее точку Со и пересекающееся с отрезком [DQ,EO], то кратность Со во всех минимальных комитетах одинакова и равна s — 2. Таким образом, К - единственный минимальный комитет системы V.
Существование минимального комитета с числом членов, равным мощности системы
Похожий способ построения комитета для конечной системы множеств рассматривался в [54]. Пусть С\ и С% - компакты в Rn, С\ лежит в ІП1.С2, а множества Л и В -границы С\ и C i соответственно. Для построения минимального комитета будем использовать комитет Км0{Л,В), где MQ - выпуклый многогранник с наименьшим числом (п — 1) -мерных граней, содержащий Л внутри и лежащий внутри (. Далее, будем называть множество Л внутренним множеством, а множество В - внешним множеством.
Теорема 2.1.1. Минимальный комитет, разделяющий внутреннее и внешнее множества, состоит не менее, чем из 2п+1 членов, причем равенство возмоснсно тогда и только тогда, когда существует п -мерный симплекс, содержащий внутри С\ и лежащий в intC2.
Доказательство. Рассмотрим случай, когда С\ = Л = {а}. Пусть К - минимальный комитет, разделяющий внутреннее и внешнее множества. Пусть также К - поднабор в К, содержащий все члены из К, голосующие за точку a, a s - число его членов. Так как а лежит в intC2, то при 5 п+1 пересечение всех полупространств в К содержит некоторый луч с началом в точке а, и против точки пересечения Ъ Є В этого луча с границей ( голосует большинство полупространств в К, что невозможно. Значит, s п 4- 1. Существует комитет Км (Л, В) из 2п + 1 членов, разделяющий внутреннее и внешнее множества, где M Q - симплекс достаточно малого диаметра, содержащий точку а внутри и лежащий внутри Сг- Так как пересечение любых п полупространств набора К содержит некоторый луч с началом в точке а, то против точки пересечения этого луча с границей Сч голосует п членов в К. Следовательно, число членов комитета К равно 2п + 1.
Многогранное множество MQ - пересечение любого поднабора К" в К , состоящего из п + 1 полупространств, содержит точку а и ограничено, т.е. является п -мерным симплексом, лежащим в intC2. Возьмем некоторую вершину и этого симплекса и рассмотрим два противоположно направленных луча с общим началом в этой точке, один из которых направлен по некоторому ребру MQ, инцидентному этой вершине. Каждый из таких лучей лежит в пересечении замыканий некоторых п полупространств в К". В этом пересечении лежит также параллельный луч с началом в точке а. Перенесем оба луча в точку а. Так как любое полупространство, содержащее точку а, содержит также один из этих двух лучей, то при s п + 1 имеется точка b Є В, против которой голосует п+1 член в К , что невозможно, т.е. s = п + 1. Если внутреннее множество неодноточечно, то любой минимальный комитет if, разделяющий внутреннее и внешнее множества, отделяет от внешнего множества любое одноточечное подмножество внутреннего множества, т.е. число его членов не меньше, чем 2п+1. Пусть К состоит из 2п + 1 члена. Для любой точки а.\ Є А существует п-мерный симплекс М , содержащий ее внутри и лежащий во внутренности С2, который порождается некоторым поднабором К из п + 1 полупространства в К. Существует также п -мерный симплекс М", содержащий внутри точку а2 Є А, &2 Ф аь и лежащий во внутренности С2, который ограничивается поднабором К" из п + 1 полупространства в К.
Для произвольной вершины симплекса М рассмотрим два противоположно направленных луча с общим началом в этой точке, один из которых направлен по некоторому ребру М , инцидентному этой вершине. Если некоторое полупространство набора К" содержит эту вершину симплекса М , то оно содержит один из двух таких лучей, а значит, принадлежит набору К . Поскольку полупространства набора К" ограничивают симплекс М", то произвольную вершину симплекса М содержит хотя бы одно из полупространств, входящих в К". Значит, наборы К и К" имеют общий член, граничную гиперплоскость которого обозначим через Н\. Аналогично, вершину (га —1) -мерного симплекса М Г\Н\ содержит некоторое (п — 1) -мерное полупространство, содержащееся на гиперплоскости .#1, которое ограничивает симплекс М" П Н\. Значит, наборы К и К" имеют еще один общий член-полупространство, граничную гиперплоскость которого обозначим через #2- Если п 2, то применяя это же рассуждение к (п — 2) -мерным симплексам М П #і П #2 и М" ПН1ПН2, имеем, что К и К" имеют три общих члена. Продолжая так далее, получим, что наборы К и К" имеют п общих членов-полупространств, а симплексы М и М" - общую вершину, являющуюся пересечением граничных гиперплоскостей этих п полупространств. Пользуясь тем же рассуждением, получим, что наборы К и К" совпадают, а внутреннее множество лежит внутри симплекса М .
Обратно, если существует п-мерный симплекс М, содержащий внутри Сі и лежащий в intC 2, то Км (А, В) - минимальный комитет, разделяющий внутреннее и внешнее множества.
Следствие 2.1.1. Пусть MQ - выпуклый многогранник, содержащий внутри С\ и лежащий в intC2, с наименьшим числом {п — 1) -мерных граней. Если это число равно п + 1 или п + 2, то Км0(Л,В) - минимальный комитет, разделяющий внутреннее и внешнее множества, который состоит из 2п + 1 или из 2п + 3 членов соответственно.
Доказательство. Пусть число (п — 1)-мерных граней многогранника MQ равно п+1. Так как ( -компакт, а С\ лежит внутри MQ, то MQ -n-мерный симплекс. По теореме 2.1.1 Км0{Л, В) - минимальный комитет. Если это число равно п + 2, то по теореме 2.1.1 не существует комитета из 2п+1 членов, разделяющего внутреннее и внешнее множества. Значит, комитет Км0(Л В) является минимальным. -
Пусть на плоскости заданы две концентрических окружности радиусов R и г, 0 г R. Назовем внешней ту из этих окружностей, которая ограничивает круг, содержащий другую окружность. Последнюю, в свою очередь, назовем внутренней окружностью. Рассмотрим задачу о разделении двух концентрических окружностей минимальным комитетом. Проведем вспомогательные построения и установим одно свойство концентрических окружностей. Возьмем произвольную точку d0 на внешней окружности. Проведем из нее две касательные к внутренней окружности. Пусть первая из них пересекает внешнюю окружность в некоторой точке doi, отличной от do, а вторая - в некоторой точке d02 ф d0. Пусть также єоі и ео2 - точки их касания с внутренней окружностью соответственно. Вписанный угол Zdoidodo2 опирается на некоторую дугу 7 внешней окружности. Соединим произвольную точку дуги 7 отрезком с точкой d0. Среди не более чем двух точек пересечения этого отрезка с внутренней окружностью выберем наиболее удаленную от do- Совокупность точек внутренней окружности, полученных таким образом для каждой точки дуги 7» сов
