Раскраска вершин гиперграфа

  • Просмотров 2795
  • Скачиваний 466
  • Размер файла 2482
    Кб

  Московский авиационный институт (государственный технический университет)                    Курсовая работа по дискретной математике   Раскраска вершин гиперграфа          Студент          Никитин И.К. Группа:           08-206 Проверил:                           Москва, 2007 Задание. № 14Т   Задание: раскраска вершин

гиперграфа. Найти минимальную раскраску гиперграфа.   Теоретический минимум.   Пусть V — конечное непустое множество, E — некоторое семейство непустых подмножеств множества V. Пара (V, E) называется гиперграфом с множеством вершин V и множеством ребер E. Неформально: гиперграф — это такое обобщение простого графа, когда ребрами могут быть не только двухэлементные, но и любые подмножества вершин. Если вершина v (из V)

принадлежит ребру e (из E), то говорят, что они инцидентны. Вершина гиперграфа, не инцидентная никакому ребру, называется изолированной. Гиперграфы содержащие петли в данной задаче не рассматриваются. Две вершины v` и v`` гиперграфа H назовем смежными, если существует ребро e = EH, которое содержит обе эти вершины. Два ребра e` и e`` гиперграфа H назовем смежными, если их объединение не пустое множество.   На рисунке выше изображен

гиперграф с множеством вершин V = {v1, v2, … v9} и множеством ребер E = {e1 = {v1 , v2, v3}, e2 = {v2, v4, v5, v6}, e3 = {v6, v7, v8}, e4 = {v3, v8}, e5 = {v9}, e6 = {v6} }. Обычно считают, что ребрами гиперграфа могут быть лишь не пустые подмножества вершин. В данной работе я полагаю, для простоты построения гиперграфа на ЭВМ, что ребром может быть любое множество вершин, в том числе и пустое. Гиперграф H называют r-хроматическим, если его вершины могут быть окрашены с

использованием r цветов (красок) так, что не найдется двух смежных вершин одного цвета. Наименьшее число r, такое , что гиперграф H является r-хроматическим, называется хроматическим числом гиперграфа. Задача нахождения хроматического числа гиперграфа называется задачей раскраски. Соответствующая этому числу раскраска вершин разбивает множество вершин графа на r независимых подмножеств, каждое из которых содержит вершины