|
, равны друг другу.
Доказательство двух последних лемм непосредственно следует из определений 
- диффузии и 
-диффузии и здесь не приводится.
Для любой весовой функции 
определим ее характеристику 
, называемую энергией функции, так, что
| (2) |
.Лемма 4. Пусть 
- весовая функция, а 
- результат применения диффузии к функции . В таком случае
| (3) |
.Доказательство. Для доказательства леммы достаточно доказать более сильное утверждение, что для произвольного 
энергия весовой функции при 
-диффузии не возрастает.
Пусть - весовая функция, полученная в результате применения -диффузии к функции . Для доказательства (3) достаточно доказать, что
| (4) |
,так как веса дужек 
, не вошедшие в левую и правую части неравенства (4), не изменились при -диффузии. Из определения -диффузии для весов и справедлива следующая цепочка:
|
,из которой следует, что
| (5) |
.Для левой части (5) справедливо очевидное неравенство
| (6) |
.Для правой части (5) справедливо равенство
| (7) |
,так как, согласно лемме 2, величина 
не зависит от 
. Из равенств (5), (7) и неравенства (6) следует (4). Лемма доказана.
Для заданной весовой функции и числа 
определено подмножество 
так, что
| (8) |
.Для заданной весовой функции определена величина 
как минимальное число 
, при котором подмножество содержит в себе согласованное подмножество дужек.
Лемма 5. Для любой весовой функции , такой, что 
, имеет место либо строгое неравенство
,
либо строгое включение
.
Доказательство. 1. Докажем, что если
| (9) |
то имеет место включение
| (10) |
,не обязательно строгое. Для этого достаточно доказать, что аналогичное свойство выполняется при -диффузии для произвольного . Выберем произвольно некоторое и зафиксируем его для последующего рассмотрения. Обозначим и весовые функции до и после -диффузии соответственно. Для доказательства включения (10) необходимо доказать, что для любой дужки , для которой выполняется равенство
| (11) |
,выполняется и равенство
| (12) |
.2. Импликация (11), (12), конечно же, справедлива для тех дужек , для которых 
и 
, так как по определению -диффузии для таких дужек
.
3. Рассмотрим дужку вида 
, 
, для которой выполняется (11), то есть
| (13) |
.Из этого равенства, конечно же, следует, что
|
.В силу лемм 2 и 3 из последнего равенства следует, что равенство
| (14) |
справедливо для всех 
.
Выберем метки 
, , так, что
|
.При этом, естественно, в качестве 
можно выбрать 
. Для меток, выбранных таким образом, выполняется равенство
| (15) |
.4. В ходе доказательства леммы 1 было установлено, что -диффузия является эквивалентным преобразованием весовой функции, и поэтому
| (16) |
.5. Условие (9) обозначает, что
| (17) |
.Из равенств (15), (16) и (17) следует равенство
|
.которое возможно тогда и только тогда, когда равенство
|
выполняется для всех , и в том числе для 
.
6. Таким образом доказано, что из равенства (13) следует равенство
|
,то есть доказано включение (10).
7. Докажем теперь, что из условий и 
следует строгое включение .
8. Диффузия 
есть суперпозиция 
-диффузий, 
, . При этом, в силу условия , по крайней мере для одной пары окажется, что существуют такие два объекта и 
, что
| (18) |
и
| (19) |
.Если бы такой пары не было, это бы обозначало, что множество 
дужек согласовано, что противоречит условию .
9. Для пары , удовлетворяющей условиям (18) и (19), определим метки 
, 
так, что
| (20) |
,и обозначим весовую функцию, полученную в результате -диффузии над функцией . В силу (19) для дужки 
окажется справедливым равенство
| (21) |
.10. Для меток , , выбранных в соответствии с (20), выполняется неравенство
|
,а в силу (18) для это неравенство выполняется строго
|
,и таким образом получаем
| (22) |
.11. Поскольку 
, то 
, то есть
| (23) |
.12. В силу леммы 1 -диффузия есть эквивалентное преобразование весовой функции, и поэтому
|
.и с учетом (22) и (23)
| (24) |
.13. В силу леммы 3 все слагаемые в левой части неравенства (24) равны друг другу. В силу леммы 2 и с учетом (20) равны друг другу все слагаемые и в правой части (24). Поэтому неравенство
|
,справедливо для всех , в том числе для , для которого справедливо равенство (см. (21)),
|
Лемма доказана.
Введем обозначение 
, 
так, что 
, а 
, 
. Пусть 
.
Лемма 6. Несогласованность весовой функции равна нулю тогда и только тогда, когда 
.
Доказательство. Если , то 
, так как в противном случае множество 
оказалось бы пустым, а это невозможно по определению (8). Достаточно очевидно, что если 
, то и 
, а следовательно 
для любого 
. Лемма доказана.
Определим метрику на множестве весовых функций так, что расстояние 
между функциями и 
равно
|
.Лемма 7. Энергия есть непрерывная функция весов .
Доказательство. Лемму доказывает следующая цепочка равенств и неравенств.
|
.Лемма доказана.
Лемма 7. Несогласованность есть непрерывная функция весов .
Доказательство. 1. Пусть и - две весовые функции, такие, что 
, и следовательно,
| (25) |
, 
, 
, 
.По определению несогласованности весовой функции множество
|
.содержит в себе согласованное подмножество дужек.
2. Из неравенства (25) следуют неравенства
| (26) |
, Из этих же неравенств следует, что
| (25) |
, 3. Из неравенств (26), (27) следует, что для любой дужки, для которой выполняется неравенство
,
выполняется неравенство
,
и, таким образом, 
.
4. Поскольку множество 
содержит в себе согласованное подмножество дужек, то множество 
также содержит в себе это же согласованное подмножество. Поэтому
| (28) |
.5. Точно так же, как было доказано неравенство (28), доказывается, что
| (29) |
.Из неравенств (28) и (29) следует, что
|
.Лемма доказана.
Лемма 9. Веса являются непрерывной функцией весов .
Доказательство. Поскольку диффузия есть последовательность конечного множества -диффузий, для доказательства леммы достаточно доказать непрерывность -диффузии.
1. Пусть 
и 
- весовые функции, полученные в результате -диффузии, примененной к функциям 
и 
соответственно, таким, что
| (30) |
, 
.2. Пусть
| (31) |
,
| (32) |
, Из (30) следует, что
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 |
