A 
           
  
  
s 
  
       
SHARE 
IS 
ds XIN NN 
  
  
uf. Ne 134 
  
  
  
  
  
di 
  
  
  
  
186 —— 160—— 461 —— — 
                     
    
               
NK 
      
es 
NISI SERRA = 
  
  
  
    
  
  
  
  
  
NNN RERSS 
Be 
DNA Vi 
NIE 
  
  
               
  
  
  
  
    
  
  
  
  
INI Yl EL. 
€ M eT 
  
  
  
        
  
Figure 2. The graph obtained applying the definition 1.1 
The following table summarizes the 
differences, in terms of graph dimensions, 
between the classical and the proposed 
graph. 
classical proposed 
V 1141 231 
E 12500 458 
The value of |E| of the classic method is 
approximated; however, comparing the 
reported values, the difference of the 
costs for a procedure that handles graph 
with 458 edges instead of 12500 and 231 
nodes instead of 1141 seems evident. 
1.3 Numbering nodes and edges 
The way for numbering edges is synthetized 
in the following procedure which assumes 
that nodes were previously ordered in the 
same way. 
procedure E 
num=1 
for i=1 to n 
let ny be the node so thatV(ny)-i 
let n b be the number 
of brothers of node ny 
for j=1 to n b 
let n4 be jth 
brother of ny 
if( not used( (nj,nj) ) ) 
then 
E( (nj; n4) ) = num 
(ni,n4) = used 
num = num+1l 
endif 
endfor 
endfor 
endprocedure 
The edges are numbered using a visit of 
the graph based on nodes order and 
labeling all edges not yet numbered; this 
operation is repeated for all the edges of 
the node n, and for all nodes of the set 
V. As every edge (n,;,nj) is considered 
twice, during the visit of the node n, and 
of the node n,, it is necessary to label 
the edge as  'used!' by the function 
'used()' when it is examined the first 
time. The effect of the procedure E is to 
create in the matrix A a low outline under 
which all elements are zero. This property 
is due to two facts: during the visit of 
the node 'i' all no labeled edges connect 
n; with the brothers n, whose indices '!j' 
are greater then 'i', and, futhermore, the 
no null coefficients of n, (i.e. the 
coefficients of the variables associated 
to n,) are always at the right side of 
those of n;., and at the left side of 
those of n,,, (because the variables 
reflect the order of the nodes). In terms 
of matrix, the equations associated with 
the | edge (n,,n3) put the not null 
coefficients of ns always at the right 
side of those of nj. 
Once the numbering procedure for the edges 
is fixed, the problem is transferred to 
the nodes. This will be solved in two 
parts consisting of: 
1) building a partition of the set V of 
nodes by three steps which determine: 
- a partition of V into (K,,K,,...,K,, 1) 
- a partition of I into (KC;;...KC;10g(r)) 
- an arrangement of the last partition. 
2) Numbering the nodes following the 
criterion synthetized by the next 
procedure based on the partition of the 
first step. 
procedure V 
num = 1 
for i=1 to r 
for  j-1 to | Ki | 
let nj be the jth node of Kj 
V( nj ) » num 
num = num +1 
endfor 
endfor 
for j=1 to log» r 
for i=1 to I 
for h=1 
let np be ERS nt 
node of KCi,j 
V( ng ) 7 num 
num = num +1 
endfor 
endfor 
endfor 
endprocedure 
Jxcy, 5 
104 
The 
orde 
  
The 
1.2 
isn! 
belc 
proc 
ther 
COLI 
unde 
coel 
rig! 
  
SO 
the