Жадный алгоритм покрытия для почти всех исходных данных/Задачи/Жадное вершинное покрытие для почти всех исходных данных — различия между версиями

Версия 06:51, 4 мая 2023 (просмотреть исходный код) StasFomin (обсуждение | вклад) (Массовая правка: добавление Категория:Теоретические задачи) ← Предыдущая правка		Текущая версия на 09:03, 13 декабря 2024 (просмотреть исходный код) Ydanyok (обсуждение | вклад)
Строка 1:		Строка 1:
−	Рассмотрим жадный алгоритм для вершинного покрытия («брать вершину максимальной степени, ребра удалять»), на случайных графах, у которых	+	{{reserve-task|[[Участник:Ydanyok|Ydanyok]] 09:03, 13 декабря 2024 (UTC)}}Рассмотрим жадный алгоритм для вершинного покрытия («брать вершину максимальной степени, ребра удалять»), на случайных графах, у которых
	* <tt>n</tt>-вершин		* <tt>n</tt>-вершин
	* ребра между любой парой вершин возникают с вероятностью <tt>p</tt>.		* ребра между любой парой вершин возникают с вероятностью <tt>p</tt>.

---

Текущая версия на 09:03, 13 декабря 2024

Рассмотрим жадный алгоритм для вершинного покрытия («брать вершину максимальной степени, ребра удалять»), на случайных графах, у которых

• n-вершин
• ребра между любой парой вершин возникают с вероятностью p.

Какова точность алгоритма для почти всех исходных данных?

(упрощенный вариант — для фиксированного p=½).