Дискретная математика — больше на графиках

Раскраска графа — это процедура присвоения цветов каждой вершине графа G таким образом, что смежные вершины не получают одинаковый цвет. Цель состоит в том, чтобы минимизировать количество цветов при окрашивании графика. Наименьшее количество цветов, необходимое для окраски графа G, называется его хроматическим числом этого графа. Проблема раскраски графов — это проблема NP Complete.

Способ раскрасить график

Шаги, необходимые для раскраски графа G с n числом вершин, следующие:

Шаг 1 — Расположите вершины графа в некотором порядке.

Шаг 2 — Выберите первую вершину и раскрасьте ее первым цветом.

Шаг 3 — Выберите следующую вершину и раскрасьте ее цветом с наименьшим номером, который не был окрашен ни в одной из соседних вершин. Если все смежные вершины закрашены этим цветом, присвойте ему новый цвет. Повторяйте этот шаг, пока все вершины не будут окрашены.

пример

На рисунке выше первая вершина $a$ окрашена в красный цвет. Поскольку смежные вершины вершины a снова являются смежными, вершина $b$ и вершина $d$ окрашиваются в разные цвета, зеленый и синий соответственно. Тогда вершина $c$ окрашивается в красный цвет, так как ни одна из смежных вершин $c$ не окрашивается в красный цвет. Следовательно, мы могли бы раскрасить график на 3 цвета. Следовательно, хроматическое число графа равно 3.

Приложения для раскраски графиков

Некоторые приложения раскраски графа включают —

• Распределение регистра
• Раскраска карты
• Проверка двудольных графиков
• Присвоение подвижной радиочастоты
• Составление расписания и т. Д.

Обход графика

Обход графа — это проблема посещения всех вершин графа в некотором систематическом порядке. Есть в основном два пути для обхода графа.

• Ширина Первый Поиск
• Глубина Первый Поиск

Ширина Первый Поиск

Поиск в ширину (BFS) начинается с начальной вершины нулевого уровня $X$ графа $G$. Затем мы посещаем все вершины, которые являются соседями $X$. После посещения мы помечаем вершины как «посещенные» и помещаем их на уровень 1. Затем мы начинаем с вершин уровня 1 и применяем один и тот же метод к каждой вершине уровня 1 и так далее. Обход BFS заканчивается, когда каждая вершина графа посещена.

Алгоритм BFS

Концепция состоит в том, чтобы посетить все соседние вершины до посещения других соседних вершин соседних вершин.

• Инициализируйте статус всех узлов как «Готов».

• Поместите исходную вершину в очередь и измените ее статус на «Ожидание».

• Повторите следующие два шага, пока очередь не станет пустой —

  • Удалите первую вершину из очереди и отметьте ее как «Посещенные».

  • Добавьте в конец очереди всех соседей удаленной вершины, чей статус «Готов». Отметьте их статус «Ожидание».

Инициализируйте статус всех узлов как «Готов».

Поместите исходную вершину в очередь и измените ее статус на «Ожидание».

Повторите следующие два шага, пока очередь не станет пустой —

Удалите первую вершину из очереди и отметьте ее как «Посещенные».

Добавьте в конец очереди всех соседей удаленной вершины, чей статус «Готов». Отметьте их статус «Ожидание».

проблема

Давайте возьмем граф (исходная вершина — «a») и применим алгоритм BFS, чтобы выяснить порядок обхода.

Решение —

• Инициализируйте статус всех вершин как «Готов».

• Поставьте в очередь и измените ее статус на «Ожидание».

• Удалить из очереди, отметить его как «Посещенные».

• Добавьте соседей a в состоянии «Готово» b, d и e в конец очереди и отметьте их как «Ожидание».

• Удалите b из очереди, пометьте его как «Посещенный», поместите соседа «Готово» c в конец очереди и отметьте c как «Ожидание».

• Удалите d из очереди и отметьте его как «Посещенные». У него нет соседа в состоянии «Готов».

• Удалить e из очереди и отметить его как «Посещенные». У него нет соседа в состоянии «Готов».

• Удалить c из очереди и пометить его как «Посещенные». У него нет соседа в состоянии «Готов».

• Очередь пуста, так что остановитесь.

Инициализируйте статус всех вершин как «Готов».

Поставьте в очередь и измените ее статус на «Ожидание».

Удалить из очереди, отметить его как «Посещенные».

Добавьте соседей a в состоянии «Готово» b, d и e в конец очереди и отметьте их как «Ожидание».

Удалите b из очереди, пометьте его как «Посещенный», поместите соседа «Готово» c в конец очереди и отметьте c как «Ожидание».

Удалите d из очереди и отметьте его как «Посещенные». У него нет соседа в состоянии «Готов».

Удалить e из очереди и отметить его как «Посещенные». У него нет соседа в состоянии «Готов».

Удалить c из очереди и пометить его как «Посещенные». У него нет соседа в состоянии «Готов».

Очередь пуста, так что остановитесь.

Таким образом, порядок обхода —

$a \ rightarrow b \ rightarrow d \ rightarrow e \ rightarrow c$

Альтернативные порядки прохождения:

$a \ rightarrow b \ rightarrow e \ rightarrow d \ rightarrow c$

Или $a \ rightarrow d \ rightarrow b \ rightarrow e \ rightarrow c$

Или $a \ rightarrow e \ rightarrow b \ rightarrow d \ rightarrow c$

Или $a \ rightarrow b \ rightarrow e \ rightarrow d \ rightarrow c$

Или $a \ rightarrow d \ rightarrow e \ rightarrow b \ rightarrow c$

Применение BFS

• Нахождение кратчайшего пути
• Минимальное связующее дерево для невзвешенного графика
• GPS навигационная система
• Обнаружение циклов в неориентированном графе
• Поиск всех узлов в одном подключенном компоненте

Анализ сложности

Пусть $G (V, E)$ — граф с числом вершин $| V |$ и числом ребер $| E |$. Если алгоритм поиска в ширину посещает каждую вершину графа и проверяет каждое ребро, то его временная сложность будет:

$$ O (| V | + | E |). O (| E |) $$

Может варьироваться от $O (1)$ до $O (| V2 |)$

Глубина Первый Поиск

Алгоритм поиска в глубину (DFS) начинается с вершины $v$, затем переходит к смежной вершине (скажем, х), которая ранее не посещалась, помечается как «посещенная» и продолжается со смежной вершиной $x$, и скоро.

Если в любой вершине он обнаруживает, что все смежные вершины посещены, то он возвращается назад, пока не найдет первую вершину, имеющую соседнюю вершину, которая не была пройдена ранее. Затем он пересекает эту вершину, продолжается со смежными вершинами, пока не пройдет все посещенные вершины и не должен вернуться назад. Таким образом, он будет проходить через все вершины, достижимые из начальной вершины $v$.

Алгоритм DFS

Концепция состоит в том, чтобы посетить все соседние вершины соседней вершины до посещения других соседних вершин.

• Инициализировать статус всех узлов как «Готов»

• Поместите исходную вершину в стек и измените ее статус на «Ожидание»

• Повторите следующие два шага, пока стек не станет пустым —

  • Вставьте верхнюю вершину из стека и отметьте ее как «Посещенные».

  • Нажмите на вершину стека всех соседей удаленной вершины, чей статус «Готов». Отметьте их статус «Ожидание».

Инициализировать статус всех узлов как «Готов»

Поместите исходную вершину в стек и измените ее статус на «Ожидание»

Повторите следующие два шага, пока стек не станет пустым —

Вставьте верхнюю вершину из стека и отметьте ее как «Посещенные».

Нажмите на вершину стека всех соседей удаленной вершины, чей статус «Готов». Отметьте их статус «Ожидание».

проблема

Давайте возьмем граф (исходная вершина — «a») и применим алгоритм DFS, чтобы выяснить порядок обхода.

Решение

• Инициализируйте статус всех вершин как «Готов».

• Вставьте в стек и измените его статус на «Ожидание».

• Нажмите a и отметьте его как «Посещенные».

• Переведите соседей a в состояние «Готово» e, d и b в верхнюю часть стека и отметьте их как «Ожидание».

• Извлеките b из стека, отметьте его как «Посещенный», поместите соседа «Готово» c в стек.

• Вытащите c из стека и отметьте его как «Посещенный». У него нет «готового» соседа.

• Вытащите d из стека и отметьте его как «Посещенный». У него нет «готового» соседа.

• Извлеките e из стека и отметьте его как «Посещенный». У него нет «готового» соседа.

• Стек пуст. Так что остановись.

Инициализируйте статус всех вершин как «Готов».

Вставьте в стек и измените его статус на «Ожидание».

Нажмите a и отметьте его как «Посещенные».

Переведите соседей a в состояние «Готово» e, d и b в верхнюю часть стека и отметьте их как «Ожидание».

Извлеките b из стека, отметьте его как «Посещенный», поместите соседа «Готово» c в стек.

Вытащите c из стека и отметьте его как «Посещенный». У него нет «готового» соседа.

Вытащите d из стека и отметьте его как «Посещенный». У него нет «готового» соседа.

Извлеките e из стека и отметьте его как «Посещенный». У него нет «готового» соседа.

Стек пуст. Так что остановись.

Таким образом, порядок обхода —

$a \ rightarrow b \ rightarrow c \ rightarrow d \ rightarrow e$

Альтернативные порядки прохождения:

$a \ rightarrow e \ rightarrow b \ rightarrow c \ rightarrow d$

Или $a \ rightarrow b \ rightarrow e \ rightarrow c \ rightarrow d$

Или $a \ rightarrow d \ rightarrow e \ rightarrow b \ rightarrow c$

Или $a \ rightarrow d \ rightarrow c \ rightarrow e \ rightarrow b$

Или $a \ rightarrow d \ rightarrow c \ rightarrow b \ rightarrow e$

Анализ сложности

Пусть $G (V, E)$ — граф с числом вершин $| V |$ и числом ребер $| E |$. Если алгоритм DFS посещает каждую вершину графа и проверяет каждое ребро, то временная сложность составляет:

$$\ circleddash (| V | + | E |)$$

Приложения