Шаблон:Eupce-6-3 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: «* Дан n-вершинный неориентированный граф G=(V, E) Рассмотрим следующий метод генерации неза…») |
StasFomin (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | * Дан n-вершинный неориентированный граф G=(V, E) | + | * Дан n-вершинный неориентированный граф ''G=(V, E)''. |
Рассмотрим следующий метод генерации независимого множества. | Рассмотрим следующий метод генерации независимого множества. | ||
| − | Для заданной перестановки вершин σ, определим подмножество S(σ) вершин следующим образом: для каждой вершины i, i ∈ S(σ) тогда и только тогда, когда | + | Для заданной перестановки вершин ''σ'', определим подмножество ''S(σ)'' вершин следующим образом: для каждой вершины ''i, i ∈ S(σ)'' тогда и только тогда, когда ни один сосед ''j'' вершины ''i'' не предшествует ''i'' в перестановке ''σ''. |
[[Категория:Теоретические задачи]] | [[Категория:Теоретические задачи]] | ||
Текущая версия на 22:10, 17 декабря 2024
- Дан n-вершинный неориентированный граф G=(V, E).
Рассмотрим следующий метод генерации независимого множества.
Для заданной перестановки вершин σ, определим подмножество S(σ) вершин следующим образом: для каждой вершины i, i ∈ S(σ) тогда и только тогда, когда ни один сосед j вершины i не предшествует i в перестановке σ.