Точная раскраска (Mkcugx jgvtjgvtg)
Точная раскраска — это раскраска вершин, в которой каждая пара цветов появляется ровно один раз на паре смежных вершин, разбиение вершин графа на непересекающиеся независимые множества. Таким образом, для каждой пары различных независимых множеств в разбиении существует только одно ребро, концы которого принадлежат обоим множествам[1][2].
Полные графы, расщепления и эйлеровы циклы
[править | править код]Любой полный граф Kn с n вершинами имеет точную раскраску n цветами, которая получается путём задания каждой вершине отдельного цвета. Также любой граф с n-цветной точной раскраской можно получить при помощи расщепления полного графа путём распадения на частицы каждой вершины на независимое множество и переключения каждого ребра, смежного вершине, ровно на одного члена соответствующего независимого множества[1][2]
Если k нечётно, путь или цикл с рёбрами имеет точную раскраску, которая получается с помощью формирования точной раскраски полного графа Kk и нахождения затем эйлерова цикла этого полного графа. Например, путь с тремя рёбрами имеет полную 3-раскраску[2].
Связанные виды раскрасок
[править | править код]Точные раскраски тесно связаны с гармоническими раскрасками (каждая пара цветов появляется максимум один раз) и полными раскрасками, поэтому точная раскраска одновременно гармоническая и полная. Граф G с n вершинами и m рёбрами имеет гармоничную k-раскраску тогда и только тогда, когда и граф, образованный из G путём добавления изолированных рёбер имеет точную раскраску. Граф G с теми же параметрами имеет полную k-раскраску тогда и только тогда, когда и существует подграф H графа G с точной k-раскраской, в которой каждое ребро графа имеет концы с разными цветами. Необходимость условия на рёбра показывается примером цикла с четырьмя вершинами, который имеет подграф с точной 3-раскраской (путь из трёх рёбер), но сам полной 3-раскраски не имеет[2].
Вычислительная сложность
[править | править код]Задача определения, имеет ли заданный граф точную раскраску, NP-полна даже для случая, когда граф является деревом[1][3]. Однако задача может быть решена за полиномиальное время для деревьев ограниченной степени[1][4].
Примечания
[править | править код]- ↑ 1 2 3 4 Edwards, 2005, с. 275–310.
- ↑ 1 2 3 4 Edwards, 2010, с. 94–114.
- ↑ Edwards, McDiarmid, 1995, с. 133–144.
- ↑ Edwards, 1996, с. 15–28.
Литература
[править | править код]- Keith Edwards. Detachments of complete graphs // Combinatorics, Probability and Computing. — 2005. — Т. 14, вып. 3. — С. 275–310. — doi:10.1017/S0963548304006558.
- Keith Edwards. Achromatic number of fragmentable graphs // Journal of Graph Theory. — 2010. — Т. 65, вып. 2. — С. 94–114. — doi:10.1002/jgt.20468.
- Keith Edwards, Colin McDiarmid. The complexity of harmonious colouring for trees // Discrete Applied Mathematics. — 1995. — Т. 57, вып. 2—3. — С. 133–144. — doi:10.1016/0166-218X(94)00100-R.
- Keith Edwards. The harmonious chromatic number of bounded degree trees // Combinatorics, Probability and Computing. — 1996. — Т. 5, вып. 1. — С. 15–28. — doi:10.1017/S0963548300001802.
На эту статью не ссылаются другие статьи Википедии. |
Для улучшения этой статьи желательно:
|