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