Колорирование в 3 цвета: Колорирование более 3 цветов — Студия красоты «NailsProfi»

Колорирование волос: виды, техники, примеры, идеи

• Главная
• /
• Журнал
• /
• Колорирование волос: виды, техники, примеры, идеи

Со временем естественный цвет волос может надоедать. Возникает желание изменить свой образ. Иногда бывает сложно определить свои предпочтения при выборе краски. Объединить несколько цветов в одной прическе позволяет современная технология окрашивания — колорирование.

Что такое колорирование?

Это способ окрашивания волос, при котором мастер чередует несколько оттенков. Они могут гармонично сочетаться между собой и с базовым цветом волос или же контрастировать друг с другом.

Колорирование практически не имеет ограничений в выборе цветовой гаммы. Тем не менее при подборе оттенков мастер должен учитывать цветотип внешности клиента, его стиль, предпочтения в одежде и другие нюансы.

В зависимости от длины и типа волос применяемые техники колорирования могут различаться.

Преимущества и недостатки колорирования

Преимущества колорирования:

• полная свобода для творчества и самовыражения с отсутствием ограничений в выборе цветов;
• разные варианты окрашивания, среди которых можно подобрать подходящий для каждого конкретного типа волос и внешности;
• возможность получить эффект натуральности или придать образу дополнительной яркости;
• возможность подчеркнуть текстуру локонов;
• придание визуального объема волосам.

К недостаткам можно отнести:

• сложность получения качественного результата при самостоятельном окрашивании в домашних условиях;
• сложность коррекции внешнего вида прически при отрастании волос;
• необходимость частого освежения цвета при колорировании с использованием ярких оттенков.

Кому подходит колорирование?

Подходит к любому образу. Оно может использоваться для волос любой длины и любого базового цвета. Выбор оттенков основывается на индивидуальных предпочтениях клиента с учетом цветотипа, особенностей внешности, формы лица и оттенка кожи.

При работе с темными локонами процедура колорирования начинается с обесцвечивания прядей. Поэтому после посещения мастера волосам требуется тщательный уход. Но так как осветлению подвергается только часть локонов, на их восстановление не требуется много времени.

Светлым волосам колорирование помогает придать объем. Образ приобретает новизну и изюминку. Светлые пряди не подвергаются обесцвечиванию. Поэтому процедура колорирования не занимает много времени и не наносит вреда волосам. Тем не менее уход за локонами требуется и в этом случае. Он направлен на поддержание интенсивности цвета.

Русые волосы позволяют добавить в прическу одновременно более темные и более светлые оттенки. Могут использоваться как естественные, так и яркие тона. В каждом случае колорирование, выполненное на русых волосах, выглядит очень эффектно.

Виды колорирования

Выбор техники колорирования зависит от длины и исходного цвета волос. Существует множество способов такого окрашивания. Но условно колорирование можно разделить на два основных типа:

1. Вертикальное. Волосы окрашиваются по всей длине. В работе может использоваться до 15 оттенков.
2. Горизонтальное. Каждая часть пряди окрашивается в определенный цвет. Как правило, используется 2–4 оттенка. Для работы с прикорневой зоной в большинстве случаев выбирают более темные оттенки, со средней — средние, а с кончиками — самые светлые.

К смешанным видам колорирования можно отнести шатуш, бронирование и др.

Внимание! Главное отличие колорирования от мелирования заключается в окрашивании прядей. При мелировании они только осветляются.

Техники колорирования

К основным техникам колорирования относятся:

1. Американское. Наиболее подходит обладательницам темных локонов. Подразумевает использование 5 оттенков, подходящих к базовому тону.
2. Многоцветное. Такое колорирование подходит и для темных, и для светлых локонов. Для окрашивания применяются краски любых натуральных оттенков.
3. «Соль и перец». Подходит для светлых волос. Позволяет качественно скрыть седину. Для окрашивания корней применяется краска более светлого оттенка, чем для кончиков.
4. Зональное. Разные участки окрашиваются в разные цвета. Эта техника позволяет создать рисунки на волосах. Для этого применяются краски ярких оттенков. Это позволяет сделать рисунок более заметным.
5. Колорирование челки. Остальные участки волос не задействуются в работе.
6. Неоновое. Подходит для темных локонов. Пряди обесцвечиваются и окрашиваются в яркие тона. Недостаток заключается в быстром вымывании цвета (через 2–3 недели).

Технология колорирования

Процедура колорирования состоит из нескольких этапов:

1. Выбор оттенков краски с учетом базового цвета локонов и типа внешности.
2. Обесцвечивание темных, рыжих или ранее окрашенных прядей. Процедура может проводиться с применением фольги или без нее.
3. Фиксация прядей, не подлежащих окрашиванию, на голове с помощью зажимов.
4. Нанесение красящих составов на пряди в выбранном порядке.
5. Удаление краски с поверхности волос с помощью воды по истечении определенного времени.
6. Обработка локонов специальным средством для фиксации цвета.

Колорирование для волос разной длины

В случае с короткой стрижкой колорирование помогает оживить образ, придать ему стиля и привлекательности. Но окрашивание локонов небольшой длины в несколько оттенков требует особого мастерства и профессионализма. Важно учесть особенности волос и внешности, чтобы избежать возможных ошибок.

Внимание! Существует множество способов укладки коротких волос. Колорирование должно сочетаться с каждой из них.

Для поддержания внешнего вида прически требуется посещение мастера не реже 1–2 раз в месяц. Короткие волосы требуют регулярной стрижки и окрашивания.

Локоны средней длины — оптимальный вариант для колорирования. На таких прядях можно реализовать любую творческую фантазию и применить любую технику сложного окрашивания. В зависимости от особенностей процедуры периодичность посещения мастера может составлять 1 раз в 2–3 месяца.

Для длинных волос колорирование наилучшим образом сочетается с такими стрижками, как удлиненное каре, каскад или другие дизайнерские прически.

Уход за волосами после колорирования

Для восстановления локонов и ухода за ними после колорирования рекомендуется выбирать шампуни и кондиционеры для окрашенных или ослабленных волос. Первые помогут сохранить результат процедуры на более длительный срок, а вторые — вернуть прядям здоровый внешний вид.

В качестве дополнительного ухода рекомендуется использовать питательную маску с периодичностью 1 или 2 раза в неделю.

Внимание! В период восстановления прядей не рекомендуется использовать нагревающие приборы, такие как утюжки и фены. Следует также избегать длительного пребывания на солнце.

Для мытья волос рекомендуется использовать теплую, но не горячую воду, чтобы избежать пересушивания прядей.

Колорирование 3 и более цветов в Зеленограде в салоне красоты

Цена на сайте не является публичной офертой. Уточняйте пожалуйста стоимость услуг у администратора по телефону.

Колорирование волос – одна из весьма распространенных процедур по влиянию на естественный цвет волос. Какая из женщин не любит изменений в своей внешности? Кто-то хочет придать своему имиджу более ярких цветов, кто-то, наоборот, успокоить.

Кто-то идет на радикальные меры по изменению внешности – будь это неожиданное окрашивание или изменения стрижки, а кто-то не способен на такие меры и хочет лишь немного изменить свой внешний вид. Вторая группа людей чаще всего и выбирает колорирование.

В чем заключается процедура?

Колорирование на темные волосы – это методика окрашивания волос в несколько оттенков, которые близки к натуральному цвету. Но существует и такая методика, как креативное или радикальное колорирование, которое может использовать неожиданные оттенки. Выбор напрямую зависит как от желания женщины, так и от умелых рук специалиста.

В чем заключается техника колорирования?

Существует огромное разнообразие техник колорирование на русые волосы, но методики при этом только две основные – горизонтальная и вертикальная. Вертикальное окрашивание может похвастать большим объемом работы, ведь нужно нанести до 19 различных оттенков на естественный цвет волос, что делает процедуру довольно сложной. При горизонтальном окрашивании используют только четыре оттенка, но при этом технология не значительно легче. Для этого нужно делить все волосы на сегменты. Далее окрашиваются отдельно кончики в самые светлые тона, корни в самые темные, а средний уровень окрашивается в промежуточное значение.

Цена на колорирование волос напрямую зависит от технологии выполнения. Рассмотрим основные разновидности:

1. Американская технология. Данный метод используется только для девушек с темными волосами, для блондинок она не подходит. При этом используется 5 различных оттенков естественного цвета.
2. «Соль и перец». Эта методика хорошо подходит для колорирования на светлые волосы. При данной методике корни волос высвечиваются, а вот кончики, наоборот, осветляются. Также следует отметить, что такая методика хорошо подходит для скрывания седины.
3. Многоцветовое колорирование. Данная методика заключается в произвольном и хаотичном нанесении оттенков естественного цвета. Для такого колорирования особо не важно, светлые волосы красятся или темные.
4. Колорирование волос с челкой. Эта методика понятна исходя даже из название. Основной пласт волос при этом не затрагивается, а окрашивается только челка.
5. Зональная методика. При таком колорировании акцент делается только на определенном локальном участке волос, который нуждается в окрашивании. Методика весьма разнообразная и включает в себя множество вариантов.

Неоновая методика. Наиболее радикальное и смелое окрашивание волос в этой группе. Лучше всего использовать ее для темных волос, чтобы придать более гармоничный вид. Неоновое колорирование – это довольно смелое решение, которое может даже создать вызывающий внешний вид.

NP-Complete

Предпосылки: NP-полнота, раскраска графов

Задача K-раскраски графа : граф так, что никакие две соседние вершины не имеют одного и того же цвета, и , не более чем K цветов используются для полного окрашивания графа.

Постановка задачи : Дан граф G(V, E) и целое число K = 3, задача состоит в том, чтобы определить, можно ли раскрасить граф, используя не более чем 3 цветов так, чтобы никакие две соседние вершины не были окрашены в один и тот же цвет.

Объяснение :
Экземпляр задачи — это ввод, указанный для задачи. Примером задачи 3-раскраски является неориентированный граф G (V, E) , и задача состоит в том, чтобы проверить, существует ли возможное назначение цветов для каждой из вершин V , использующий только 3 разных цвета, причем каждый сосед окрашен по-разному. Поскольку NP-полная задача — это задача, которая находится в NP и NP-hard , доказательство утверждения о том, что задача является NP-полной, состоит из двух частей:

1. Сама задача находится в НП класс .
2. Все другие задачи в классе NP могут быть сведены к ней за полиномиальное время.0046

Если выполняется только 2-е условие , то проблема называется NP-Hard .

Но невозможно каждую NP-задачу свести к другой NP-задаче, чтобы все время показывать ее NP-полноту. Следовательно, чтобы показать, что проблема является NP-полной, тогда доказательство того, что проблема находится в NP и что любая NP-полная проблема сводится к этому, то есть, если B является NP-полной и B≤P ^C , то для C в NP, то C является NP-полным. Таким образом, можно сделать вывод, что Задача K-раскраски графа является NP-полной с использованием следующих двух утверждений:

Задача 3-раскраски находится в NP:
Если какая-либо проблема находится в NP, то, учитывая сертификат, который является решением проблемы и пример задачи (График G(V, E) и назначение цветов {c ₁ , c ₂ , c ₃ } , где каждой вершине присвоен цвет из этого три цвета {с ₁ , с ₂ , с ₃ } ), то можно проверить (проверить правильность данного решения или нет), что сертификат за полиномиальное время. Это можно сделать следующим образом:

Для каждого ребра {u, v} в графе G проверить, что цвет c(u) != c(v)

Следовательно, правильность присвоения можно проверить в полиномиальное время графа относительно его ребер O (V + E).

Задача с тремя раскрасками является NP-сложной:
Чтобы доказать, что задача с тремя раскрасками является NP-сложной, выполните сведение известной NP-сложной задачи к этой задаче. Проведите редукцию, с помощью которой можно свести задачу 3-SAT к задаче о 3-х раскрасках. Предположим, что задача 3-SAT имеет формулу 3-SAT из m предложений от n переменных, обозначенных х ₁ , х ₂ , …, х _п . Тогда граф можно построить по формуле следующим образом:

1. Для каждой переменной x _i Построить вершину v _i В графе и вершину v _i’ 900 обозначающую отрицание переменной x _i .
2. Для каждого предложения c в m добавьте 5 вершин, соответствующих значениям c1, c1, …, c5.
3. Дополнительно добавлены три вершины разных цветов для обозначения значений True, False и Base (T, F, B) соответственно.
4. Ребра добавляются к этим трем дополнительным вершинам T, F, B , образуя треугольник.
5. Ребра добавляются между вершинами v _i и v _i’ и основанием (B) для формирования треугольника.

Для графа G справедливы следующие ограничения: ЛОЖЬ.

Таким образом, для каждого пункта c = (u V v V w) в формуле по входным узлам u, v, w можно построить небольшой граф гаджета ИЛИ и соединить выходной узел гаджета с обоими Ложь и Базовые специальные узлы.

Рассмотрим формулу f = (u’ V v V w’) И (u V v V w’)

Теперь редукция может быть доказана следующими двумя утверждениями:
Предположим, что формула 3-SAT имеет удовлетворительное назначение, тогда в каждом предложении хотя бы один из литералов x _i должен быть истинным, поэтому соответствующее v _i может быть присвоен ИСТИННЫЙ цвет, а v _i’ — ЛОЖЬ. Теперь, расширяя это, для каждого предложения соответствующий граф ИЛИ-гаджета может быть 3-цветным. Следовательно, граф может быть трехцветным.

Будем считать, что граф G раскрашивается в 3 цвета, так что если вершине vi поставить в соответствие истинный цвет, то соответственно переменная x _i присвоено значение true. Это сформирует задание юридической истины. Кроме того, для любого предложения C _j = (x V y V z) не может быть, чтобы все три литерала x, y, z были False. Потому что в этом случае вывод графа OR-gadget для C _j должен быть окрашен в False. Это противоречие, потому что выход связан с Base и False. Следовательно, существует удовлетворительное присвоение пункту 3-SAT.

Заключение : Следовательно, 3-раскраска — это NP-полная задача .

5.8 Раскраска графика

Как мы кратко обсуждали в разделе 1.1, наиболее
Знаменитая проблема раскраски графа — это, безусловно, проблема раскраски карты.
предложенный в девятнадцатом веке и окончательно решенный в 1976 году.

Определение 5.8.1 правильная раскраска графа
— такое присвоение цветов вершинам графа, что никакие два
соседние вершины имеют одинаковый цвет.
$\квадрат$

Обычно мы опускаем слово «правильная», если только другие типы окраски не используются.
также в стадии обсуждения. Конечно, «цвета» не обязательно должны быть
актуальные цвета; они могут быть любыми различными метками — целыми числами, для
пример. Если граф несвязен, каждая компонента связности может быть
окрашены самостоятельно; если не указано иное, мы предполагаем, что графы
подключены. Мы также предполагаем, что графы в этом разделе простые.

Пример 5.8.2. Если вершины графа представляют академические классы, а
две вершины смежны, если в соответствующих классах есть люди
общий, то раскраска вершин может быть использована для планирования занятий
встречи. Здесь цвета будут временем расписания, например, 8MWF, 9МВФ,
11ТТ и др.
$\квадрат$

Пример 5.8.3. Если вершины графа представляют радиостанции, а
две вершины являются смежными, если станции расположены достаточно близко к
мешают друг другу, можно использовать раскраску, чтобы назначить
частоты, не создающие помех для станций.
$\квадрат$

Пример 5.8.4. Если вершины графа представляют сигналы светофора в
пересечение, и две вершины смежны, если соответствующие
сигналы не могут быть зелеными одновременно, можно использовать окраску, чтобы
обозначают наборы сигналов, которые могут быть зелеными одновременно.
$\квадрат$

Определение 5.8.5. Множество $S$ вершин в графе является независимым, если никакие два
вершины $S$ смежны.
$\квадрат$

Если граф правильно раскрашен, вершины, которым присвоены
определенный цвет образует независимый набор. Имея граф $G$, легко
чтобы найти правильную раскраску: дайте каждой вершине различную
цвет. Ясно, что интересное количество — это минимальное количество
цвета, необходимые для раскрашивания. Также легко найти независимых
наборы: просто выберите вершины, которые взаимно несмежны. Один
набор вершин, например, является независимым и обычно находит большее
независимые множества легко. Интересное количество — максимальный размер
независимого множества.

Определение 5.8.6 Хроматическое число
граф $G$ — минимальное количество цветов, необходимое для правильной раскраски;
она обозначается $\chi(G)$.
номер независимости от $G$
максимальный размер независимого множества; он обозначается $\alpha(G)$.
$\квадрат$

Естественный первый вопрос об этих
графические параметры
является: насколько маленькими или большими они могут быть в графе $G$ с $n$
вершины. Легко видеть, что
$$\выравнивание{
1&\le \chi(G)\le n\cr
1&\le \alpha(G)\le n\cr
}$$
и что все пределы достижимы: граф без ребер имеет
хроматическое число 1 и число независимости $n$, а полный граф
имеет хроматическое число $n$ и число независимости 1. Эти неравенства
поэтому не очень интересны. Мы увидим некоторые, которые более
интересный.

Другой естественный вопрос: какова связь между хроматическим
номер графа $G$ и хроматический номер подграфа $G$?
Это тоже просто, но иногда весьма полезно.

Доказательство.
Любая раскраска $G$ обеспечивает правильную раскраску $H$ просто за счет
присвоение тем же цветам вершинам $H$, что и в
$G$. Это означает, что $H$ можно раскрасить в цвета $\chi(G)$, например
еще меньше, чего мы и хотим.
$\qed$

Часто этот факт интересен «наоборот». Например, если $G$ имеет
подграф $H$, являющийся полным графом $K_m$, то $\chi(H)=m$ и, следовательно,
$\chi(G)\ge m$. Подграф $G$, являющийся полным графом, называется
нажмите , и есть соответствующий графический
параметр.

Определение 5.8.8. кликовое число графа $G$ равно
наибольшее $m$ такое, что $K_m$ является подграфом $G$.
$\квадрат$

Заманчиво предположить, что только способ графа $G$
может потребоваться $m$ цветов при наличии такого подграфа. Это неверно;
графы могут иметь высокое хроматическое число при низком кликовом числе;
см. рисунок 5.8.1. Легко видеть, что это
граф имеет $\chi\ge 3$, потому что в графе много 3-клик.
график. В общем случае может быть трудно показать, что граф не может быть
раскрашены заданным числом цветов, но в этом случае легко
видим, что на самом деле граф нельзя раскрасить тремя цветами,
потому что так много «вынуждено». Предположим, что граф можно раскрасить с помощью 3
цвета. Начиная слева
если вершина $v_1$
получает цвет 1, тогда $v_2$ и $v_3$ должны быть окрашены в цвета 2 и 3, а вершина
$v_4$ должен быть цвета 1. Продолжая, $v_{10}$ должен быть цвета 1, но это
не допускается, поэтому $\chi>3$. С другой стороны, поскольку $v_{10}$ может быть
цвет 4, мы видим $\chi=4$.

Пол Эрдёш
показал в 1959 г., что существуют графы с произвольно
большое хроматическое число и сколь угодно большой обхват (обхват — размер наименьшего цикла в
график). Это гораздо сильнее, чем существование графов с высокой
хроматическое число и низкое кликовое число.

Рисунок 5.8.1. Граф с кликой номер 3 и хроматическим номером 4.

Двудольные графы хотя бы с одним ребром имеют хроматическое число 2, так как
две части являются независимыми наборами и могут быть окрашены с помощью
один цвет. И наоборот, если граф можно раскрасить в 2 цвета, он
двудольный, так как все ребра соединяют вершины разных цветов. Этот
означает, что двудольные графы легко идентифицировать: раскрасьте любую вершину
цвет 1; раскрасьте его соседей цветом 2; продолжая таким образом будет или
не будет успешно раскрашивать весь график двумя цветами. Если оно
терпит неудачу, граф не может быть двухцветным, так как все варианты вершин
цвета принудительные.
9\чи |V_i| \ле \чи\альфа,
$$
по желанию.
$\qed$

Мы также можем улучшить верхнюю границу для $\chi(G)$. В любом графе $G$
$\Delta(G)$ — максимальное
степень любой вершины.

Теорема 5.8.10.
В любом графе $G$ $\ds \chi\le\Delta+1$.

Доказательство.
Мы показываем
что мы всегда можем раскрасить $G$ в цвета $\Delta+1$ с помощью простого
жадный алгоритм :
Выберите вершину $v_n$ и перечислите
вершин $G$ как $v_1,v_2,\ldots,v_n$, так что если $i

Это, безусловно, верно для $v_1$.
За 1 9 долларов0005

После того, как $v_1,\ldots,v_{n-1}$ были раскрашены, все соседи $v_n$ покрашены.
были окрашены в цвета $1,2,\ldots,\Delta$, поэтому раскрасьте $\Delta+1$
может использоваться для окрашивания $v_n$.
$\qed$

Обратите внимание, что если $\d(v_n)

Следствие 5.8.11. Если $G$ нерегулярно, то $\chi\le\Delta$.
$\qed$

Существуют графы, для которых $\chi=\Delta+1$: любой цикл нечетной длины
имеет $\Delta=2$ и $\chi=3$, а $K_n$ имеет $\Delta=n-1$ и
$\чи=n$. Конечно, это обычные графики.
Оказывается, это единственные примеры, т. е. если
$G$ не является нечетным циклом или полным графом, то
$\chi(G)\le\Delta(G)$.

Теорема 5.8.12.
(теорема Брукса)
Если $G$ — граф, отличный от $K_n$ или $C_{2n+1}$,
$\chi\le\Delta$.
$\qed$

Жадный алгоритм не всегда раскрашивает граф
наименьшее возможное количество цветов. Рисунок 5.8.2
показывает график с хроматическим номером 3, но жадный алгоритм использует
4 цвета, если вершины упорядочены, как показано.

Рисунок 5.8.2. Жадная раскраска слева и наилучшая раскраска справа.

В общем случае вычислить $\chi(G)$ сложно, т. е. требуется
большой объем вычислений, но есть простой алгоритм построения графа
окраска не быстрая. Предположим, что $v$ и $w$ несмежны.
вершины в $G$. Обозначим через $G+\{v,w\}=G+e$ граф, образованный добавлением
ребро $e=\{v,w\}$ в $G$. Обозначим через $G/e$ граф, в котором $v$ и
$w$ являются «идентифицированными», то есть $v$ и $w$ заменяются одним
вершина $x$, смежная со всеми соседями $v$ и $w$. (Но учтите, что мы
не вводите кратные ребра: если $u$ смежно и с $v$, и с
$w$ в $G$, будет одно ребро от $x$ до $u$ в $G/e$.)

Рассмотрим правильную раскраску $G$, в которой $v$ и $w$ — разные цвета;
то это также правильная раскраска $G+e$. Кроме того, любой
правильная раскраска $G+e$ — это правильная раскраска $G$, в которой
$v$ и $w$ имеют разные цвета.
Таким образом, раскраска $G+e$ с наименьшим возможным количеством цветов есть
наилучшая раскраска $G$, в которой $v$ и $w$ имеют разные цвета,
то есть $\chi(G+e)$ — это наименьшее количество цветов, необходимое для раскрашивания
$G$ так, чтобы $v$ и $w$ были разного цвета.

Если $G$ раскрашена правильно, а $v$ и $w$ одного цвета, то
это дает правильную раскраску $G/e$, раскрашивая $x$ в $G/e$ с помощью
тот же цвет, что и для $v$ и $w$ в $G$. Кроме того, если $G/e$ правильно
окрашены, это дает правильную раскраску $G$, в которой $v$ и $w$ имеют
того же цвета, а именно цвета $x$ в $G/e$. Таким образом, $\chi(G/e)$
это наименьшее количество цветов, необходимое для правильного окрашивания $G$ так, чтобы
$v$ и $w$ одного цвета.

Итогом этих наблюдений является то, что
$\ds\chi(G)=\min(\chi(G+e),\chi(G/e))$. Этот алгоритм можно применить
рекурсивно, то есть если $G_1=G+e$ и $G_2=G/e$, то
$\ds\chi(G_1)=\min(\chi(G_1+e),\chi(G_1/e))$ и
$\ds\chi(G_2)=\min(\chi(G_2+e),\chi(G_2/e))$, где конечно ребро
$e$ отличается на каждом графике. Продолжая таким образом, мы можем
в конечном итоге вычислить $\chi(G)$ при условии, что в конечном итоге мы получим
графы, которые «просто» раскрасить. Грубо говоря, поскольку $G/e$
имеет меньше вершин, а $G+e$ имеет больше ребер, мы должны в конце концов закончить
построить полный граф по всем ветвям
вычисление. Всякий раз, когда мы встречаем полный граф $K_m$, он имеет
хроматическое число $m$, поэтому никаких дальнейших вычислений вдоль
соответствующую ветку. Давайте сделаем это более точным.

Теорема 5.8.13 Приведенный выше алгоритм правильно вычисляет хроматическое число в
конечное количество времени.

Доказательство.
Предположим, что граф $G$ имеет $n$ вершин и $m$ ребер. Количество
пар несмежных вершин равно $\na(G)={n\choose 2}-m$. Доказательство
по индукции по $\na$.

Если $\na(G)=0$, то $G$ — полный граф и алгоритм
немедленно прекращается.

Теперь заметим, что $\na(G+e)

Теперь, если $\na(G)>0$, $G$ не является полным графом, поэтому существуют несмежные
вершины $v$ и $w$. По индукционному предположению
алгоритм правильно вычисляет $\chi(G+e)$ и $\chi(G/e)$ и, наконец,
вычисляет $\chi(G)$ из них за один дополнительный шаг.
$\qed$

Хотя этот алгоритм очень неэффективен, он
достаточно быстро, чтобы его можно было использовать на небольших графах с помощью
компьютер.

Пример 5.8.14 Проиллюстрируем очень простым графиком:

Хроматическое число графика вверху равно
$\мин(3,4)=3$. (Конечно, это довольно легко увидеть непосредственно.)
$\квадрат$

Пример 5.8.1
Предположим, что $G$ имеет $n$ вершин и хроматическое число
$к$. Докажите, что $G$ имеет не менее $k\choose2$ ребер.

Пример 5.8.2
Найдите хроматическое число приведенного ниже графика, используя
алгоритм в этом разделе. Нарисуйте все графы $G+e$ и $G/e$
сгенерированный алгоритмом в виде «древовидной структуры» с полным
графики внизу, обозначьте каждый полный график его хроматическим
число, затем распространите значения до исходного графика.

Пример 5.8.3
Покажите, что $\chi(G-v)$ есть либо $\chi(G)$, либо
$\хи(G)-1$.

Пример 5.8.4
Докажите теорему 5.8.10.
не предполагая каких-либо конкретных
свойства порядка $v_1,\ldots,v_n$.

Пример 5.8.5
Докажите теорему 5.8.12 следующим образом.
По следствию 5. 8.11 нам нужно рассматривать только регулярные
графики. Регулярные графы степени 2 просты, поэтому мы рассматриваем только
регулярные графы степени не ниже 3.

Если $G$ не является 2-связным, покажите, что блоки $G$ могут быть окрашены
с цветами $\Delta(G)$, и тогда раскраски можно изменить
немного так, чтобы они вместе давали правильную окраску $G$.

Если $G$ 2-связен, покажите, что существуют вершины $u$, $v$, $w$ такие
что $u$ смежно и с $v$, и с $w$, $v$ и $w$ не смежны.
смежно, а $G-v-w$ связно. Учитывая такие вершины,
цвет $v$ и $w$ с цветом 1,
затем раскрасьте оставшиеся вершины жадным алгоритмом, подобным
к этому в
теорема \xrefnexternal{thm:почти ручьи}{cgt.pdf},
где $u$ играет роль $v_n$.

Чтобы показать существование $u$, $v$, $w$, как требуется, пусть $x$ будет
вершина, не смежная со всеми остальными вершинами. Если $G-x$ 2-связен,
пусть $v=x$, пусть $w$ находится на расстоянии 2 от $v$ (обоснуйте это), и пусть
путь длины 2 равен $v,u,w$. Воспользуйтесь теоремой 5.