4. Выберите сначала светлоту, а затем цветовой тон*.
Даются рекомендации по выбору фонового цвета, который часто бывает светлым и приглушенным, затем следует переходить к акцентирующим цветам, которые могут быть темными или яркими. Только после этого можно определяться с цветовыми тонами.
5. Меняйте тона.Обращается внимание на то, что более важным представляется разнообразие светлоты цветов в комбинации, чем цветовых тонов.
6. Пользуйтесь совместимыми цветовыми тонами.Обращается внимание на то, что комбинации, где меняются и светлоты и цветовые тона, почти всегда страдают избытком контрастности. Один из способов получения более совместимых оттенков – это соединить небольшое количество одного цвета с другим и небольшую дозу второго с первым. Например, красно-фиолетовый и сине-фиолетовый лучше смотрятся, чем красный и синий.
7. Ограничивайте количество цветов. Обычно хватает двух-трех цветов. Пять – уже многовато. Особенно тщательно следует отбирать четырехцветные сочетания. Следует всегда думать о доминирующем цветовом тоне, который определяет гамму в целом. Все остальные цвета должны быть подчинены по своему цветовому тону, насыщенности и светлоте.
10. Пользуйтесь знакомыми цветами.Лучше не употреблять цветовые тона, которые редко встречаются в естественной среде, либо знакомые цвета с непривычной светлотой. Для традиционной публики используйте традиционные цвета.
11. Пользуйтесь природными цветами.Природные цвета гармоничны по определению, ибо наше зрение более всего приспособлено к ним. Так как глаза прекрасно различают светотень, важно варьировать светлоты гаммы, а не ее цветовые тона.
Если сопоставить эти практические советы с теми фактами, что выявили в цветовой гармонии Джадд и Вышецки, а также с рекомендациями Л.Н. Мироновой, мы видим их разительное сходство.
* Термины изменены, так как в источнике нестрого переведены термины: светлота названа тоном, а цветовой тон – оттенком.
Алгоритм определяет длины кратчайших путей от фиксированной вершины s до всех остальных вершин графа. Он корректно работает с дугами отрицательной длины и, в случае присутствия в графе контура отрицательной длины, обнаруживает его и сообщает о невозможности построения кратчайших путей.
Заметим, что всякий кратчайший путь – это простая цепь, поэтому в любом кратчайшем пути в графе G с множеством вершин {s,v1,v2, … vn} не более n дуг.
Обозначим через – длину пути от вершины s до вершины vi, кратчайшего из всех путей от s до vi, в которых не более k дуг.
Тогда
(1)
. (2)
Здесь – это длина пути до вершины vi, предпоследняя вершина которого – vj. Причем путь до vj – кратчайший из всех путей до этой вершины, в которых не более чем k дуг.
Зная числа , , можно шаг за шагом рассчитать числа ,..., , . Если задача о кратчайшем пути имеет решение, величины , - это заведомо длины кратчайших путей от вершины s до вершин v1,v2, …, vn.
Чтобы определить, есть ли в графе G контур отрицательной длины, нужно рассчитать числа , . Если окажется, что хотя бы одно из этих чисел меньше соответствующего значения предыдущего шага, в графе есть контур отрицательной длины: путь от вершины s до некоторой вершины v, содержащий n+1 дугу оказался короче пути от s до v, состоящего из n дуг.
Алгоритм может окончить работу быстрее, чем за n шагов. Не обязательно, чтобы в графе существовали кратчайшие пути, содержащие n дуг. Если все числа , , найденные на шаге совпадают с соответствующими величинами, определенными на k-м шаге, то кратчайшие пути найдены, а максимальное число дуг в кратчайших путях равно k.
Пример 1. Определим кратчайшие пути от вершины 1 до всех остальных вершин графа, изображенного на рис. 1. В графе есть дуги отрицательной длины, поэтому применим алгоритмом Беллмана.
И здесь удобно воспользоваться таблицей (табл. 1).Столбцы таблицы соответствуют вершинам графа. В k-й строке таблицы стоят числа , . Первый столбец таблицы соответствует вершине s (вершине 1), он содержит одни нули.
На первом шаге находятся пути из одной дуги до вершин 2, 4, 5. Значит, пути, состоящие не более чем из двух дуг, следует искать только до вершин, в которые входят дуги выходящие из вершин 2, 4, 5 (рис. 2).
Над кружками с номерами вершин на рис. 2 стоят длины путей до этих вершин, найденные на предыдущем шаге.
;
;
;
;
;
;
; .
Заполним вторую строку табл. 1.
Таблица 1
∞
∞
∞
∞
∞
Уменьшились длины путей до вершин 2, 3, 6, 7, 8, 9. Значит, имеет смысл искать более короткие пути до тех вершин графа, в которые входят дуги из перечисленных вершин (рис. 3).
; ;
;
;
; ;
.
Заполняем третью строку табл. 1. На третьем шаге уменьшились длины путей до вершин 3, 5, 6, 8, 9. Постараемся найти более короткие пути до
тех вершин графа, в которые входят дуги, выходящие из перечисленных вершин (рис. 4).
; ;
;
; ;
; .
Заполняем четвертую строку таблицы. Уменьшились длины путей до вершин 3, 5, 8, 9. Продолжаем действовать по алгоритму Беллмана (рис. 5).
;
;
;
;
;
; .
Заполняем пятую строку таблицы. Уменьшились длины путей до вершин 3, 5, 9. Следовательно, нужно пересчитать длины путей до вершин 2, 3, 4, 5, 6, 7, 9.
; ;
;
;
; ;
.
Заполняем шестую строку таблицы.
Уменьшилась длина пути до вершины 3.
Нужно пересчитать длины путей до вершин 2, 5, 6.
;
;
.
Заполняем седьмую строку таблицы. Длины седьмой строки повторяют длины шестой строки. Кратчайшие пути найдены и среди них есть пути, состоящие из шести дуг.
Построим дерево кратчайших путей (рис. 6). Длина кратчайшего пути до вершины 4 была найдена уже в первой строке. Значит, этот путь состоит из одной дуги. Включаем в дерево дугу (1, 4). Во второй строке стоят длины кратчайших путей до вершин 2 и 7. Следовательно, эти пути включают в себя две дуги. Из расчетов (и диаграммы) вытекает, что предпоследняя вершина кратчайшего пути как до вершины 2, так и до вершины 7 – это вершина 4. В дерево кратчайших путей добавляем дуги (4,2) и (4,7).
В третьей строке табл. 1 стоит длина кратчайшего пути до вершины 6, этот путь состоит из трех дуг. Пользуясь расчетами (и диаграммой) находим, что кратчайший путь до вершины 6 – это путь 1-4-2-6. Включаем в дерево дугу (2,6). Продолжая анализ табл. 1, достраиваем дерево кратчайших путей.
Пример 2. Покажем, как алгоритм Беллмана обнаруживает контур отрицательной длины.
На рис. 7 изображен граф, для которого задача о кратчайшем пути не имеет решения из-за присутствия контура 2-3-4-2 длины -1. Из-за него длины путей от вершины 1 до всех остальных вершин графа можно сделать как угодно большими по модулю, но отрицательными по знаку.
Для этого достаточно обойти контур 2-3-4-2 нужное число раз.
Без дальнейших пояснений приведем таблицу алгоритма Беллмана (табл. 2).
В четвертой строке табл. 2 уменьшилась длина пути до второй вершины. Путь из четырех дуг 1-2-3-4-2 оказался короче пути из одной дуги (1,2). Алгоритм обнаружил в графе контур отрицательной длины.
