Дискретная математика (998286), страница 51
Текст из файла (страница 51)
Перекрасим вершины 2 +з 4 в той компоненте связности графа Сз4, которой принадлежит оз, и получим 5-раскраску графа С -е, в которой цвет 2 свободен для о. П 1 ! 1 ! 1 1 1 1 1 1 От Рис. 12.2. Иллюстрация к доказательству теоремы о пяти красках 12.3. Алгоритмы раскрашивания В этом разделе на примере алгоритмов раскрашивания графов вводится понятие приближенного алгоритма в более широком смысле по сравнению с тем, кото- рый обычно подразумевается в вычислительной математике и при проведении численных расчетов на ЭВМ. 12.3.1. Точный алгоритм раскрашивания Рассмотрим следующую схему рекурсивной процедуры Р: 1. Выбрать в графе С некоторое максимальное независимое множество вершин Я. 2. Покрасить вершины множества Я в очередной цвет.
3. Применить процедуру Р к графу С вЂ” Я. Вход: граф С(К Е), номер свободного цвета т. Выход: раскраска, заданная массивом С]Ъ'], — номера цветов, приписанные вершинам. 11 У = а 0 теогтв ( раскраска закончена ) енй 1т Я: = Яе1есьшах(С) (3 — максимальное независимое множество ) С]Я] г = т ( раскрашиваем вершины множества Я в цвет 1 ) Р(С вЂ” Я, т + 1) ( рекурсивный вызов ) 2В7 12.3. Алгоритмы раскрашивания ЗАМЕЧАНИЕ Функция Яе1есьтпак может быть реализована, например, алгоритмом 11.2А.
ТЕОРЕМА Если граф С И-раскрашиваемый, то существует такая последовательность выборов множества 5 на шаге 1 процедуры Р, что применение процедуры Р к графу С построит не более чем А-раскраску графа С. Докязяткльство Пусть имеется некоторая А-раскраска графа С(У, Е). Перестроим ее в не более чем й-раскраску, которая может быть получена процедурой Р. Пусть Уг с У— множество вершин в данной Й-раскраске, покрашенных в цвет 1. Множество У,— независимое, но, может быть, не максимальное.
Рассмотрим множество Уг, такое что Уг 0 У вЂ” максимальное независимое множество (может оказаться, что У ' = е). Вершины из У,' не смежны с У„значит, вершины из У„' можно перекрасить в Цвет 1. ПУсть Далее Уз С У1,(Уг 1.1 Уг') — множество веРшин, покРашенных в цвет 2. Аналогично рассмотрим множество Уз', такое что Уз О Уз' — максимальное независимое в С1(У, О Уг ), покРасим веРшины Уз 0 Уз' в цвет 2 и т. д.
Всего в исходной раскраске было )г независимых множеств, При перекраске их число не возрастет (но может уменьшиться, если т(С) с к). На каждом шаге алгоритма рассматривается одно из множеств, следовательно, процесс закончится. П 12.3.2. Приближенный алгоритм последовательного раскрашивания В предыдущем подразделе алгоритм точного раскрашивания был построен на основе алгоритма выделения максимальных независимых множеств вершин, который имеет переборный характер. Таким образом, алгоритм точного раскрашивания также имеет переборный характер. В таких случаях целесообразно рассматривать приближенные алгоритмы, которые не всегда находят точное решение задачи (иногда они находят только приближение к нему, и мы не можем знать зтого заранее), но зато достаточно аффективны. Рассмотрим следуюший алгоритм последовательного раскрашивания. Алгоритм 12.1.
Алгоритм последовательного раскрашивания Вход: гоаф С. Выход: раскраска графа — массив С: аггау [1..р[ ог 1..р. (ог о е У Йо С[о[: = О ( все не раскрашены ) епа гог гог ю я У Оо А: =(1,..., р) ( все цвета ) гог о я Г+(о) к[о А; = А 1 (С[и]) ( занятые для о цвета ) епд (ог 2ВВ Глава 12. Раскраска графов С[о]: = поп А ( минимальный свободный пает ) епо' 1ог ЗАМЕЧАНИЕ Таким образом, красить вершины необходимо последовательно, выбирая среди допустимых цветов минимальный. ОБОСНОВАНИЕ В основном цикле рассматриваются все вершины, и каждая из них получает допустимую раскраску, таким образом, процедура строит допустимую раскраску П 12.3.3. Улучшенный алгоритм последовательного раскрашивания Следующий алгоритм также строит допустимую раскраску, применяя такую звристику: начинать раскрашивать следует с вершины наибольшей степени, поскольку, если их раскрашивать в конце процесса, то более вероятно, что для них не найдется свободного цвета и придется задействовать еще один цвет.
Алгоритм 12.2. Улучшенный алгоритм последовательного раскрашивания Вход: граф С. Выход: раскраска графа — массив С: актау [1..р] от 1..р. Яогс(е) ( упорядочить вершины по невозрастанпю степени ) с: = 1 ( первый цвет ) гоген и оо С[о]: = О ( все не раскрашены ) епд Гог тгЫе У ф я По Гог о е Ъ' по Гог и е Г+ [е) оо К С[и] = с ГЬеп пехФ 1ог о ( вершину е нельзя покрасить в цвет с ) епо Ы епп 1ог С[о]: = с ( красим вершину е в цвет с ) У: = У '1 (э) ( и удаляем ее из рассмотрения ) еш1 гег с: = с+ 1 ( следующий цвет ) епд тг[п1е ОБОСНОВАНИЕ Заметим, что данный алгоритм отличается от предыдущего тем, что основной цикл идет не по вершинам, а по цветам: сначала все что можно красим в цвет 1, затем в оставшемся красим все что можно в цвет 2 и т.
д. В остальном алгоритмы аналогичны, и данный алгоритм заканчивает свою работу построением допустимой раскраски по тем же причинам, что и предыдущий. П 289 Упражнения Комментарии Пентральный результат этой главы — теорема о пяти красках — изложен по книге [23). Алгоритмы раскрашивания изложены по книге [11), в которой можно найти их более детальное и подробное обсуждение.
Различные применения задачи о раскраске графов в программировании и смежные вопросы освещены в [5). Упражнения 12.1. Доказать, что Х(С(У, Е)) ( 1+ п1ах Ю(С'('и", Ь")). 12.2. Доказать, что если в планарном графе каждая грань есть С„, то п(р — 2) о= и — 2 12.3. Построить примеры графов, для которых алгоритмы последовательного раскрашивания строят не минимальную раскраску. Литература 1. А. Ахо, Дж. Хопкрофт, Дж. Ульман, Построение и анализ вычислительных алгоритмов, Мир, 1979. 2. К. Берж, Теория графов и ее применения, Изд.
иностр. лиг., 1962. 3. Д. А. Владимиров, Булевы алгебры, Наука, 1969. 4. М. Гзри, Д. Джонсон, Вычислительные машины и труднорешаемые задачи, Мир, 1982. 5. В. А. Евстигнеев, Применение теории графов в программировании, Наука, 1985. 6. В. А. Емеличев, О. И. Мельников, В. И. Сарванов, Р И. Тышкевич, Лекции по теории графов, Наука, 1990. 7. А, П.
Ершов, Введение в теоретическое программирование, Наука, 1977. 8, Д. Кнут, Искусство программирования для ЭВМ, т. 1, Мир, 1977. 9. Д. Кнут, Искусство программирования для ЭВМ, т. 2, Мир, 1977. 10. П. Кон, Универсальная алгебра, Мир, 1968. 11. Н. Кристофидес, Теория графов. алгоритмический подход, Мир, 1978.
12. В. Кук, Г Бейз, Компьютерная математика, Наука, 1990. 13. С. С. Лавров, Л, И. Гончарова, Автоматическая обработка данных, хранение информации в памяти ЭВМ, Наука, 1971. 14. В, Липский, Комбинаторика для программистов, Мир, 1988. 15. Э. Мендельсон, Введение в математическую логику, Наука, 1984.
16. В. И. Нечаев, Элементы криптографии. Основы теории защиты информации, Высшая школа, 1999. 17. Дискретная математика и математические вопросы кибернетики. Под ред. С. В, Яблонского и О. Б. Лупанова; Наука, 1974. 18. И. В. Романовский, Дискретный анализ, Невский диалект, 1999. 19. В.
Н. Сачков, Введение в комбинаторные методы дискретной математики, Наука, 1977. 20. В. Н. Сачков, Введение в комбннаторные методы дискретной математики, Наука, 1982. Литература 291 21. Р. Уилсон, Введение в теорию графов, Мир, 1977. 22. Э. Фрид, Элементарное введение в абстрактную алгебру, Мир, !979. 23. Ф. Харари, Теория графов, Мир, 1973, 24.
Ч. Чень, Р Ли, Математическая логика и автоматическое доказательство теорем, Наука, 1983. 25. С. В. Яблонский, Введение в дискретную математику, Наука, 1986. Алфавитный указатель А Автоморфизм, 55 Адекватность формальной теории, 107 Айбука Морзе, 165 Аксиома логическая, 105 иелогическая, 105 собсгвеииая, 105 формальной теории, 105 Аксиоматизируемость алгебраической системы, !07 коиечиая, 125 Алгебра, 52 Е-алгебра, 53 Лиидеибаума-Тарского, 86 булеза, 70 булевых функций, 86 высказываний, 103 конечно-порожденная, 53 миоГоосновная, 52 подмножеств, 25, 52 термов свободная, 53 универсальная, 52 Алгоритм Грея, 28 Дейкстры, 230 Краскала, 257 Лемпела — Зива, 179 Уоршалла, 48 Фаио, 167 Флойда, 229 Хаффмеиа, 170 бинарного поиска, 248 выделения компонент сильной связности, 227 вычисления СДНФ, 91 генерации перестаиовок, 142 Алгоритм (яродаюкеиие) генерации подмножеств, 147 жадиый, 75 интерпретации, 82 линейный, 75 метода резолюций, 132 иахождеиия максимального потока, 223 цезффективиый, 273 обхода бинарного дерева, 245 поиска в глубину, 203 в ширину, 203 поиска с возвратами, 273 последовательного раскрашивания, 287 последовательного раскрашивания (улучшеицый), 288 построения СДНФ, 90 построения кратчайшего остова, 256 построения зйлерова цикла, 264 приближенный, 287 слияния, 29 топологической сортировки, 46 уиификапии, 109 зффективиый, 273 Алфавит, 161 формальной теории, 105 Аргумент функции, 38 Арифметика двоичная, 63 Ассоциативность объединения, 25 пересечения, 25 га База матроида, 73 Базис, 82 векторного простраиства, 66 матроида, 73 АлФавитный указатель Биграф, 197 Бином Ньютона, 145 Блок графа, 212 разбиения, 148 Брат узла, 240 Буква, 161 Булеан, 25 Бэктрекинг, 273 В Валентность вершины, 194 Вектор, 64 Векторное пространство конечномерное, 67 Величина потока, 221 Вершина висячая, 195 графа, 191 изолированная, 195 концевая, 195 покрывающая, 269 Вес дуги, 228 Ветвь ордерева, 240 Включение множеств, 22 Вхождение определяющее, 17 переменной свободное, 119 связанное, 119 Выводимостгь 106 непосредственная, 106 Выполнимость формулы, 106, 121 Высказывание простое, 101 Высота дерева, 240 Вычет, 183 Г Гамма шифра, 182 Геодезическая, 196 Гиперграф, 192 Гипердуга, 192 Гипотеза, 106 Гомоморфнзм, 54 Граница верхняя, 69 нижняя, 69 Грань верхняя, 69 Грань (лродолжеиие) графа, 283 нижняя, 69 решетки верхняя, 68 нижняя, 68 Граф, 191 к-связный, 214 Герца, 227 ациклический, 196, 234 вполне несвязный, 197 гамильтонов, 266 двудольный, 197 древовидный, 234 нагруженный, 192 несвязный, 197 ориентированный, 192 планарный, 283 плоский, 283 полный, 197 полный двудольный, 197 полуэйлеров, 263 помеченный, 192 регулярный, 194 с петлями, 192 связный, 197, 210 субциклическнй, 235 тривиальный, 197 четный, 197 эйлеров, 263 Группа, 59 абелева, 60, 125 коммутативная, 60 периодическая, 125 полная, 125 порядка и, 125 симметрическая, 140 А Декодирование, ! 60 Делитель нуля, 62 левый, 62 правый, 62 Дерево, 234 АВЛ-дерево, 254 бинарное, 242 выровненное, 253 корневое, 238 ориентированное, 238 294 Алфавитный указатель Дерево (лродолжение) подровненное, 254 прошитое, 245 сбалансированное, 254 свободное, 234 сортировки, 247 упорядоченное, 241 Дешифрация, 181 Дешифрование, 181 Диаграмма Эйлера, 23 графа, 192 коммутативная, 55 Диаметр графа, 196 Дивергенция, 221 Дистрнбутнвность объединения относительно пересечения, 25 пересечения относительно объединения, 25 Длина дуги, 228 кодирования, 166 маршрута, 196 пути, 228 слова, 161 Добавление вершины, 200 ребра, 200 Доказательство теорем автоматическое, 127 Доля, 197 Дополнение, 68 графа„ 199 множества, 23 Достнжимость вершины, 206 Дуга, 192 Е Единица алдитивная, 64 мононда, 58 мультиплнкативная, 64 решетки, 68 3 Задача Хр-полная, 267 Рамсея, 209 Задача (иродохжение) Штейнера, 258 комбннаторная, 135 коммивояжера,267 о Кенигсбергских мостах, 190 о восьми ферзях, 277 о выборе переводчиков, 278 о наименьшем покрытии, 278 о пяти ферзях, 277 о развозке, 278 о свадьбах, 218 о трех домах и трех колодцах, 190 о четырех красках, 190 Заключение правила вывода, 106 Законы де Моргана, 25 Замена переменной, 58 линейная, 78 Замыкание, 94 множества, 53 отношения, 47 формулы, 122 Запись, 246 инфиксная, 34, 51 префиксная, 38 Зашифровка, 181 Звезда, 271 Значение истннностное, 101 функции,38 И Идемпотегпность объединения, 25 пересечения, 25 Измельчение разбиения, 148 Изоморфизм, 55 алгебр, 56 графов, 193 Инвариант графа, 193 Инверсия, 141 Инволютивность дополнения, 25 Интерпретация исчисления предикатов, 121 прелставления, 229 формальной теории, 106 фоРмУлы, 102 Инцидеитность, 191 Алфавитный указатель Матроид (продолжение) свободный, 77 трансверсалей, 77 Медиана множества, 167 Мстатеоремы, 106 Метол пузырька, 141 Метод резолюций, 128 Метрика, 174 Множество, 20 аксиом независимое, 107 бесконечное, 21 вершин независимое, 270 разделяющее, 215 вполне упорядоченное, 45 доминирующее, 277 зависимое, 71, 261 задание перечислением элементов, 21 порождающей процедурой, 21 характеристическим предикатом, 21 конечное, 21 линейно зависимое, 65 линейно независимое, 65 минимальное, 277 наименьшее, 277 независимые, 71 несущее, 52 основное, 52 пометок, 192 порождающее, 66 пустое, 20 разрезов независимое, 261 ребер независимое, 218, 270 разделяющее, 215 смежности, 191 универсальное, 20 циклов независимое, 261 частично упорядоченное, 45 Модель, 52 множества формул, 107, 122 формальной теории, 107 Моноид, 58 Мономорфизм, 55 Мост, 212 Мощность множества, 23 Мультиграф, 192 Н Надмножесгво, 22 Начало слова, 161 собственное, 161 Неподвижная точка, 158 Непротиворечивость семантическая, 107 формальная, 107 Неравенство Макмиллана, 163 треугольника, 231 Носитель, 52 интерпретации, 121 Нуль группы, 60 решетки, 68 Нуль-вектор, 64 О Область действия квантора, 120 значений функции, 39 интерпретации, 106 определения функции, 39 целостности, 62 Обр ., 40 Объединение графов, 199 множеств, 23 Окончание слова, 161 собственное, 161 Оператор возврата, 41 структурного перехода, 92 Операция н-арная, 51 н-местная, 51 ассоциативная, 54 главная (внешняя), 82 дистрибутивная слева, 54 справа, 54 идемпотентная, 54 коммутативная, 54 конкатенации, 57 Алфавитный указатель Орграф, 192 направленный, 199 Ордерево, 238 Основа, 52 Остов, 256 кратчайший, 256 Отец узла, 240 Отношение п-арное, 34 п-местное, 34 антирефлексивное, 36 антисимметричное, 36 бинарное, 34 дополнительное, 34 линейное, 36 на множестве, 34 обратное, 34 однозначное, 38 полное, 36 порядка„ 45 алфавитного, 50 антилексикографического, 142 лексикографического, 50, 142 линейного, 45 нестрогого, 45 полного, 45 строгого, 45 частичного, 45 рефлексивное,36 симметричное, 36 сравнимости чисел, 183 тождественное, 34 транзитивное, 36 универсальное, 34 функциональное, 38 эквивалентности, 42 П Память ассоциативная, 246 Парадокс Рассела, 22 Паросочетание, 218, 270 совершенное, 218 Переменная несущественная, 80 предметная, 119 пропозициональная, ! 01, 108 существенная, 80 фиктивная, 80 Пересечение множеств, 23 Переход к прообразам, 40 Петля, 192 Побочный эффект, 83 Поглощение, 25, 54 Подалгебра, 52 Подграф, 194 остовной, 194 остовный, 256 правильный, 194 собственный, 194 Поддерево, 239 Подмножество, 22 замкнутое, 52 независимое максимальное, 72 собственное, 22 Подстановка, 58, 139 обратная, 139 тождественная, 139 Подформула, 82 Поиск бинарный, 248 в глубину, 204 в ширину, 204 двоичный, 248 полнотекстовый, 178 Покрытие, 24 вершинное, 269 реберное, 269 Поле, 62 действительных чисел, 52 упорядоченное, 78 Поле рациональных чисел, 52 Полипом Жегалкина, 96 Полнота системы булевых Функций, 96 формальной теории, 107 Полный перебор, 267 Полугруппа, 57 свободная, 57 циклическая, 57 Полуразрешимость формальной теории, 108 Полустепень захода, 195 исхода, 195 Польская запись, 244 обратная, 245 зев Алфавитный указатель Порядок установленный, 91 Постфикс, 161 Посылка правила вывода, 106 Поток, 22! Потомок узла, 240 Правило введения импликации, 112 вывода производное, 112 формальной теории, 105 замены, 85 отделения, 108 подстановки, 85 резолюции, 130 сечения, 113 склеивания/расщепления, 92 транзитивности, 113 Предикат, 119 п-арный, 119 п-местный, 1!9 Предложение, 128 резольвируемое, 130 родительское, 130 Преобразование эквивалентное, 92 Префикс, 161 Приведение подобных, 93 Принадлежность элемента множеству 20 Принцип включения и исключения, 152 Произведение декартово, 33 подстановок, 139 прямое, 33 алгебр, 78 Прообраз, 40 Пропускная способность дуги, 221 разреза, 221 Пространство векторное, 64 Протаскивание отрицаний, 93, 129 Противоречие, 102 Псевдограф, 192 Путь, 196 кратчайший, 228 Р Равенство множеств, 23 упорядоченных пар, 33 Равиомощиость множеств, 23 Разбиение, 24 Разделение связанных переменных, 129 Размерность векторного пространства, 67 Размножение вершины, 200 Разность множеств, 23 симметрическая, 23 Разрез, 215, 260 простой, 260 фундаментальный, 261 Разрешимость класса формул, 90 формальной теории, 108 Разряд информационный, 176 контрольный, 176 Ранг коциклический, 261 множества, 73 циклический, 261 Раскраска графа, 281 Раскрытие скобок, 93 Расстояние, 174, 196 Хэмминга, 174 кодовое, 174 Расшифровка, 181 Расшифровываиие, 181 Расщепление, 92 переменных, 93 Ребро графа, 191 кратное, 192 покрывающее, 269 Резольвеита, 130 Решетка, 67 дистрибутивная, 67 ограниченная, 68 с дополнением, 68 Родитель узла, 240 С Связанность вершин, 197 Связка логическая, 108 Связность вершинная, 214 графа односторонняя, 226 сильная, 226 дяфааитный указатель Связность (продолжение) орграфа слабая, 226 реберная, 214 Семейство дизъюнктное, 24 множеств, 20 Сеть, 199 Сжатие, 177 адаптивное, 179 Сигнатура, 52 формальной теории, 105 Система образующих, 53 различных представителей, 218 разрезов фундаментальная, 261 циклов фундаментальная, 261 Скаляр, 64 Склеивание, 92 Сколемизация, 129 Следование логическое, 103, 107, 123 Словарь, 178 Слово, 161, 178 пустое, 161 Сложность временная, 135 по времени, 135 по памяти, 135 емкостная, 135 Смежность вершин, 191 ребер, 191 Смешанные вычисления, 83 Соединение графов, 199 Сообщение, 160 шифрованное, 181 Соотношения определяющие, 57 .Сортировка формулы, 93 Список смежности, 202 Сравнение по модулю, 183 Степень вершины, 194 множества, 33 отношения, 35 Сток, 199 Стратегия метода резолюций, 133 Строение алгебры, 54 формулы, 85 Структура алгебраическая, 52 Стягивание подграфа, 200 Сужение функции, 39 Схема аксиом 105 108 кодирования, 161 правил вывода, 108 префиксная, 162 разделимая, 162 Сын узла, 240 Т Таблица истинности, 79 кодов, 161 расстановки, 247 хзш, 247 Тавтология, 102, 107 Тайнопись, 181 Теорема формальной теории, 106 Теория групп, 124 равенства, 123 формальная, !05 формальной арифметики, 124 Терм, 53, 119 свободный для переменной в формуле, 120 Тип, 52 Тождество Коши, 146 Точка сочленения, 211 Трансверсаль, 218 частичная, 77 Транспозиция, 140 Треугольник Паскаля, 146 Турнир, 199 У Удаление вершины, 200 1 чр,20о Узел, 192 Укладка графа, 283 Улучшение перебора, 275 Умножение вектора на скаляр, 64 Универсум, 20 Унификатор, 109 наиболее общий, 109 общий, 109 зоо Алфавитный указатель Упаковка„177 Упорядоченная пара, ЗЗ Уровень узла, 240 Ф Фактор-граф, 227 Фактормножество, 43 Финитарность, 52 Форма дизъюнктивная, 93 нормальная, 90 соверпгенная нормальная дизъюнктивная, 89 коиъюнктивная, 90 Формализуемость алгебраической системы, 107 Формула Кали, 259 Стирлинга, 139 бескванторная, 123 в предварениой форме, 123 выполнимая, 102 замкнутая, 120 истинная, 122 ложная, 122 над базисом, 82 невыполнимая, 102 общезначимая, 102, 107, 122 открытая, 122 пропозициоиальная, 101 противоречивая, 107 пустая, 128 равносильная, 84 унифицируемая, 109 формальной теории, 105 Функтор, 119 Функция, 38 и аргументов, 39 п-местная, 39 Булеза„ 79 Эйлера, 184 алгебры логики, 79 биективиая, 39 весовая, 74 взаимнооднозначная, 39 двойственная, 86 индуцированная, 40 инъективная, 39 монотонная,47 Функция (продолжение) обратная, 39 отождествления, 44 производящая, 156 самодвойственная, 87 строго монотонная, 47 сюръективная, 39 тотальная, 39 характеристическая, 38 хзш, 247 частичная, 39 Х Хорда, 261 Ц Цена кодирования, 166 Цепочка множеств, 137 полная, 137 Цепь, 195 аугментальная, 223 вернгинно-непересекающаяся, 215 простая, 195 реберно-непересекающаяся, 215 эйлерова, 263 Цика, 140, 196 гамильтонов, 266 простой, 196 фундаментальный, 26$ эйлеров, 263 Цифровая подпись, 187 Ч Частный случай набора формул, 109 наборов формул совместный, 109 совместный, 109 формулы, 109 Число Белла, 150 Стирлинга второго рода, 149 Стирлинга первого рода, .150 Фибоначчи, 158 вершинного покрытия, 269 вершинное независимости, 270 вещественное, 20 взаимно простое, 184 Алфавитный указатель Число (продолжение) инверсий, 141 коцикломатическое, 261 натуральное, 20, 53 перестановок, 136 простое, 20 псевдослучайное, 181 размещений, 135 размещений без повторений, 136 реберного покрытия, 269 реберное независимости, 270 сочетаний, 137 сочетаний с повторениями, 138 хроматическое, 281 целое, 53 цикломатическое, 261 четное, 56 Ш Ширина ветвления, 259 Шифр, 181 надежный, 181 раскрытие, 181 с открытым ключом, 183 симметричный, 182 Шифрование, 181 Шифровка, 181 Э Зйлерова характеристика, 284 Эквивалентность логическая, 103, 123 Электронная подпись, 187 Элемент минимальный„45 множества, 20 обратный, 59 Элиминация импликации, 129 кваиторов всеобщности, 129 кванторов существования, 129 конъюнкции, 129 операций, 93 Эндоморфизм, 55 Зпиморфизм, 55 Зпиоморфизм, 55 Я Ядро графа, 278 отношения, 35 функции, 44 Язык формальной теории, 105 Ярус, 196 дерева, 240 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
