Зада́ча о незави́симом мно́жестве относится к классу NP-полных задач в области теории графов. Эквивалентна задаче о клике. Множество вершин графа называется...
29 KB (2,024 words) - 11:38, 17 May 2025
коммивояжёра Задача о вершинном покрытии Задача о покрытии множества Задача о независимом множестве Задача о клике Проблема Штейнера Проблема раскраски графа Пятнашки...
11 KB (772 words) - 23:43, 4 August 2024
не более k {\displaystyle k} ? Задача о вершинном покрытии сходна с задачей о независимом множестве. Поскольку множество вершин C {\displaystyle C} является...
7 KB (603 words) - 15:32, 22 August 2022
клику максимального размера. NP-полнота задачи о клике следует из NP-полноты задачи о независимом множестве вершин. Легко показать, что необходимым и...
8 KB (770 words) - 16:24, 19 December 2023
были систематически изложены основные разделы теории множеств, включая теорию точечных множеств и теорию трансфинитных чисел (кардинальных и порядковых)...
31 KB (2,402 words) - 10:10, 16 July 2025
Алгоритм Брона — Кербоша (section Нахождение максимальных (по включению) независимых множеств вершин)
candidates, и помещаем в not Нетрудно видеть, что задача о клике и задача о независимом множестве по сути эквивалентны: каждая из них получается из другой...
6 KB (461 words) - 04:19, 6 April 2023
очевидные задачи — это задача о максимальном независимом множестве, задача о максимальной клике и минимальном независимом доминирующем множестве. Все они...
28 KB (1,874 words) - 18:10, 19 May 2025
Независимое множество в теории графов может быть как независимым множеством вершин, так и независимым множеством рёбер. Независимые множества рассматриваются...
4 KB (360 words) - 14:46, 7 November 2021
гиперкуба хорошо изучен и называется задачей о змее в коробке. Задача о наибольшем независимом множестве является также задачей изоморфизма порождённому подграфу...
8 KB (593 words) - 11:34, 17 May 2025
Число независимости графа G {\displaystyle G} — это размер наибольшего независимого множества вершин в нём. Поскольку задача о независимом множестве является...
2 KB (195 words) - 10:58, 27 May 2020
доминирующем множестве G. Задача о доминирующем множестве заключается в проверке, верно ли неравенство γ(G) ≤ K для заданного графа G и числа K. Задача является...
38 KB (2,754 words) - 07:21, 17 May 2025
сложных задач оптимизации на графах, таких как задача о независимом множестве, раскраска графов и задача о минимальном доминирующем множестве, можно эффективно...
11 KB (782 words) - 22:50, 16 May 2025
Задача о сделках (также задача о переговорах, задача торга) — игра двух лиц, в которой моделируется ситуация двусторонних переговоров. В ней участвуют...
4 KB (394 words) - 12:32, 13 October 2021
Задача Данцера — Грюнбаума — проблема комбинаторной геометрии, ставящая вопрос о том, какое максимальное число точек можно разместить в многомерном пространстве...
50 KB (4,388 words) - 12:09, 16 July 2025
полиномиальное время между задачей о независимом множестве и задачей упаковки множеств: Если дана задача упаковки множеств на наборе S {\displaystyle...
19 KB (1,358 words) - 12:26, 24 August 2024
Формальная система (section Независимость аксиом)
описанные формальные системы появились после того, как была поставлена задача Гильберта. Первые ФС появились после выхода книг Рассела и Уайтхеда «Формальные...
17 KB (947 words) - 09:58, 5 May 2025
Задача канадского путешественника (ЗКП) (англ. Canadian traveller problem, CTP) — это обобщение задачи о кратчайшем пути на графы, которые частично видимы...
19 KB (1,705 words) - 11:34, 17 May 2025
запись и обработку данных о космических объектах. Для этого игроку предоставлены 4 терминала со своими отдельными задачами, для обмена данными между которыми...
7 KB (368 words) - 00:37, 22 July 2025
Задача о кликовом покрытии — вычислительная задача, заключающаяся в определении возможности разбить вершины графа на k {\displaystyle k} клик. Является...
4 KB (228 words) - 11:37, 17 May 2025
(Johnson) 1974 года для задачи о выполнимости булевых формул, задачи о покрытии множества, задачи о независимом множестве и задача о хроматическом числе графа...
19 KB (1,410 words) - 07:37, 25 October 2024
{\displaystyle n>4} ? Эта задача решена лишь для n = 8 {\displaystyle n=8} (240) и n = 24 {\displaystyle n=24} (196 560). Задача плотнейшей упаковки шаров...
133 KB (9,448 words) - 10:17, 16 July 2025
забавную формулировку задачи о плавающих курсах валют, которая впервые привела к задаче о максимуме множества точек. Задача о плавающих курсах валют...
34 KB (2,540 words) - 12:47, 14 July 2025
хотя бы одну матрицу B {\displaystyle B} , имеющую малый ранг. Задача о независимом множестве Иногда также используется обозначение Θ ( G ) {\displaystyle...
19 KB (1,747 words) - 09:01, 18 July 2025
задачи, такие как задача о независимом множестве, задача о клике, раскраска, задача о кликовом покрытии, доминирующее множество и задача Штейнера о минимальном...
14 KB (1,160 words) - 02:02, 10 April 2025
сообщение о том, что Христофор Колумб прибыл в США в 2015 году как правдивое, ChatGPT использует информацию о путешествиях Колумба и информацию о современном...
66 KB (4,175 words) - 12:33, 12 July 2025
на вопрос задача чаще всего сводится к построению алгоритма, а отрицательный почти не встречается в олимпиадной практике. При решении задач на взвешивание...
22 KB (2,303 words) - 12:26, 6 July 2022
Граф Петерсена (section Гипотеза Петерсена о раскраске)
мостов. См. Связный граф. имеет число независимости 4 и является 3-дольным. См. Задача о независимом множестве. является кубическим графом, имеет число...
36 KB (2,466 words) - 22:52, 16 May 2025
них. Задача о наибольшей общей подпоследовательности: даны две последовательности, требуется найти самую длинную общую подпоследовательность. Задача поиска...
20 KB (1,292 words) - 19:19, 25 July 2024
Комбинаторика (redirect from Комбинаторные задачи)
математики, посвящённый решению задач, связанных с выбором и расположением элементов некоторого (чаще всего конечного) множества в соответствии с заданными...
62 KB (3,436 words) - 11:41, 18 May 2025
Парадокс Рассела (redirect from Расселовское множество)
системы Фреге, являвшейся ранней попыткой формализации наивной теории множеств Георга Кантора. Был открыт ранее, но не опубликован Эрнстом Цермело. На...
59 KB (4,061 words) - 10:11, 16 July 2025
решении задач: о нахождении площади под кривой; пройденного пути при неравномерном движении; массы неоднородного тела, и тому подобных; а также в задаче о восстановлении...
30 KB (2,374 words) - 15:50, 6 July 2025