courses:algorithms_building_and_analysis:materials:graph_coloring_notes
Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
courses:algorithms_building_and_analysis:materials:graph_coloring_notes [2020/06/27 14:13] aoblizanov [[В работе] Конспект лекции по раскраскам] |
courses:algorithms_building_and_analysis:materials:graph_coloring_notes [2022/12/10 09:08] (current) |
||
|---|---|---|---|
| Line 2: | Line 2: | ||
| Раскраска графа | Раскраска графа | ||
| - | * [[#раскраска-графа|Раскраска графа]] | + | * [[#раскраска графа|Раскраска графа]] |
| - | * [[#алгоритм-полного-перебора-совсем-наивный-перебор|Алгоритм полного перебора (совсем наивный перебор)]] | + | * [[#алгоритм полного перебора (совсем наивный перебор)|Алгоритм полного перебора (совсем наивный перебор)]] |
| - | * [[#перебор-с-учётом-выбора-только-из-2-цветов|Перебор с учётом выбора только из 2 цветов]] | + | * [[#перебор с учётом выбора только из 2 цветов|Перебор с учётом выбора только из 2 цветов]] |
| - | * [[#перебор-подмножеств-размера-math-xmlnshttpwwww3org1998mathmathmlsemanticsmrowmomomfracminmimn3mnmfracmrowannotation-encodingapplicationx-texleftarrow-fracn3annotationsemanticsmath3n|Перебор подмножеств размера $\Leftarrow \frac{n}{3}$]] | + | * [[#перебор подмножеств размера $\Leftarrow \frac{n}{3}$|Перебор подмножеств размера $\Leftarrow \frac{n}{3}$]] |
| - | * [[#вероятностный-алгоритм-two-list-coloring-сведение-к-задаче-выполнимости|Вероятностный алгоритм (Two-List Coloring). Сведение к задаче выполнимости.]] | + | * [[#Вероятностный алгоритм (Two-List Coloring). Сведение к задаче выполнимости|Вероятностный алгоритм (Two-List Coloring). Сведение к задаче выполнимости]] |
| - | * [[#алгоритм-перебора-по-инцидентным-вершинам|Алгоритм перебора по инцидентным вершинам]] | + | * [[#алгоритм перебора по инцидентным вершинам|Алгоритм перебора по инцидентным вершинам]] |
| * [[#применение|Применение]] | * [[#применение|Применение]] | ||
| Line 49: | Line 49: | ||
| Значит, сложность алгоритма - $O(1.9^n)$. | Значит, сложность алгоритма - $O(1.9^n)$. | ||
| - | ===== Вероятностный алгоритм (Two-List Coloring). Сведение к задаче выполнимости. ===== | + | ===== Вероятностный алгоритм (Two-List Coloring). Сведение к задаче выполнимости ===== |
| Посмотрим все цвета для вершин, в которые можно их покрасить. Можно для каждой вершины случайным образом выкинуть один цвет и красить из оставшихся. В таком случае каждая вершина может быть покрасить в один из двух цветов. | Посмотрим все цвета для вершин, в которые можно их покрасить. Можно для каждой вершины случайным образом выкинуть один цвет и красить из оставшихся. В таком случае каждая вершина может быть покрасить в один из двух цветов. | ||
courses/algorithms_building_and_analysis/materials/graph_coloring_notes.1593267180.txt.gz · Last modified: 2022/12/10 09:08 (external edit)
Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Share Alike 4.0 International
