Вы точно человек?
В этом уроке мы разберем, что такое раскраска графов и как это относится к цифрам на вершинах. Также покажем примеры раскраски графов разных типов, так как в каждом случае этот процесс немного отличается. Цвета — это целые положительные цифры. Графы нужно раскрашивать так, чтобы соседние вершины имели разные цвета.
На втором курсе университета учебный год нам объявили что пора уже задумываться о выборе научного руководителя, поскольку зима третий курс близко. Как раз в том учебном году к нам в филиал впервые приехал мой будущий научный руководитель и провел нам великолепный курс по теории графов. Меня так увлекла его манера преподавания, и тема была настолько интересна, что я не задумываясь после окончания курса а курсы от приезжих специалистов читались нам в сжатые сроки, примерно за месяц обратился с просьбой взять надо мной шефство. С тех самых пор научный руководитель у меня не менялся, но правда по науке графами много заниматься не пришлось. Тем не менее, теплые чувства к теории графов никуда не пропали, а потому часто возникает желание окунуться в графовые задачки и найти что-то познавательное хотя в этой области уже все давно украдено решено за нас. Пару недель назад в голову пришла мысль посмотреть на заезженную вдоль и поперек задачу о правильной вершинной раскраске планарного графа с алгоритмической точки зрения.
Правильная вершинная рёберная раскраска — это раскраска вершин рёбер графа, при которой любые смежные вершины рёбра окрашены в разные цвета. Правильную вершинную раскраску часто называют просто раскраской графа. Граф называется k k k -раскрашиваемым, если существует правильная вершинная раскраска графа k k k цветами. Граф является 2 2 2 -хроматическим тогда и только тогда, когда он не содержит простых циклов нечётной длины. Пусть f G , t f G, t f G , t — число различных правильных раскрасок графа G G G с нумерованными вершинами в t t t или меньше цветов, тогда для любого графа G G G функция f G , t f G, t f G , t есть многочлен от переменной t t t , называемый хроматичеcким многочленом графа G G G.
