Эффективная аффинная аппроксимация в метрике L₁
Предложен эффективный алгоритм поиска оптимального в терминах метрики L₁ аффинного преобразования одного вектора в другой, открывающий возможности к применению метрики L₁ в задачах, где она не использовалась....
Gespeichert in:
| Datum: | 2010 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
2010
|
| Schriftenreihe: | Управляющие системы и машины |
| Schlagworte: | |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/82841 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Эффективная аффинная аппроксимация в метрике L₁ / М.А. Тищенко, Д.А. Кордубан // Управляющие системы и машины. — 2010. — № 4. — С. 25-30. — Бібліогр.: 7 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-82841 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-828412015-06-11T03:02:05Z Эффективная аффинная аппроксимация в метрике L₁ Тищенко, М.А. Кордубан, Д.А. Новые методы в информатике Предложен эффективный алгоритм поиска оптимального в терминах метрики L₁ аффинного преобразования одного вектора в другой, открывающий возможности к применению метрики L₁ в задачах, где она не использовалась. An efficient algorithm of the search for the optimal affine transformation of a vector to another one in terms of L₁ metric is suggested. The algorithm unveils the possibility of exploiting L₁ metric in problems where it was not used. Запропоновано ефективний алгоритм пошуку оптимального в термінах метрики L₁ афінного перетворення одного вектора в інший, який дозволяє використовувати метрику L₁ в задачах, де вона не використовувалася. 2010 Article Эффективная аффинная аппроксимация в метрике L₁ / М.А. Тищенко, Д.А. Кордубан // Управляющие системы и машины. — 2010. — № 4. — С. 25-30. — Бібліогр.: 7 назв. — рос. 0130-5395 http://dspace.nbuv.gov.ua/handle/123456789/82841 004.021 ru Управляющие системы и машины Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Новые методы в информатике Новые методы в информатике |
| spellingShingle |
Новые методы в информатике Новые методы в информатике Тищенко, М.А. Кордубан, Д.А. Эффективная аффинная аппроксимация в метрике L₁ Управляющие системы и машины |
| description |
Предложен эффективный алгоритм поиска оптимального в терминах метрики L₁ аффинного преобразования одного вектора в другой, открывающий возможности к применению метрики L₁ в задачах, где она не использовалась. |
| format |
Article |
| author |
Тищенко, М.А. Кордубан, Д.А. |
| author_facet |
Тищенко, М.А. Кордубан, Д.А. |
| author_sort |
Тищенко, М.А. |
| title |
Эффективная аффинная аппроксимация в метрике L₁ |
| title_short |
Эффективная аффинная аппроксимация в метрике L₁ |
| title_full |
Эффективная аффинная аппроксимация в метрике L₁ |
| title_fullStr |
Эффективная аффинная аппроксимация в метрике L₁ |
| title_full_unstemmed |
Эффективная аффинная аппроксимация в метрике L₁ |
| title_sort |
эффективная аффинная аппроксимация в метрике l₁ |
| publisher |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України |
| publishDate |
2010 |
| topic_facet |
Новые методы в информатике |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/82841 |
| citation_txt |
Эффективная аффинная аппроксимация в метрике L₁ / М.А. Тищенко, Д.А. Кордубан // Управляющие системы и машины. — 2010. — № 4. — С. 25-30. — Бібліогр.: 7 назв. — рос. |
| series |
Управляющие системы и машины |
| work_keys_str_mv |
AT tiŝenkoma éffektivnaâaffinnaâapproksimaciâvmetrikel1 AT kordubanda éffektivnaâaffinnaâapproksimaciâvmetrikel1 |
| first_indexed |
2025-07-06T09:31:05Z |
| last_indexed |
2025-07-06T09:31:05Z |
| _version_ |
1836889425736368128 |
| fulltext |
УСиМ, 2010, № 4 25
УДК 004.021
М.А. Тищенко, Д.А. Кордубан
Эффективная аффинная аппроксимация в метрике 1L
Предложен эффективный алгоритм поиска оптимального в терминах метрики L1 аффинного преобразования одного вектора в
другой, открывающий возможности к применению метрики L1 в задачах, где она не использовалась.
An efficient algorithm of the search for the optimal affine transformation of a vector to another one in terms of L1 metric is suggested.
The algorithm unveils the possibility of exploiting L1 metric in problems where it was not used.
Запропоновано ефективний алгоритм пошуку оптимального в термінах метрики L1 афінного перетворення одного вектора в
інший, який дозволяє використовувати метрику L1 в задачах, де вона не використовувалася.
Введение. Метрики L1 и L2 – едва ли не самые
распространенные во многих областях приклад-
ной математики, и, в частности, в структурном
распознавании. Каждая из них, в контексте тех
или иных задач, имеет как преимущества, так
и недостатки. Один из недостатков метрики L2,
применительно к задачам аппроксимации экс-
периментальных данных, – существенное вли-
яние «выбросов» на результат аппроксимации
[1], в то время как метрика L1 этого лишена. В
свою очередь, преимуществом метрики L2 в
сравнении с L1 является то, что во многих слу-
чаях задачи, сформулированные в этой метри-
ке, аналитически разрешимы. Благодаря этому
преимуществу, метрика L2 широко применя-
лась как на заре структурного распознавания
[2, 3], так и в более поздних работах [4–6]. В
частности, задача аффинной аппроксимации,
т.е. минимизации функции вида:
1
n
i i
i=
x a y b (1)
в метрике L2 может быть решена аналитиче-
ски. В то же время при постановке в метрике
L1 даже построение эффективного алгоритма
решения этой задачи выглядит довольно про-
блематично. В данной статье не ставится и тем
более не решается вопрос о том, какую из ука-
занных метрик следует применять. В ней пред-
лагается итеративный алгоритм решения зада-
чи минимизации функции (1) в метрике L1, ко-
торый в наихудшем случае работает за время
порядка O(n2).
Постановка и анализ задачи
Пусть задано два вектора x = (x1, x2, , xn)
T
R
n и y = (y1, y2, , yn)
T
R
n. Необходимо най-
ти параметры a и b, доставляющие минимум
функции:
1
n
i i
i=
F a,b = x a y b . (2)
Отметим, что функция (2) обладает таким
свойством, что поиск минимизирующих ее па-
раметров a и b достаточно проводить лишь по
тем их значениям, которые обращают в ноль
по крайней мере два слагаемых в сумме (2).
Более строго это утверждение формулируется
в лемме 2. Лемма 1 представляет собой вспо-
могательное утверждение, необходимое для
доказательства леммы 2.
Лемма 1. Пусть задано два вектора x = (x1,
x2, , xn)
T
R
n и y = (y1, y2, , yn)
T
R
n, а также
функция :f R R вида:
1
n
i i
i=
f a = x a y .
Тогда существует такой индекс j и такое зна-
чение *a , что
xj – a yj = 0,
и
af=af
a
min .
Лемма 2. Пусть a и b – значения параметров
a и b соответственно, при которых (2) достига-
ет минимума. Тогда существуют такие aи b,
что для некоторых двух различных индексов j
и k выполняется требование: xj – a yj – b = 0
и 0k kx a' y b' = и соблюдается равенство
* *F a ,b = F a',b' .
Доказательство. Предположим, что значе-
ния *a и *b не обращают в ноль ни одно сла-
26 УСиМ, 2010, № 4
гаемое из (2). В противном случае следует пе-
рейти к п. 2 доказательства.
Рассмотрим (2) как функцию от a при фик-
сированном значении b = b. В силу леммы 1
найдется такое значение a, что * ,F a',b =F a b
и для некоторого индекса j выполняется:
* 0j jx a' y b = .
Следовательно, без потери общности можно
считать, что параметры a и b обращают в
ноль по крайней мере одно слагаемое в (2).
Теперь мы имеем значения параметров a и
b, обращающие в ноль по крайней мере одно
слагаемое из суммы (2). Предположим, что та-
кое слагаемое единственно. В противном слу-
чае требование леммы уже выполняется. Обо-
значим через j индекс этого слагаемого. Рас-
смотрим множество таких пар (a, b), при кото-
рых j-е слагаемое обращается в ноль:
0j jx a y b = . (3)
Это множество задается зависимостью
j jb = x a y . (4)
Подставим это значение b в (2):
1
n
i j i j
i=
F a, j = x x a y y . (5)
В силу леммы 1 существует такое значение
a, что F(a, j) = F(a, j) и для некоторого k j
выполняется равенство:
0k j k jx x a' y y = .
Следовательно, мы нашли такие значения
a' и j jb' = x a' y , что F(a, b) = F(a, b) и
для некоторых двух различных индексов j и k
выполняется требование: 0j jx a' y b' = и
0k kx a' y b' = .
Лемма доказана.
Из леммы 2 непосредственно следует алго-
ритм поиска оптимальных значений парамет-
ров a и b, сложности O(n3). Проводится пере-
бор по всем парам индексов i и j, j > i . На ос-
новании системы уравнений:
0
0
i ij i ij
j ij j ij
x a y b =
x a y b =
(6)
определяются параметры aij и bij. Из множества
параметров , : 1,..., 1;ij ijP = a b i = n j = i+1,
, n} путем прямого перебора выбирается па-
ра (aij, bij), доставляющая минимум функции (2).
С учетом леммы 1 это и будет решением задачи.
Множество P содержит
2
2
n n
элементов.
Для подсчета значения функции (2) при неко-
торых фиксированных значениях a и b необхо-
димо порядка n операций. Таким образом, по-
лучаем сложность O(n3).
В следующем разделе указан более эффек-
тивный алгоритм решения задачи (2).
Эффективный алгоритм решения задачи
Решение задачи в одномерном случае
Рассмотрим задачу минимизации функции (5)
по переменной a. В силу леммы 1 минимум
этой функции достаточно искать при таких зна-
чениях параметра a, при которых по крайней
мере одно из слагаемых в (5) равно нулю. Обо-
значим множество таких значений параметра a
через A(j) = {a : i : xi – xj – a (yi – yj) = 0}.
Запишем выражение для производной слева
функции (5):
: 0
: 0
0,
.
i x x a y y <i j i j
i x x a y y >i j i j
i j
i j
F' a j = y y
y y
(7)
Обозначим разности xi – xj и yi – yj через ix
и iy соответственно1. Перепишем в этих обо-
значениях выражение (7) не указывая, для
удобства, зависимости от j:
: 0 : 0
0
i x a y < i x a y >i i i i
i iF' a = y y
. (8)
Без потери общности предположим, что
0iy > для всех 1,...,i = n . Тогда (8) можно пе-
реписать в виде:
1 В случае когда требуется минимизировать не (2), а
функцию вида: ,zbyax=ba,F
n
=i
iii
1
можно приме-
нить подобные рассуждения. Тогда через ix и iy сле-
дует обозначить величины:
j
ii
ii
j
ij
ii z
zy
y=y,
z
zx
x=x ~~ .
УСиМ, 2010, № 4 27
: :
0
x xi ii a> i a<
y yi i
i iF' a = y y
. (9)
При наименьших значениях a из A j все
, 1,...,iy i = n будут содержаться во второй
сумме выражения (9), и, следовательно, произ-
водная 0F' a будет отрицательной. При
увеличении a количество слагаемых во второй
сумме выражения (9) будет уменьшаться, а в
первой – увеличиваться. При некотором зна-
чении a' параметра a наступит одно из сле-
дующих событий:
производная станет положительной:
0 0F' a' > , (10)
производная станет равной нулю:
0 0F' a' = . (11)
Если имеет место первый случай, то мини-
мум функции (5) достигается при единствен-
ном значении параметра a, а именно при
a = prev a' , где prev a' – предшествую-
щий a' по величине элемент множества A j .
Если же имеет место второй случай, то мини-
мум достигается на интервале prev a' ,a' .
На основании изложенных соображений по-
строим алгоритм, выдающий оптимальное зна-
чение параметра a и множество индексов:
* *: 0i j i jI a , j = i x x a y y = ,i j . (12)
Предположим, что имеется алгоритм, кото-
рый указывает a. Такой алгоритм, для случая,
когда все iy в (9) равны единице, описан в [7]
и назван в данном источнике Select. Его слож-
ность составляет O(n). В [7] имеется также
рандомизированная версия этого алгоритма –
Randomized_Select, для которого O(n) – ожи-
даемое время работы. Второй из указанных
алгоритмов – более практичный, так как в его
асимптотической оценке скрыта меньшая кон-
станта. Оба эти алгоритма легко обобщаются
на случай произвольных iy . Опишем обобще-
ние алгоритма Randomized_Select.
Алгоритм 0
Ш а г 1. Сформировать рабочий массив пар:
, , 1,...,i
i
i
x
A= y i = n
y
.
Первый элемент i-й пары назовем ключом, а
второй – значением, и обозначим соответствен-
но k A i , и v A i .
Задать границы обрабатываемой области мас-
сива A :
: 1, : .head = tail = n
Ш а г 2. Случайным образом выбрать эле-
мент q в подмассиве ...A head tail . Преобра-
зовать подмассив ...A head tail таким образом,
чтобы:
, ;
, ,
k A i k q head i index q
k A i > k q index q < i tail
где index q – индекс элемента q в преобразо-
ванном подмассиве.
Ш а г 3. Подсчитать суммы элементов мас-
сива A, расположенных по левую и правую
стороны от q:
1 1
, .
index q n
l r
i= i=index q +
s = v A i s = v A i
Ш а г 4. Если l rs = s , завершить работу ал-
горитма, и в качестве ответа выдать *:a = k q .
Если l rs < s , передвинуть начало обрабатыва-
емой области массива A:
: 1.head = index q +
Если l rs > s , передвинуть конец обрабаты-
ваемой области массива A:
: 1.tail = index q
Если head = tail, завершить работу алгоритма,
и в качестве ответа выдать :a = k A head . В
противном случае перейти к шагу 2.
В [7] изложено доказательство того факта,
что алгоритм Randomized_Select работает в сред-
нем за время O(n). Это доказательство может
быть механически перенесено на алгоритм 0.
На основании значения a, выданного алго-
ритмом 0, можно построить множество I (a
, j)
при помощи следующего простого алгоритма.
28 УСиМ, 2010, № 4
Алгоритм 1
Ш а г 1. Получить значение a с помощью
алгоритма 0.
Ш а г 2. Построить множество *I a , j :
* *: .i j
i j
x x
I a , j = i = a
y y
(13)
Решение задачи в двумерном случае
Построим алгоритм, который находит ми-
нимум функции (2) путем последовательного
применения алгоритма 1 к функции (5).
Алгоритм 2
Ш а г 1. Определим множество V = ин-
дексов слагаемых из суммы (2), которые уже
обработаны алгоритмом. Выберем из этой сум-
мы какое-либо из слагаемых. Пусть оно соот-
ветствует индексу j. Добавим индекс j к мно-
жеству V.
Будем рассматривать такие значения пара-
метров a и b, которые обращают в ноль j-е сла-
гаемое (рис. 1):
0.j jx a y b = (14)
(xk, yk)
(xj, yj)
x
y
Рис. 1. Иллюстрация работы алгоритма 2. Различные прямые
соответствуют различным значениям параметров a и b,
обращающим в ноль j-е слагаемое из (2)
Выразив b из (14) и подставив в (2) получим
(5), т.е. функцию, минимизируемую алгорит-
мом 1. Применив его, найдем такое значение *a
параметра a и множество I(a, j) (рис. 2), что:
arg min ,
a
a F a j .
Ш а г 2. Выберем из множества I(a, j) еще
не обработанные элементы:
Vj,aIj,aI=j,aI \: .
Последовательно применим алгоритм 1 к эле-
ментам множества I(a, j), добавляя соответ-
ствующие индексы в множество V до тех пор,
пока найдем такой индекс k I (a
, j), что:
min , , ,
a
F a k < F a j (15)
либо просмотрим все элементы множества.
(xk, yk)
(xj, yj)
y
x
Рис. 2. Иллюстрация работы алгоритма 2. Пара точек, через
которые проходит прямая, соответствует двум слагае-
мым, обращающимся в ноль при текущих значениях
параметров a и b
Ш а г 3. Если в множестве I(a, j) не суще-
ствует индекса k, удовлетворяющего (15), то
алгоритм заканчивает свою работу и выдает
результат – значения параметров (a, b), b=
= xj – a yj. В противном случае алгоритм пе-
реходит к шагу 2 с новыми значениями a и j:
: arg min ,
a
a F a k ,
: .j = k
В процессе выполнения алгоритма множе-
ство V монотонно увеличивается, следователь-
но алгоритм 2 закончит работу за количество
шагов, не превосходящее размерности про-
странства, в котором определены вектора x и y.
В худшем случае алгоритм 2 выполнит n вы-
зовов алгоритма 1, просмотрев все n возмож-
ных значений индекса j в (5). Первый шаг ал-
горитма 1 выполняется за время порядка O(n)
[7]. Второй его шаг также выполняется за ли-
нейное по n время. Таким образом, алгоритм 2
в худшем случае выполнится за O(n2).
Теорема 1. Точка останова алгоритма 2 – точ-
ка глобального минимума функции (2).
Доказательство. В силу выпуклости функ-
ции (2) ее локальный минимум – глобален. Сле-
довательно, для доказательства теоремы доста-
точно показать, что точка (a, b) – локальный
минимум функции (2).
УСиМ, 2010, № 4 29
Для наглядности дальнейших рассуждений
воспользуемся рис. 3. Каждая из изображенных
на нем прямых представляет множество точек,
соответствующих таким значениям параметров
a и b, которые обращают в ноль некоторое
фиксированное слагаемое из суммы (2). Сле-
довательно, точки пересечения этих прямых оп-
ределяют те значения параметров (a, b), при ко-
торых два или более слагаемых из (2) обраща-
ются в ноль. Троеточия между прямыми на
рис. 3 обозначают возможное наличие, помимо
1 mPP и k uP P , также других прямых, пересека-
ющихся в точке M, что соответствует той си-
туации, когда в этой точке обращаются в ноль
более двух слагаемых.
Pk
Pm
a
Pu
P1
M
b
Рис. 3. Точка минимума функции (2)
Пусть количество прямых, проходящих че-
рез точку M, равняется / 2r . Рассмотрим неко-
торый луч αi , исходящий из точки M, на кото-
ром обращается в ноль одно из слагаемых в
сумме (2). Возможны два случая:
существует хотя бы одна точка Pi на этом
луче, в которой более одного слагаемого из (2)
обращается в ноль. Без потери общности будем
считать, что на отрезке (M, Pi) обращается в
ноль единственное слагаемое из суммы (2);
на всем луче, за исключением точки M,
только одно слагаемое из (2) обращается в
ноль. Выберем на этом луче произвольную
точку, отличную от M, и обозначим ее Pi.
Теперь точки 1 2, ,..., ,..., ,..., ,..., k m u rP P P P P P вы-
браны таким образом, что на отрезках (M, Pi),
i = 1, , r обращается в ноль единственное сла-
гаемое из суммы (2). Следовательно, на этих
отрезках функция (2) – линейна.
Предположим, что алгоритм 2 закончил ра-
боту в точке M. Покажем, что в этой точке
функция (2) имеет локальный минимум. В со-
ответствии с шагами 2–3 алгоритма 2, значе-
ния функции (2) в точках 1 2, ,..., rP P P не мень-
ше, чем в точке M, иначе алгоритм перешел бы
в одну из этих точек. В силу линейности функ-
ции (2) в пределах каждого из треугольников
1 2 3 -1, ,..., 2 r rPP M P P M P P M , можно утверждать,
что в каждой точке многоугольника 1 2, ,..., rP P P
значение функции (2) не меньше ее значения в
точке M. Следовательно, точка M – локальный
минимум функции (2), а в силу ее выпуклости,
и глобальный.
Теорема доказана.
Замечания относительно программной ре-
ализации
Повышая быстродействие программной реа-
лизации алгоритма 2, можно разбить слагаемые
суммы (2) на N классов, в каждом из которых
значения пар i ix , y одинаковы:
1
,
N
i i i
i=
F a,b = w x a y b
где iw – количество элементов в i-м классе.
В этом случае (9) примет вид:
i.
iy
ix
<ai
ii
iy
ix
>ai
i ywyw=aF' ~~0
~
~
:~
~
:
. (16)
На первом шаге алгоритма 0 массив A сле-
дует формировать с учетом весовых коэффи-
циентов iw :
, , 1,..., .i
i i
i
x
A= w y i = N
y
В случае когда N n , такой прием позволя-
ет существенно сократить количество вычис-
лений.
Таким образом, в статье предложен эффек-
тивный алгоритм минимизации функции
1
n
i i
i=
F a,b = x a y b . (17)
Заключение. Алгоритм минимизации функ-
ции открывает возможность для использования
метрики L1 при постановке задач, где она ранее
не участвовала из-за отсутствия эффективных
30 УСиМ, 2010, № 4
алгоритмов минимизации функции (17). К таким
задачам можно отнести немалое количество
прикладных проблем распознавания образов,
и, в частности, обработки и распознавания
изображений.
1. Стецюк П.И., Колесник Ю.С., Лейбович М.М. О ро-
бастности метода наименьших модулей // Компью-
терная математика. – 2002. – 2. – С. 114–123.
2. Ковалевский В.А. Корреляционный метод распозна-
вания изображений. // Ж. выч. математикиии мат.
физика. – 1962. – 2, № 4.– С. 684–689.
3. Ковалевский В.А. Алгоритм разделения машинопис-
ной строки на знаки при отсутствии пробелов // ІІІ
Всесоюз. конф. по информационно-поисковым сис-
темам и автоматизированной обработке науч.-техн.
информации. – 1967. –Т. 3. – С. 156–164.
4. Рябоконь Д.И. Пространственная реконструкция по-
верхностей по стереопаре изображений с помощью
алгоритмов поиска минимального сечения на графе
// УСиМ. –2004. – № 3. – С. 47–51.
5. Рябоконь Д.И. Восстановление пространственной
конфигурации объектов и сцен по их стереоизоб-
ражениям // Там же. – 2005. – № 1. – С. 22–31.
6. Система доступу до приміщення на основі розпі-
знавання людських облич / В.М. Кийко, К.В. Кийко,
В.В. Мацелло та ін. // Пр. Восьмої Всеукр. міжнар.
конф. «УкрОБРАЗ’2006», Київ, 28–31 серпня 2006. –
С. 123–126.
7. Алгоритмы: построение и анализ / Т. Кормен, Ч. Лей-
зерсон, Р. Ривест и др. – М.: Вильямс, 2007. – 1296 с.
Поступила 16.03.2010
Тел. для справок: (044) 502-6314 (Киев)
E-mail: maxim.tischenko@gmail.com
© М.А. Тищенко, Д.А. Кордубан, 2010
Окончание статьи Г.А. Донца и др.
9 (7, 2, 1, 3, 8); 15 (8, 3, 1, 4, 9); 19 (8, 6, 2, 7,
9); 22 (7, 3, 1, 4, 8); 31 (8, 5, 2, 6, 9); 34 (9, 7, 5,
2, 6, 8); 37 (8, 6, 5, 7, 9); 38 (9, 6, 3, 1, 4, 7); 39
(6, 3, 1, 4, 7).
На каждой из этих цепей необходимо по-
строить правильную нумерацию f5(3) или f6(3),
что выполняется достаточно легко. Для деревьев
21 и 33 правильная нумерация приведена на
рис. 7.
Рис. 7. Правильная нумерация графов 21 и 33
Этот метод можно применять и для деревь-
ев более высокого порядка. На определенном
уровне придется прибегнуть к помощи вычис-
лительной техники. Как показала практика, не-
посредственное использование вычислитель-
ной техники для простого перебора вариантов
уже для деревьев порядка 20–22 наталкивается
на непреодолимые препятствия технического
характера.
Заключение. В данной статье продемонстри-
ровано решение проблемы Роса для деревьев с
числом вершин n = 9. Очевидно, что этот же ме-
тод можно распространить и на деревья более
высоких порядков. Для этого понадобится най-
ти правильную нумерацию для новых, более
сложных, чем звезда, цепь и гусеница, конфи-
гураций. Об этом пойдет речь в последующих
публикациях.
1. Петренюк А.Я. Півобертові деревні факторизації
повних графів // Укр. матем. журнал. – 2001. – 53,
№ 5. – С. 710–716.
2. Харари Ф. Теория графов. – М.: Мир, 1973. –
С. 267–268.
3. Rosa А. On certain valuations of the vertices of a graph. –
New York: Gordon and Breach, 1967. – Р. 349–355.
4. Cahit А. On graceful trees // Bull. of the ICA. – 1994. –
12 Sept. – Р. 15–18.
5. Донец Г.А. Об одной задаче нумерации вершин де-
ревьев // Матем. машины и системы. – 2010. – № 1. –
С. 17–24.
Поступила 19.02.2010
Тел. для справок: (044) 526-2188 (Киев)
© Г.А. Донец, Д.А. Петренюк, 2010
<<
/ASCII85EncodePages false
/AllowTransparency false
/AutoPositionEPSFiles true
/AutoRotatePages /None
/Binding /Left
/CalGrayProfile (Dot Gain 20%)
/CalRGBProfile (sRGB IEC61966-2.1)
/CalCMYKProfile (U.S. Web Coated \050SWOP\051 v2)
/sRGBProfile (sRGB IEC61966-2.1)
/CannotEmbedFontPolicy /Error
/CompatibilityLevel 1.4
/CompressObjects /Tags
/CompressPages true
/ConvertImagesToIndexed true
/PassThroughJPEGImages true
/CreateJobTicket false
/DefaultRenderingIntent /Default
/DetectBlends true
/DetectCurves 0.0000
/ColorConversionStrategy /CMYK
/DoThumbnails false
/EmbedAllFonts true
/EmbedOpenType false
/ParseICCProfilesInComments true
/EmbedJobOptions true
/DSCReportingLevel 0
/EmitDSCWarnings false
/EndPage -1
/ImageMemory 1048576
/LockDistillerParams false
/MaxSubsetPct 100
/Optimize true
/OPM 1
/ParseDSCComments true
/ParseDSCCommentsForDocInfo true
/PreserveCopyPage true
/PreserveDICMYKValues true
/PreserveEPSInfo true
/PreserveFlatness true
/PreserveHalftoneInfo false
/PreserveOPIComments true
/PreserveOverprintSettings true
/StartPage 1
/SubsetFonts true
/TransferFunctionInfo /Apply
/UCRandBGInfo /Preserve
/UsePrologue false
/ColorSettingsFile ()
/AlwaysEmbed [ true
]
/NeverEmbed [ true
]
/AntiAliasColorImages false
/CropColorImages true
/ColorImageMinResolution 300
/ColorImageMinResolutionPolicy /OK
/DownsampleColorImages true
/ColorImageDownsampleType /Bicubic
/ColorImageResolution 300
/ColorImageDepth -1
/ColorImageMinDownsampleDepth 1
/ColorImageDownsampleThreshold 1.50000
/EncodeColorImages true
/ColorImageFilter /DCTEncode
/AutoFilterColorImages true
/ColorImageAutoFilterStrategy /JPEG
/ColorACSImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/ColorImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/JPEG2000ColorACSImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/JPEG2000ColorImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/AntiAliasGrayImages false
/CropGrayImages true
/GrayImageMinResolution 300
/GrayImageMinResolutionPolicy /OK
/DownsampleGrayImages true
/GrayImageDownsampleType /Bicubic
/GrayImageResolution 300
/GrayImageDepth -1
/GrayImageMinDownsampleDepth 2
/GrayImageDownsampleThreshold 1.50000
/EncodeGrayImages true
/GrayImageFilter /DCTEncode
/AutoFilterGrayImages true
/GrayImageAutoFilterStrategy /JPEG
/GrayACSImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/GrayImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/JPEG2000GrayACSImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/JPEG2000GrayImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/AntiAliasMonoImages false
/CropMonoImages true
/MonoImageMinResolution 1200
/MonoImageMinResolutionPolicy /OK
/DownsampleMonoImages true
/MonoImageDownsampleType /Bicubic
/MonoImageResolution 1200
/MonoImageDepth -1
/MonoImageDownsampleThreshold 1.50000
/EncodeMonoImages true
/MonoImageFilter /CCITTFaxEncode
/MonoImageDict <<
/K -1
>>
/AllowPSXObjects false
/CheckCompliance [
/None
]
/PDFX1aCheck false
/PDFX3Check false
/PDFXCompliantPDFOnly false
/PDFXNoTrimBoxError true
/PDFXTrimBoxToMediaBoxOffset [
0.00000
0.00000
0.00000
0.00000
]
/PDFXSetBleedBoxToMediaBox true
/PDFXBleedBoxToTrimBoxOffset [
0.00000
0.00000
0.00000
0.00000
]
/PDFXOutputIntentProfile ()
/PDFXOutputConditionIdentifier ()
/PDFXOutputCondition ()
/PDFXRegistryName ()
/PDFXTrapped /False
/CreateJDFFile false
/Description <<
/ARA <FEFF06270633062A062E062F0645002006470630064700200627064406250639062F0627062F0627062A002006440625064606340627062100200648062B062706260642002000410064006F00620065002000500044004600200645062A064806270641064206290020064406440637062806270639062900200641064A00200627064406450637062706280639002006300627062A0020062F0631062C0627062A002006270644062C0648062F0629002006270644063906270644064A0629061B0020064A06450643064600200641062A062D00200648062B0627062606420020005000440046002006270644064506460634062306290020062806270633062A062E062F062706450020004100630072006F0062006100740020064800410064006F006200650020005200650061006400650072002006250635062F0627063100200035002E0030002006480627064406250635062F062706310627062A0020062706440623062D062F062B002E0635062F0627063100200035002E0030002006480627064406250635062F062706310627062A0020062706440623062D062F062B002E>
/BGR <FEFF04180437043f043e043b043704320430043904420435002004420435043704380020043d0430044104420440043e0439043a0438002c00200437043000200434043000200441044a0437043404300432043004420435002000410064006f00620065002000500044004600200434043e043a0443043c0435043d04420438002c0020043c0430043a04410438043c0430043b043d043e0020043f044004380433043e04340435043d04380020043704300020043204380441043e043a043e043a0430044704350441044204320435043d0020043f04350447043004420020043704300020043f044004350434043f0435044704300442043d04300020043f043e04340433043e0442043e0432043a0430002e002000200421044a04370434043004340435043d043804420435002000500044004600200434043e043a0443043c0435043d044204380020043c043e0433043004420020043404300020044104350020043e0442043204300440044f0442002004410020004100630072006f00620061007400200438002000410064006f00620065002000520065006100640065007200200035002e00300020043800200441043b0435043404320430044904380020043204350440044104380438002e>
/CHS <FEFF4f7f75288fd94e9b8bbe5b9a521b5efa7684002000410064006f006200650020005000440046002065876863900275284e8e9ad88d2891cf76845370524d53705237300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c676562535f00521b5efa768400200050004400460020658768633002>
/CHT <FEFF4f7f752890194e9b8a2d7f6e5efa7acb7684002000410064006f006200650020005000440046002065874ef69069752865bc9ad854c18cea76845370524d5370523786557406300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c4f86958b555f5df25efa7acb76840020005000440046002065874ef63002>
/CZE <FEFF005400610074006f0020006e006100730074006100760065006e00ed00200070006f0075017e0069006a007400650020006b0020007600790074007600e101590065006e00ed00200064006f006b0075006d0065006e0074016f002000410064006f006200650020005000440046002c0020006b00740065007200e90020007300650020006e0065006a006c00e90070006500200068006f006400ed002000700072006f0020006b00760061006c00690074006e00ed0020007400690073006b00200061002000700072006500700072006500730073002e002000200056007900740076006f01590065006e00e900200064006f006b0075006d0065006e007400790020005000440046002000620075006400650020006d006f017e006e00e90020006f007400650076015900ed007400200076002000700072006f006700720061006d0065006300680020004100630072006f00620061007400200061002000410064006f00620065002000520065006100640065007200200035002e0030002000610020006e006f0076011b006a016100ed00630068002e>
/DAN <FEFF004200720075006700200069006e0064007300740069006c006c0069006e006700650072006e0065002000740069006c0020006100740020006f007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400650072002c0020006400650072002000620065006400730074002000650067006e006500720020007300690067002000740069006c002000700072006500700072006500730073002d007500640073006b007200690076006e0069006e00670020006100660020006800f8006a0020006b00760061006c0069007400650074002e0020004400650020006f007000720065007400740065006400650020005000440046002d0064006f006b0075006d0065006e0074006500720020006b0061006e002000e50062006e00650073002000690020004100630072006f00620061007400200065006c006c006500720020004100630072006f006200610074002000520065006100640065007200200035002e00300020006f00670020006e0079006500720065002e>
/DEU <FEFF00560065007200770065006e00640065006e0020005300690065002000640069006500730065002000450069006e007300740065006c006c0075006e00670065006e0020007a0075006d002000450072007300740065006c006c0065006e00200076006f006e002000410064006f006200650020005000440046002d0044006f006b0075006d0065006e00740065006e002c00200076006f006e002000640065006e0065006e002000530069006500200068006f006300680077006500720074006900670065002000500072006500700072006500730073002d0044007200750063006b0065002000650072007a0065007500670065006e0020006d00f60063006800740065006e002e002000450072007300740065006c006c007400650020005000440046002d0044006f006b0075006d0065006e007400650020006b00f6006e006e0065006e0020006d006900740020004100630072006f00620061007400200075006e0064002000410064006f00620065002000520065006100640065007200200035002e00300020006f0064006500720020006800f600680065007200200067006500f600660066006e00650074002000770065007200640065006e002e>
/ESP <FEFF005500740069006c0069006300650020006500730074006100200063006f006e0066006900670075007200610063006900f3006e0020007000610072006100200063007200650061007200200064006f00630075006d0065006e0074006f00730020005000440046002000640065002000410064006f0062006500200061006400650063007500610064006f00730020007000610072006100200069006d0070007200650073006900f3006e0020007000720065002d0065006400690074006f007200690061006c00200064006500200061006c00740061002000630061006c0069006400610064002e002000530065002000700075006500640065006e00200061006200720069007200200064006f00630075006d0065006e0074006f00730020005000440046002000630072006500610064006f007300200063006f006e0020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e003000200079002000760065007200730069006f006e0065007300200070006f00730074006500720069006f007200650073002e>
/ETI <FEFF004b00610073007500740061006700650020006e0065006900640020007300e4007400740065006900640020006b00760061006c006900740065006500740073006500200074007200fc006b006900650065006c007300650020007000720069006e00740069006d0069007300650020006a0061006f006b007300200073006f00620069006c0069006b0065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740069006400650020006c006f006f006d006900730065006b0073002e00200020004c006f006f0064007500640020005000440046002d0064006f006b0075006d0065006e00740065002000730061006100740065002000610076006100640061002000700072006f006700720061006d006d006900640065006700610020004100630072006f0062006100740020006e0069006e0067002000410064006f00620065002000520065006100640065007200200035002e00300020006a00610020007500750065006d006100740065002000760065007200730069006f006f006e00690064006500670061002e000d000a>
/FRA <FEFF005500740069006c006900730065007a00200063006500730020006f007000740069006f006e00730020006100660069006e00200064006500200063007200e900650072002000640065007300200064006f00630075006d0065006e00740073002000410064006f00620065002000500044004600200070006f0075007200200075006e00650020007100750061006c0069007400e90020006400270069006d007000720065007300730069006f006e00200070007200e9007000720065007300730065002e0020004c0065007300200064006f00630075006d0065006e00740073002000500044004600200063007200e900e90073002000700065007500760065006e0074002000ea0074007200650020006f007500760065007200740073002000640061006e00730020004100630072006f006200610074002c002000610069006e00730069002000710075002700410064006f00620065002000520065006100640065007200200035002e0030002000650074002000760065007200730069006f006e007300200075006c007400e90072006900650075007200650073002e>
/GRE <FEFF03a703c103b703c303b903bc03bf03c003bf03b903ae03c303c403b5002003b103c503c403ad03c2002003c403b903c2002003c103c503b803bc03af03c303b503b903c2002003b303b903b1002003bd03b1002003b403b703bc03b903bf03c503c103b303ae03c303b503c403b5002003ad03b303b303c103b103c603b1002000410064006f006200650020005000440046002003c003bf03c5002003b503af03bd03b103b9002003ba03b103c42019002003b503be03bf03c703ae03bd002003ba03b103c403ac03bb03bb03b703bb03b1002003b303b903b1002003c003c103bf002d03b503ba03c403c503c003c903c403b903ba03ad03c2002003b503c103b303b103c303af03b503c2002003c503c803b703bb03ae03c2002003c003bf03b903cc03c403b703c403b103c2002e0020002003a403b10020005000440046002003ad03b303b303c103b103c603b1002003c003bf03c5002003ad03c703b503c403b5002003b403b703bc03b903bf03c503c103b303ae03c303b503b9002003bc03c003bf03c103bf03cd03bd002003bd03b1002003b103bd03bf03b903c703c403bf03cd03bd002003bc03b5002003c403bf0020004100630072006f006200610074002c002003c403bf002000410064006f00620065002000520065006100640065007200200035002e0030002003ba03b103b9002003bc03b503c403b103b303b503bd03ad03c303c403b503c103b503c2002003b503ba03b403cc03c303b503b903c2002e>
/HEB <FEFF05D405E905EA05DE05E905D5002005D105D405D205D305E805D505EA002005D005DC05D4002005DB05D305D9002005DC05D905E605D505E8002005DE05E105DE05DB05D9002000410064006F006200650020005000440046002005D405DE05D505EA05D005DE05D905DD002005DC05D405D305E405E105EA002005E705D305DD002D05D305E405D505E1002005D005D905DB05D505EA05D905EA002E002005DE05E105DE05DB05D90020005000440046002005E905E005D505E605E805D5002005E005D905EA05E005D905DD002005DC05E405EA05D905D705D4002005D105D005DE05E605E205D505EA0020004100630072006F006200610074002005D5002D00410064006F00620065002000520065006100640065007200200035002E0030002005D505D205E805E105D005D505EA002005DE05EA05E705D305DE05D505EA002005D905D505EA05E8002E05D005DE05D905DD002005DC002D005000440046002F0058002D0033002C002005E205D905D905E005D5002005D105DE05D305E805D905DA002005DC05DE05E905EA05DE05E9002005E905DC0020004100630072006F006200610074002E002005DE05E105DE05DB05D90020005000440046002005E905E005D505E605E805D5002005E005D905EA05E005D905DD002005DC05E405EA05D905D705D4002005D105D005DE05E605E205D505EA0020004100630072006F006200610074002005D5002D00410064006F00620065002000520065006100640065007200200035002E0030002005D505D205E805E105D005D505EA002005DE05EA05E705D305DE05D505EA002005D905D505EA05E8002E>
/HRV (Za stvaranje Adobe PDF dokumenata najpogodnijih za visokokvalitetni ispis prije tiskanja koristite ove postavke. Stvoreni PDF dokumenti mogu se otvoriti Acrobat i Adobe Reader 5.0 i kasnijim verzijama.)
/HUN <FEFF004b0069007600e1006c00f30020006d0069006e0151007300e9006701710020006e0079006f006d00640061006900200065006c0151006b00e90073007a00ed007401510020006e0079006f006d00740061007400e100730068006f007a0020006c006500670069006e006b00e1006200620020006d0065006700660065006c0065006c0151002000410064006f00620065002000500044004600200064006f006b0075006d0065006e00740075006d006f006b0061007400200065007a0065006b006b0065006c0020006100200062006500e1006c006c00ed007400e10073006f006b006b0061006c0020006b00e90073007a00ed0074006800650074002e0020002000410020006c00e90074007200650068006f007a006f00740074002000500044004600200064006f006b0075006d0065006e00740075006d006f006b00200061007a0020004100630072006f006200610074002000e9007300200061007a002000410064006f00620065002000520065006100640065007200200035002e0030002c0020007600610067007900200061007a002000610074007400f3006c0020006b00e9007301510062006200690020007600650072007a006900f3006b006b0061006c0020006e00790069007400680061007400f3006b0020006d00650067002e>
/ITA <FEFF005500740069006c0069007a007a006100720065002000710075006500730074006500200069006d0070006f007300740061007a0069006f006e00690020007000650072002000630072006500610072006500200064006f00630075006d0065006e00740069002000410064006f00620065002000500044004600200070006900f900200061006400610074007400690020006100200075006e00610020007000720065007300740061006d0070006100200064006900200061006c007400610020007100750061006c0069007400e0002e0020004900200064006f00630075006d0065006e007400690020005000440046002000630072006500610074006900200070006f00730073006f006e006f0020006500730073006500720065002000610070006500720074006900200063006f006e0020004100630072006f00620061007400200065002000410064006f00620065002000520065006100640065007200200035002e003000200065002000760065007200730069006f006e006900200073007500630063006500730073006900760065002e>
/JPN <FEFF9ad854c18cea306a30d730ea30d730ec30b951fa529b7528002000410064006f0062006500200050004400460020658766f8306e4f5c6210306b4f7f75283057307e305930023053306e8a2d5b9a30674f5c62103055308c305f0020005000440046002030d530a130a430eb306f3001004100630072006f0062006100740020304a30883073002000410064006f00620065002000520065006100640065007200200035002e003000204ee5964d3067958b304f30533068304c3067304d307e305930023053306e8a2d5b9a306b306f30d530a930f330c8306e57cb30818fbc307f304c5fc59808306730593002>
/KOR <FEFFc7740020c124c815c7440020c0acc6a9d558c5ec0020ace0d488c9c80020c2dcd5d80020c778c1c4c5d00020ac00c7a50020c801d569d55c002000410064006f0062006500200050004400460020bb38c11cb97c0020c791c131d569b2c8b2e4002e0020c774b807ac8c0020c791c131b41c00200050004400460020bb38c11cb2940020004100630072006f0062006100740020bc0f002000410064006f00620065002000520065006100640065007200200035002e00300020c774c0c1c5d0c11c0020c5f40020c2180020c788c2b5b2c8b2e4002e>
/LTH <FEFF004e006100750064006f006b0069007400650020016100690075006f007300200070006100720061006d006500740072007500730020006e006f0072011700640061006d00690020006b0075007200740069002000410064006f00620065002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b00750072006900650020006c0061006200690061007500730069006100690020007000720069007400610069006b007900740069002000610075006b01610074006f00730020006b006f006b007900620117007300200070006100720065006e006700740069006e00690061006d00200073007000610075007300640069006e0069006d00750069002e0020002000530075006b0075007200740069002000500044004600200064006f006b0075006d0065006e007400610069002000670061006c006900200062016b007400690020006100740069006400610072006f006d00690020004100630072006f006200610074002000690072002000410064006f00620065002000520065006100640065007200200035002e0030002000610072002000760117006c00650073006e0117006d00690073002000760065007200730069006a006f006d00690073002e>
/LVI <FEFF0049007a006d0061006e0074006f006a00690065007400200161006f00730020006900650073007400610074012b006a0075006d00750073002c0020006c0061006900200076006500690064006f00740075002000410064006f00620065002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b006100730020006900720020012b00700061016100690020007000690065006d01130072006f00740069002000610075006700730074006100730020006b00760061006c0069007401010074006500730020007000690072006d007300690065007300700069006501610061006e006100730020006400720075006b00610069002e00200049007a0076006500690064006f006a006900650074002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b006f002000760061007200200061007400760113007200740020006100720020004100630072006f00620061007400200075006e002000410064006f00620065002000520065006100640065007200200035002e0030002c0020006b0101002000610072012b00200074006f0020006a00610075006e0101006b0101006d002000760065007200730069006a0101006d002e>
/NLD (Gebruik deze instellingen om Adobe PDF-documenten te maken die zijn geoptimaliseerd voor prepress-afdrukken van hoge kwaliteit. De gemaakte PDF-documenten kunnen worden geopend met Acrobat en Adobe Reader 5.0 en hoger.)
/NOR <FEFF004200720075006b00200064006900730073006500200069006e006e007300740069006c006c0069006e00670065006e0065002000740069006c002000e50020006f0070007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740065007200200073006f006d00200065007200200062006500730074002000650067006e0065007400200066006f00720020006600f80072007400720079006b006b0073007500740073006b00720069006600740020006100760020006800f800790020006b00760061006c0069007400650074002e0020005000440046002d0064006f006b0075006d0065006e00740065006e00650020006b0061006e002000e50070006e00650073002000690020004100630072006f00620061007400200065006c006c00650072002000410064006f00620065002000520065006100640065007200200035002e003000200065006c006c00650072002000730065006e006500720065002e>
/POL <FEFF0055007300740061007700690065006e0069006100200064006f002000740077006f0072007a0065006e0069006100200064006f006b0075006d0065006e007400f300770020005000440046002000700072007a0065007a006e00610063007a006f006e00790063006800200064006f002000770079006400720075006b00f30077002000770020007700790073006f006b00690065006a0020006a0061006b006f015b00630069002e002000200044006f006b0075006d0065006e0074007900200050004400460020006d006f017c006e00610020006f007400770069006500720061010700200077002000700072006f006700720061006d006900650020004100630072006f00620061007400200069002000410064006f00620065002000520065006100640065007200200035002e0030002000690020006e006f00770073007a0079006d002e>
/PTB <FEFF005500740069006c0069007a006500200065007300730061007300200063006f006e00660069006700750072006100e700f50065007300200064006500200066006f0072006d00610020006100200063007200690061007200200064006f00630075006d0065006e0074006f0073002000410064006f0062006500200050004400460020006d00610069007300200061006400650071007500610064006f00730020007000610072006100200070007200e9002d0069006d0070007200650073007300f50065007300200064006500200061006c007400610020007100750061006c00690064006100640065002e0020004f007300200064006f00630075006d0065006e0074006f00730020005000440046002000630072006900610064006f007300200070006f00640065006d0020007300650072002000610062006500720074006f007300200063006f006d0020006f0020004100630072006f006200610074002000650020006f002000410064006f00620065002000520065006100640065007200200035002e0030002000650020007600650072007300f50065007300200070006f00730074006500720069006f007200650073002e>
/RUM <FEFF005500740069006c0069007a00610163006900200061006300650073007400650020007300650074010300720069002000700065006e007400720075002000610020006300720065006100200064006f00630075006d0065006e00740065002000410064006f006200650020005000440046002000610064006500630076006100740065002000700065006e0074007200750020007400690070010300720069007200650061002000700072006500700072006500730073002000640065002000630061006c006900740061007400650020007300750070006500720069006f006100720103002e002000200044006f00630075006d0065006e00740065006c00650020005000440046002000630072006500610074006500200070006f00740020006600690020006400650073006300680069007300650020006300750020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e00300020015f00690020007600650072007300690075006e0069006c006500200075006c0074006500720069006f006100720065002e>
/RUS <FEFF04180441043f043e043b044c04370443043904420435002004340430043d043d044b04350020043d0430044104420440043e0439043a043800200434043b044f00200441043e043704340430043d0438044f00200434043e043a0443043c0435043d0442043e0432002000410064006f006200650020005000440046002c0020043c0430043a04410438043c0430043b044c043d043e0020043f043e04340445043e0434044f04490438044500200434043b044f00200432044b0441043e043a043e043a0430044704350441044204320435043d043d043e0433043e00200434043e043f0435044704300442043d043e0433043e00200432044b0432043e04340430002e002000200421043e043704340430043d043d044b04350020005000440046002d0434043e043a0443043c0435043d0442044b0020043c043e0436043d043e0020043e0442043a0440044b043204300442044c002004410020043f043e043c043e0449044c044e0020004100630072006f00620061007400200438002000410064006f00620065002000520065006100640065007200200035002e00300020043800200431043e043b043504350020043f043e04370434043d043804450020043204350440044104380439002e>
/SKY <FEFF0054006900650074006f0020006e006100730074006100760065006e0069006100200070006f0075017e0069007400650020006e00610020007600790074007600e100720061006e0069006500200064006f006b0075006d0065006e0074006f0076002000410064006f006200650020005000440046002c0020006b0074006f007200e90020007300610020006e0061006a006c0065007001610069006500200068006f0064006900610020006e00610020006b00760061006c00690074006e00fa00200074006c0061010d00200061002000700072006500700072006500730073002e00200056007900740076006f00720065006e00e900200064006f006b0075006d0065006e007400790020005000440046002000620075006400650020006d006f017e006e00e90020006f00740076006f00720069016500200076002000700072006f006700720061006d006f006300680020004100630072006f00620061007400200061002000410064006f00620065002000520065006100640065007200200035002e0030002000610020006e006f0076016100ed00630068002e>
/SLV <FEFF005400650020006e006100730074006100760069007400760065002000750070006f0072006100620069007400650020007a00610020007500730074007600610072006a0061006e006a006500200064006f006b0075006d0065006e0074006f0076002000410064006f006200650020005000440046002c0020006b006900200073006f0020006e0061006a007000720069006d00650072006e0065006a016100690020007a00610020006b0061006b006f0076006f00730074006e006f0020007400690073006b0061006e006a00650020007300200070007200690070007200610076006f0020006e00610020007400690073006b002e00200020005500730074007600610072006a0065006e006500200064006f006b0075006d0065006e0074006500200050004400460020006a00650020006d006f0067006f010d00650020006f0064007000720065007400690020007a0020004100630072006f00620061007400200069006e002000410064006f00620065002000520065006100640065007200200035002e003000200069006e0020006e006f00760065006a01610069006d002e>
/SUO <FEFF004b00e40079007400e40020006e00e40069007400e4002000610073006500740075006b007300690061002c0020006b0075006e0020006c0075006f00740020006c00e400680069006e006e00e4002000760061006100740069007600610061006e0020007000610069006e006100740075006b00730065006e002000760061006c006d0069007300740065006c00750074007900f6006800f6006e00200073006f00700069007600690061002000410064006f0062006500200050004400460020002d0064006f006b0075006d0065006e007400740065006a0061002e0020004c0075006f0064007500740020005000440046002d0064006f006b0075006d0065006e00740069007400200076006f0069006400610061006e0020006100760061007400610020004100630072006f0062006100740069006c006c00610020006a0061002000410064006f00620065002000520065006100640065007200200035002e0030003a006c006c00610020006a006100200075007500640065006d006d0069006c006c0061002e>
/SVE <FEFF0041006e007600e4006e00640020006400650020006800e4007200200069006e0073007400e4006c006c006e0069006e006700610072006e00610020006f006d002000640075002000760069006c006c00200073006b006100700061002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400200073006f006d002000e400720020006c00e4006d0070006c0069006700610020006600f60072002000700072006500700072006500730073002d007500740073006b00720069006600740020006d006500640020006800f600670020006b00760061006c0069007400650074002e002000200053006b006100700061006400650020005000440046002d0064006f006b0075006d0065006e00740020006b0061006e002000f600700070006e00610073002000690020004100630072006f0062006100740020006f00630068002000410064006f00620065002000520065006100640065007200200035002e00300020006f00630068002000730065006e006100720065002e>
/TUR <FEFF005900fc006b00730065006b0020006b0061006c006900740065006c0069002000f6006e002000790061007a006401310072006d00610020006200610073006b013100730131006e006100200065006e0020006900790069002000750079006100620069006c006500630065006b002000410064006f006200650020005000440046002000620065006c00670065006c0065007200690020006f006c0075015f007400750072006d0061006b0020006900e70069006e00200062007500200061007900610072006c0061007201310020006b0075006c006c0061006e0131006e002e00200020004f006c0075015f0074007500720075006c0061006e0020005000440046002000620065006c00670065006c0065007200690020004100630072006f006200610074002000760065002000410064006f00620065002000520065006100640065007200200035002e003000200076006500200073006f006e0072006100730131006e00640061006b00690020007300fc007200fc006d006c00650072006c00650020006100e70131006c006100620069006c00690072002e>
/UKR <FEFF04120438043a043e0440043804410442043e043204430439044204350020044604560020043f043004400430043c043504420440043800200434043b044f0020044104420432043e04400435043d043d044f00200434043e043a0443043c0435043d044204560432002000410064006f006200650020005000440046002c0020044f043a04560020043d04300439043a04400430044904350020043f045604340445043e0434044f0442044c00200434043b044f0020043204380441043e043a043e044f043a04560441043d043e0433043e0020043f0435044004350434043404400443043a043e0432043e0433043e0020043404400443043a0443002e00200020042104420432043e04400435043d045600200434043e043a0443043c0435043d0442043800200050004400460020043c043e0436043d04300020043204560434043a0440043804420438002004430020004100630072006f006200610074002004420430002000410064006f00620065002000520065006100640065007200200035002e0030002004300431043e0020043f04560437043d04560448043e04570020043204350440044104560457002e>
/ENU (Use these settings to create Adobe PDF documents best suited for high-quality prepress printing. Created PDF documents can be opened with Acrobat and Adobe Reader 5.0 and later.)
>>
/Namespace [
(Adobe)
(Common)
(1.0)
]
/OtherNamespaces [
<<
/AsReaderSpreads false
/CropImagesToFrames true
/ErrorControl /WarnAndContinue
/FlattenerIgnoreSpreadOverrides false
/IncludeGuidesGrids false
/IncludeNonPrinting false
/IncludeSlug false
/Namespace [
(Adobe)
(InDesign)
(4.0)
]
/OmitPlacedBitmaps false
/OmitPlacedEPS false
/OmitPlacedPDF false
/SimulateOverprint /Legacy
>>
<<
/AddBleedMarks false
/AddColorBars false
/AddCropMarks false
/AddPageInfo false
/AddRegMarks false
/ConvertColors /ConvertToCMYK
/DestinationProfileName ()
/DestinationProfileSelector /DocumentCMYK
/Downsample16BitImages true
/FlattenerPreset <<
/PresetSelector /MediumResolution
>>
/FormElements false
/GenerateStructure false
/IncludeBookmarks false
/IncludeHyperlinks false
/IncludeInteractive false
/IncludeLayers false
/IncludeProfiles false
/MultimediaHandling /UseObjectSettings
/Namespace [
(Adobe)
(CreativeSuite)
(2.0)
]
/PDFXOutputIntentProfileSelector /DocumentCMYK
/PreserveEditing true
/UntaggedCMYKHandling /LeaveUntagged
/UntaggedRGBHandling /UseDocumentProfile
/UseDocumentBleed false
>>
]
>> setdistillerparams
<<
/HWResolution [2400 2400]
/PageSize [612.000 792.000]
>> setpagedevice
|