![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/d/d9/Distinguishing_4-hypercube.svg/langru-640px-Distinguishing_4-hypercube.svg.png&w=640&q=50)
Характерная раскраска
Материал из Википедии — свободной encyclopedia
Характерная раскраска или характерная разметка графа — это назначение цветов или меток вершинам графа, которые разрушают нетривиальные симметрии графа. Не требуется, чтобы раскраска была правильной — смежным вершинам разрешено иметь одинаковый цвет. Для раскрашенного графа не должно существовать биективного отображения множества вершин с сохранением смежности и раскраски. Минимальное число цветов в характерной раскраске называется характерным числом графа.
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/d/d9/Distinguishing_4-hypercube.svg/220px-Distinguishing_4-hypercube.svg.png)
Характерные раскраски и характерные числа ввели Альбертсон и Коллинз[1], которые дали следующий пример для объяснения введения такой раскраски, основанный на головоломке, которую до этого сформулировал Франк Рубин: «Пусть у вас имеется связка ключей (на кольце) от различных дверей. Каждый ключ открывает только одну дверь, но все ключи выглядят одинаково (вы не можете их различить по внешнему виду). Сколько цветов вам нужно, чтобы раскрасить ключи и вы после этого могли полностью идентифицировать каждый ключ?»[2] Этот пример решается с помощью характерной раскраски для графа-цикла. С помощью такой раскраски каждый ключ может быть однозначно идентифицирован по его цвету и цвету окружающих его ключей[3].