r96_3 Пусть (A1,
r96_3 Пусть (A1, ..., An) - произвольная последовательность множеств. Они могут и пересекаться и совпадать. Системой различных представителей для (A1, ..., An) называют такую произвольную последовательность (a1, ..., an), что ai?Ai, 1?i?n, и ai?aj для i?j. Говорят, что в такой системе элемент ai представляет множество Ai.
Теорема Холла. Система различных представителей данного множества существует тогда и только тогда, когда любые k множеств (1?k?n) в совокупности содержат не менее k различных элементов.
Теорема Холла утверждает существование системы различных представителей, но не дает способа нахождения этой системы. Очевидно, что теорема Холла не имеет большого значения с алгоритмической точки зрения, так как проверка всех семейств подмножеств, а их 2n, требует значительных временных затрат. Рассмотрим метод поиска системы различных представителей для нашей задачи.
Обозначим элементы каждой строки нашей таблицы как S1, S2, S3, S4. Cчитаем, что есть множества Si (1?i?n), составленные
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
