Информационные технологии проектирования электронных средств

- 37 - для которого ∆ F ( x z ,x l )>0. Если таких приращений несколько, то выбирается первый из них. 2. Отличие заключается в том, что для обмена выбирается такой элемент x s , для которого ∆ F ( x z ,x s )= j max ∆ F ( x z , x j ). Обозначим через Х множество вершин исходного графа G ( X , Е ) ; Х 1 – мно- жество вершин, вошедших в первый кусок G 1 ; 1 1 Х\Х Х = – множество вершин, оставшихся в  G 1 ;  G 1 = G \ G 1 , α ( x j ) − число связности j -й вершины ; α ( x j )= b ( x j )– a ( x j ), где b ( x j ) − число внешних связей вершины x j , определяемых количе- ством ребер, соединяющих вершину x j ∈ Х 1 c вершинами из множества Х 1 ; а ( x j ) − число внутренних связей вершины x j , определяемых количеством ребер, со- единяющих вершину x j с другими вершинами из Х 1 . Тогда справедливо следующее высказывание. Перестановка любых двух вершин x j ∈ Х 1 и х k ∈ Х 1 уменьшит связность между кусками G 1 и  G 1 , если для этих двух вершин выполняется соотношение: ∆α ( x j ,x k )= D ( x j )+ D ( x k ) − 2 с ( x j ,x k ) >0 , где с ( x j ,x k ) – количество связей между вершинами x j ∈ Х 1 и х k ∈ Х 1 , D ( x j )= b ( x j )– a ( x j ), D ( x к )= b ( x к )– a ( x к ) или ∆α ( х j ,х к )= [ b ( x j ) + b ( x k ) ] − [ a ( x j )+ a ( x k ) ] − 2 c ( x j ,x k ) >0 . Другими словами, перестановка двух вершин из разных кусков целесооб- разна в том случае, если сумма внешних связей этих вершин больше суммы их внутренних связей. Вопросы для самоконтроля 1. Приведите классификацию алгоритмов компоновки. 2. Приведите постановку задачи разрезания. 3. На чем основаны комбинаторные методы (поисковые).