Rivalry2

HTML Diff

0 added 0 removed

Original 2026-01-01

Modified 2026-02-26

1 <p>В этом уроке мы разберем, что такое раскраска графов и как это относится к цифрам на вершинах. Также покажем примеры раскраски графов разных типов, так как в каждом случае этот процесс немного отличается.</p>

2 <h2>Раскраска графов</h2>

3 <p>Когда мы присваиваем вершинам графа метки - это называется<strong>раскраской графов</strong>.</p>

4 <p><strong>Цвета</strong>- это целые положительные цифры. Графы нужно раскрашивать так, чтобы соседние вершины имели разные цвета. Еще стоит использовать как можно меньше цветов.</p>

5 <p>Вот несколько примеров раскраски графа:</p>

6 <p>Первый пример на схеме выше не совсем верный, потому что соседним вершинам присваивается один и тот же цвет. Вторая раскраска лучше, так как удовлетворяет правилам, но в ней используется больше цветов, чем нужно. Третья раскраска - правильная. Она удовлетворяет правилам и использует как можно меньше цветов.</p>

7 <p>В этих графах невозможно использовать меньше трех цветов, так как треугольники содержат три вершины, которые являются соседями.</p>

8 <p><strong>Хроматическое число графа</strong>G, которое обозначается chi(G) - это минимальное количество цветов, необходимое для правильной раскраски графа.</p>

9 <p>Чтобы обозначить, о каком графе идет речь, мы будем сокращенно обозначать chi(G) как chi. Рассмотрим раскраску графов на просто классе графов - путях.</p>

10 <h2>Раскраска путей</h2>

11 <p>Вот несколько оптимальных вариантов раскраски путей:</p>

12 <p>В общем случае chi(P_n) = 2 для каждого n ≥ 2.</p>

13 <p>Рассмотрим другие примеры:</p>

14 <p>Четные и нечетные циклы ведут себя по-разному. У нечетных всегда хроматическое число три, а у четных - хроматическое число два.</p>

15 <p>Теперь рассмотрим, как раскрашивают полные графы.</p>

16 <h2>Раскраска полных графов</h2>

17 <p>У нас есть следующие полные графы с уже помеченными вершинами:</p>

18 <p>Поскольку в полном графе каждая вершина смежна с любой другой вершиной, мы не можем повторить ни одного цвета. Таким образом, chi(Kn ) = n.</p>

19 <h2>Раскраска двудольных графов</h2>

20 <p>Рассмотрим следующие примеры:</p>

21 <p>На графиках видно, что соседние вершины раскрашены в один цвет. В случае с двудольными графами такое возможно, так как применяется правило<strong>партитного множества</strong>- независимое множество, между вершинами которого нет ребер. Поэтому мы можем окрасить все его вершины в один цвет.</p>

22 <p>Для двух партитных множеств нужно два цвета. И это относится к любому двудольному графу, а не только к полному.</p>

23 <p>Любой граф с хотя бы одним ребром является двудольным, когда он двухцветный. Поскольку деревья двудольные, мы теперь знаем, что все нетривиальные деревья имеют хроматическое число 2.</p>

24 <h2>Объединения и стыковки</h2>

25 <p>Мы пришли к такой формуле:</p>

26 <p>chi(GcupH) = max(chi(G),chi(H))</p>

27 <p>Это связано с тем, что между копиями G и H в объединении нет ребер. Поэтому мы можем раскрасить каждый граф отдельно, и не беспокоиться:</p>

28 <p>Мы также имеем chi(G vee H) = chi(G) + chi(H) - каждая вершина G смежна с каждой вершиной H. Поэтому ни один цвет, который используется на G, не может быть использован на H и наоборот.</p>

29 <p>Обратите внимание на второй граф на схеме выше. Чтобы получить правильную раскраску G vee H, мы можем раскрасить G и H отдельно, а затем заменить каждый цвет c из H на c + chi(G).</p>

30 <h2>Декартово произведение</h2>

31 <p>Декартово произведение немного сложнее. Результат chi(G H) = max(chi(G),chi(H)), что совпадает с результатом для объединения.</p>

32 <p>Рассмотрим пример: C5 C4. Ниже выделена конкретная вершина:</p>

33 <p>Выделенная вершина - это часть сразу двух графов (C5 и C4). Нам нужно убедиться, что ее раскраска работает в отношении обоих графов. Мы можем представить C5 и C4 как состоящий из пяти копий C4 со связями между копиями, которые определяются связями C5.</p>

34 <p>Нам нужно раскрасить каждую из пяти копий C4 по-своему и убедиться, что взаимодействия между копиями, которые определяются C5, соблюдены. Начнем с оптимальных раскрасок C4 и C5:</p>

35 <p>Хитрость в том, чтобы для каждой вершины взять ее цвет в C4, ее цвет в C5 и сложить их. При этом нужно уменьшить результат по модулю 3 и заменить все полученные нули тройками. В итоге раскраски для пяти копий выглядят следующим образом:</p>

36 <p>Такой способ гарантирует, что соседние вершины никогда не будут иметь одинаковый цвет. Этот же процесс работает и в общем случае:</p>

37 <ul><li>Для графов G и H пусть будет m = max(chi(G),chi(H))</li>

38 <li>Раскрасим вершину (u, v) из GH цветом (cG(u)+cH (v)) mod m</li>

39 <li>Уточним, что в выражении выше cG(u) и cH (v) - это цвета в G и H соответственно</li>

40 </ul><h2>Произвольный граф</h2>

41 <p>Вот еще один пример раскраски графа без очевидной структуры:</p>

42 <p>Может потребоваться некоторое усилие, чтобы придумать ответ к такой неочевидной структуре. Пройдем этот процес по шагам:</p>

43 <ul><li>На графе много треугольников, поэтому нам нужно использовать как минимум три цвета</li>

44 <li>На графе справа выделен 5-цикл, для него требуется 3 цвета</li>

45 <li>Вершина в середине цикла смежна со всем циклом, поэтому мы не можем повторно использовать ни один из цветов цикла</li>

46 <li>Таким образом, требуется 4 цвета</li>

47 </ul><h2>Выводы</h2>

48 <p>В этом уроке мы разобрали, что такое раскраска графов и как это относится к цифрам на вершинах. Мы показали, как раскрашивать графы разных типов. В каждом случае этот процесс немного отличается, при этом везде соблюдается правило соседних вершин.</p>