| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
Такой вопрос назрел. Дан граф. Требуется покрыть все ребра графа минимальным количеством клик.(ВАЖНО: каждое ребро РОВНО в одной клике). Например: Граф из ребер (1, 2), (1, 3), (2, 3), (3, 4), (2, 4) Ответ 3.
Пытался гуглить, ничего не нашел путного. Если кто может пруфануть класс сложности, буду благодарен.
Тут не про это написано случаем? Снизу в Related problems есть ссылка на покрытие ребер кликами. Вроде обе задачи NP.
https://en.wikipedia.org/wiki/Intersection_number_(graph_theory)
Тут покрытием ребер считается немного другое.(разрешается покрывать одно ребро многими кликами)
Мне же важно, что одно ребро входит ровно в одну клику.
Окей, I tried. Я не силен в теории сложности, поэтому не буду высказывать свои предположения по поводу того, какая из этих двух задач сложнее и насколько они схожи. Удачи с поиском!
Auto comment: topic has been translated by Extraordinary_ (original revision, translated revision, compare)
Auto comment: topic has been updated by Extraordinary_ (previous revision, new revision, compare).