Бесконфликтное окрашивание
Бесконфликтная раскраска — это обобщение понятия раскраски графов на гиперграфы . [ 1 ]
Определение
[ редактировать ]Гиперграф E H имеет множество вершин V множество ребер . и Каждое ребро представляет собой подмножество вершин (в графе каждое ребро содержит не более двух вершин, но в гиперграфе оно может содержать более двух).
Раскраска — присвоение цвета каждой вершине V. это
Раскраска бесконфликтна , если хотя бы одна вершина каждого ребра имеет уникальный цвет. Если H — граф, то это условие становится стандартным условием допустимой раскраски графа: две вершины, прилегающие к каждому ребру, должны иметь разные цвета.
Приложения
[ редактировать ]Бесконфликтные раскраски возникают в контексте назначения полос частот e сотовой антенне , в аспектах потребления батареи сенсорных сетей и в протоколах RFID . [ 1 ]
Особые случаи
[ редактировать ]Распространенный частный случай — когда вершины являются точками на плоскости, а ребра — подмножествами точек, содержащихся в одном круге . В этой постановке раскраска точек называется бесконфликтной , если для каждого замкнутого круга D, содержащего хотя бы одну точку из множества, существует цвет, встречающийся ровно один раз. Любая бесконфликтная раскраска каждого набора из n точек на плоскости использует не менее c log n цветов для абсолютной константы c > 0. То же самое верно не только для дисков, но и для гомотетических копий любого выпуклого тела . [ 2 ]
Другой частный случай — когда вершины являются вершинами графа, а ребра — множествами соседей. В этом случае раскраска вершин называется бесконфликтной , если для каждой вершины v существует цвет, присвоенный ровно одной вершине среди v и ее соседей. В этом случае справедлив бесконфликтный вариант гипотезы Хадвигера : если граф G не содержит K k +1 в качестве минора , то он имеет бесконфликтную раскраску не более чем в k цветов. Для плоских графов три цвета иногда необходимы и всегда достаточны для бесконфликтной раскраски. NP-полно решить, имеет ли планарный граф бесконфликтную раскраску в один цвет и имеет ли планарный граф бесконфликтную раскраску в два цвета. [ 3 ]
Внешние ссылки
[ редактировать ]Ссылки
[ редактировать ]- ^ Jump up to: а б Смородинский, Шахар (2013), Лэмб, Имре; Бёрочки, Карой Дж.; Тот, Габор Фейес; Пах, Янош (ред.), «Бесконфликтная раскраска и ее приложения» , Геометрия — интуитивная, дискретная и выпуклая: Дань уважения Ласло Фейесу Тоту , Математические исследования Общества Бойяи, том. 24, Берлин, Гейдельберг: Спрингер, стр. 331–389, arXiv : 1005.3616 , дои : 10.1007/978-3-642-41498-5_12 , ISBN 978-3-642-41498-5 , S2CID 174683 , получено 20 января 2021 г.
- ^ Пах, Янош; Тот, Геза (2003), Аронов, Борис; Басу, Саугата; Пах, Янош; Шарир, Миха (ред.), «Бесконфликтные раскраски» , Дискретная и вычислительная геометрия: Фестиваль Гудмана-Поллака , Алгоритмы и комбинаторика, том. 25, Берлин, Гейдельберг: Springer, стр. 665–671, doi : 10.1007/978-3-642-55566-4_30 , ISBN. 978-3-642-55566-4 , получено 20 января 2021 г.
- ^ Авель, Закари; Альварес, Виктор; Демейн, Эрик Д.; Фекете, Шандор П.; Гур, Аман; Хестерберг, Адам; Кельденич, Филипп; Схеффер, Кристиан (01 января 2018 г.). «Бесконфликтная раскраска графов» . SIAM Journal по дискретной математике . 32 (4): 2675–2702. дои : 10.1137/17M1146579 . hdl : 1721.1/122951 . ISSN 0895-4801 .
 | Эта теории графов статья, посвященная , незавершена . Вы можете помочь Википедии, расширив ее . |