Раскраска - карта
Cтраница 1
Раскраска карты на сфере - это окрашивание каждой области карты одним цветом так, чтобы никакие две соседние области не были окрашены одинаковым цветом. Таким образом, две области карты, обладающие указанным выше свойством ( штаты Колорадо и Аризона), могут быть окрашены одинаковым цветом, а страны, подобные Франции и Испании, должны быть окрашены в разные цвета. [1]
Задача раскраски карты состоит в приписывании каждой стране на заданной карте одного из четырех заданных цветов с таким расчетом, чтобы ни одна пара соседних стран не была окрашена в одинаковый цвет. Существует теорема, которая гарантирует, что это всегда возможно. [2]
Для задач типа раскраски карты условие согласованного унификатора работает подобно функции-ограничению и также дает значительное сокращение перебора. При условии применения такого сокращения опровержение графа связи с использованием AND-параллельной резолюции дает ускорение в 5 - 10 раз по сравнению с AND-параллельной резолюцией с полным перебором и в 50 - 70 раз по сравнению с последовательным опровержением. [3]
 |
Размер активов российских банков.| Уставной фонд. [4] |
Ниже приводится ряд раскрасок карты Кохонена Российских банков по некоторым статьям баланса. Как видно из карт Итого доходов и Итого расходов, наиболее активные банки ( банки; у которых отношение доходов и расходов к их размеру наибольшее) располагаются в левом верхнем углу карты. Карта размеров говорит нам о том, что эти банки относительно невелики по своим размерам. [5]
Показать, что для раскраски карты на листе Мебиуса необходимо шесть цветов. [6]
Теперь уже несложно проверить, что определенная нами раскраска карты G действительно является 4-раскраской. [7]
Одной из наиболее известных нерешенных проблем в математике является задача о раскраске карты, в которой требуется доказать или опровергнуть тот факт, что любую карту на плоскости можно раскрасить, используя четыре цвета или меньше. Карта делит плоскость на много областей; ограничение состоит в том, что две области, имеющие общую границу, должны быть раскрашены в разные цвета. Если бы существовал алгоритм, позволяющий найти минимальное количество цветов для любой карты, то он мог бы служить для построения примеров и контрпримеров. [8]
В данной главе в полном виде приводится программа для задачи о раскраске карты ( см. гл. Читатели, которым довелось испытать это на собственной шкуре, знают как трудно описывать программу, излагая алгоритм прозрачно и просто. Когда решение головоломки рассказано, обычной реакцией бывает: Как я не догадался. Ну а программа - это, конечно, тоже решение головоломки. Из описаний всегда устраняют дух исследования, историю неудавшихся подходов и отступлений, упоминание о глупых ошибках, сбивавших с правильного пути. [9]
Рассмотрим работу надстройки автоматического выбора параллельного метода на примере решения тестовой задачи раскраски карты. [10]
Новый способ упорядочивания списка стран резко повышает эффективность по отношению к исходному, алфавитному порядку, и теперь возможные раскраски карты Европы будут получены без труда. [11]
Раскраской данной карты М на S называют такое приписывание цвета каждой области карты, при котором никаким двум соседним областям не приписывается один и тот же цвет. В каждой раскраске карты М используется некоторое число цветов. [12]
Если в каждой стране поместить вершину графа и соединить ребрами все пары вершин, расположенные в соседних странах ( они имеют общую границу), мы получим граф географической карты. Его хроматическое число совпадает с минимальным числом красок для раскраски карты. [13]
Рассмотрим граф G, вершины которого - страны, а ребра соединяют страны, имеющие общую границу. Числу x ( G) соответствует наименьшее число красок, необходимых для раскраски карты так, чтобы никакие две соседние страны не были окрашены в один цвет. [14]
Та же самая процедура получения однородной карты степени 3 из плоской карты применима также для карты на поверхности р-го рода. Далее мы будем рассматривать только связные карты, так как нетрудно видеть, что раскраска несвязной карты является частным случаем раскраски связной. [15]
Страницы: 1 2