Другие предметы \ Основы теории творческой деятельности

Методы синтеза технических решений, страница 21


м

мощью коэффициентов   pi?   где i = Z + 1, Af, 23  Pi = 1, и неко-торого числа г:

м

, $Z+2> • • • , «м ) 6 CM-l

(4.12)

Будем говорить, что комбинация D e rt является рациональ­ной относительно A d См, если для всех х ее D П К G (ж) С А.

Техническое решение, соответствующее рациональной относи­тельно A d cm комбинации, будем называть рациональным.

Постановка задачи поиска рациональных комбинаций. Пусть имеется прадерево Т (X, [/), отображение G: К ->- См и замкну­тое подмножество А с См. Необходимо найти множество Дт всех рациональных комбинаций, т. е. для любого D ЕЕ rt должно выполняться условие: G (D f] К) d A.

Очевидно, что задача не имеет решения в случае G (К) (~]А — ф.

Условие существования решения задачи поиска рациональных комбинаций. Пусть йГсц К — множество вершин, такое, что G (К) f] -4 = 0- Построим множество X d X по следующим правилам:

77"    t                   ~\7" .                                                                                                                                                                                                                                                                                                                                      / /      л  f) \

аса,                                                                                      (4.13)

F (х) ф ф и F (х)

х

г=^яе J;                                   (4.14)

фф=$х^ X.(4.15)

Лемма   1.    Для   любого   Z) е #т # ЕЕ Z) Г) ^4^=^ 3s (=

е f (х) п я П х.

Доказательство. F (х) Ф 0, так как х {£ К. Возможны два случая.

1.  х ЕИ Хг. Тогда по (4.4] F (х) d D и по построению X (4.15)
следует,  что  F (х) (~] D р) X ф ф.

2.  х е Х^ Тогда по (4.5) существует se F (x) f| £),  но по
построению  X (4.14) F (х) d Z.  Следовательно 5 е X.

Лемма доказана.  Из леммы 1 легко получить

Следствие. Если s ЕЕ D f] JC \ К, то существует путь из s в одну из висячих вершин, проходящий через вершины из множе­ства D f] }[.

vj. ем/м/а &. lj j    .л.   / • сэ \ / a/ f ] j\.   /  ^^.

Доказательство. Пусть se D П ^- Если s ^ К, то по (4.13) s ЕЕ ^Г. Если 5 QE Я", то по следствию леммы 1 существует ж е ЗГ П ^ р| К, т. е. # е D П .ЙГ. Обратное утверждение оче­видно. Лемма доказана.

Условие существования решения задачи поиска рациональных комбинаций формулируется теоремой 1.

Теорема  1.   х1 §£ Ж 4Ф rt (А) =^= ф.

Доказательство. Пусть хг ф, X. Покажем, что в этом случае можно построить комбинацию D такую, что D f] X = ф. Рассмот-

Скачать файл