cted sub- 
he graph 
graph — 
ir four N, 
rder 961 
-distance 
and Fig- 
: 961 and 
mplifica- 
ng edges 
represen- 
adjusted 
or, also, 
ent that 
etwork. 
sted dis- 
) is 6.88 
6 LD 3 
ler cases 
rings do 
to 4.67! 
yorithms 
ce of the 
e 1). Of 
ering al- 
[3]. 
1etworks 
t graphs 
re of the 
instance 
t correc- 
or edges 
hich de- 
he hybrid 
rithm, for 
well. 
To face those problems, rather than to establish 
brand new numbering algorithms, it seems wiser to 
develope network analysis tools for the detection and 
isolation of the perturbing edges as pursued in the 
following section. Once this is done, appropiate ac- 
tion can be taken before the actual numbering al- 
gorithms be applied to the unperturbed underlying 
graph. These tools are of interest even for conven- 
tional networks since [structural] gross errors, for in- 
stance point numbering errors, modify the network 
graph connectivity in a similar way as observations 
between distant parameters do. 
6 SOME DISCRETE ANALYSIS TOOLS 
The concepts developed in this section can be found 
in more detail in [3][Chapter 6]. They are here in- 
troduced from less to more difficult, starting with the 
almost trivial task of analysing the connectivity prop- 
agation. 
6.1 Superconnectivity 
For any x € V(G) consider the sequence 
do(z) di(z) ... d, (x), 
where d;(x) = #(L;), à € {0,...,r} and where Lo = 
{=}, IA == Adj(z) and Lj = Adj(L;_1) =— Lio for 
(22. 
À complete analysis of the sequences do(x) di () . . . 
d.(z) requires too big a computational effort. The 
computation of a restricted number of elements of 
the above sequences —the first elements provide the 
most relevant information—, however, is almost as 
helpful as the whole computation. This is specially 
true if the very pathological vertices like border ones 
are removed from the graph as soon as they are de- 
tected. 
6.2 Nonlocality 
Let G — (V,E) be a graph and e = {a,b} one of 
its edges such that #(F) » 3 and (V, E — (e]) is 
connected. The nonlocality of e, r(e) is defined as 
r(e) = d(v,E—{e}) (a, b). 
r(e) + 1 is, obviously, the length of the shortest cy- 
cle through the edge e. The concept of nonlocality, 
however, fits the intuitive idea of discrete distance 
between graph —network— vertices better and can 
be further extended by considering d(v,z_r)(a, b) for 
some subset F' of edges. 
Nonlocality has some limitations. For instance, for 
any edge e of P in Figure 3 it is r(e) — 6. This allows 
the detection and isolation of P. On the contrary for 
619 
  
Figure 3: A graph G with a 6-distance connected 
subgraph P. 
the graph of Figure 2 the detection of the perturbing 
subgraph is not possible through the analysis of non- 
locality since r(e) — 3 for any edge. This question is 
dealt with in the next section. 
6.3 Graph filtering 
First, the concept of n-distance connected subgraph 
is introduced. Let n be a positive integer, G = 
(V, E) a graph and P a connected subgraph such that 
#(V(P)) 2 2 and that d7(u,v) > n, Vu,v € V(P) 
where I = (V,E — E(P)). P is then called a n- 
distance subgraph of G. 
Figure 2 shows a 4-distance subgraph and Figure 3 
a 6-distance subgraph (P). 
A graph filter f is a graph operator; ie. given a 
graph G, f(G) is a subgraph of G. Throughout the 
section, B will stand for a minimal weight (length) 
cycle basis of G and q for an integer q > 3. 
Filter h9. h%(G) is the subgraph of G defined as 
h(G)= Gl({v € V(G) : Je; € B,w(c;) < a, 
vis a vertex of an edge of c; }). 
h%(G) may be nonconnected or the empty set. Based 
on the fact that (C,F) is a matroid on C (Sec- 
tion 2.5), it can be proven that h%(G) does not de- 
pend on the particular base B. 
Filter l3. In a similar way the subgraph [%(G) 
may be defined as 
IB(G)= G({ve V(G): Ic; € B,Uc;) > q, 
vis a vertex of an edge of c;}). 
Again I2 (G) may be nonconnected or even the empty 
set but in this case /$(G) is clearly dependent on B. 
In spite of this dependency, under certain conditions, 
some edges of G belong to /$(G) no matter which 
particular minimal basis is chosen. This property is 
useful in practice and formalized as follows: if P is a 
q-distance connected subgraph, for any minimal cycle 
basis B, it holds that P C I$ (G).