NT 
within 
when 
paper 
ection 
nodels 
ts, the 
which 
ay be 
ation. 
bering 
 num- 
KS Was 
les. In 
sults,’ 
ted to 
patho- 
ty and 
odetic 
order 
ctures 
can be 
iscrete 
o the 
t (see 
, have 
ion of 
nd, in 
hat is 
times 
mplete. 
well — 
ist, the 
proven 
ons are 
is con- 
Ct time 
ized as 
)00 un- 
g algo- 
try to 
ur (for 
identification errors are coped with pure statistical 
techniques like iterated reweighting. This approach 
sometimes leads to troublesome computation sessions 
and does not take into account that the error is of a 
structural nature and can be detected by structural 
means. This second aspect —structural analysis of 
networks— emerges in a natural way while investi- 
gating the pathologies mentioned above. 
2 BASIC TERMINOLOGY AND 
RESULTS 
In order to facilitate the understanding of the next 
sections some basic concepts from combinatorics are 
required. The concepts reviewed are graphs and their 
cycle structure, hypergraphs and matroids. Other 
more specific concepts will be introduced when re- 
quired. 
2.1 Graphs 
Let V be a finite non empty set and E C {{z,y} : 
x # y;x,y € V} a collection of unordered pairs of 
elements of V. (V, E) will be called a finite undirected 
graph with no loops and no multiple edges or, in our 
context, simply a graph. If G is a graph then it will be 
written G — (V(G), E(G)). The elements of V(G) are 
the vertices or nodes of G and the elements of E(G) — 
unordered pairs of V(G)— are the edges. The amount 
#(V (G)) is the order of the graph and #(E(G)) is the 
size. 
If {x1,x2} € E(G), then x1, x2 are adjacent ver- 
tices. Given a subset X of V, the adjacent set of X 
is defined as 
Adj(X) = {y € V(G) — X : 32 € X; {x,y} € E(G)}. 
Adj(z) will also be used for Adj({z}). 
The degree of a vertex x, d(r), is the number of 
vertices in Adj({z}), i.e. d(z) = #(Adj({x})). If 
d(x) = #(V(G)) — 1 then x is said to be a border 
vertez. 
The series z1 a1 2202 ... G4 124 (n 2 2) where 
irn.4.) COVy (mil: 6 E andoa > 
{xe, Xisr } is a path of length n — 1 which connects zi 
and z,. It is said, then, that the path contains the 
above vertices and edges and that it is a path through 
them. A path of length 0 is a series z1. A closed path 
is à path such that z1 — z4. À chain is a path with 
no repeated vertices. A cycle is a closed path with 
no repeated edges. A simple cycle is a closed path 
with no repeated vertices. Henceforth, if not other- 
wise stated, it will be assumed that when referring to 
cycle a simple cycle is meant. 
A graph is connected if there is a chain which con- 
nects each pair of vertices. 
615 
The distance de (z1, z2) —or simply d(x1, x2)— be- 
tween vertices zi and r2 of a connected graph G is 
the length of the shortest chain from x; to x». 
2.2 Graph  numberings and elimination 
graphs 
A numbering of a graph G = (V, E) is a one-to-one 
mapping p : {1,...,#(V)} — V. The graph G 
together with the numbering p is sometimes called 
an ordered graph and written as G, = (V,E,pD). 
In this paper, the equivalent definition p : V —s 
{1,...,#(V)} will also be used. 
For a given G,, the elimination graph is (G, EUF), 
where the new edges in F are the fill-ins; the fill-in 
factor is #(EU F)/#(E). Since the concept of fill-in 
is very well known in photogrammetry, only the path 
theorem [12] which characterizes them and which will 
be used in Section 4 as a definition is reviewed. 
The path theorem|12]: Let G be a graph and p a 
numbering of G. Let i » j, i — p^ !(a), j — p^ !(b). 
Then {a,b} is a fill-in if, and only if, there exists a 
path 
G (a, 2p, ) tp, ... Tp, {Tp,.,b}b 
in the graph G9, p,,...,p, « j; where p, — 
A (ta) 0 
Based on results derived from the above theo- 
rem [12|[p.277], a fast fill-in generation algorithm 
(running time: O(#(V) + #(E UF)) can be devised. 
2.3 Cycle bases 
Let G = (V, E) be a graph and p a one-to-one map p : 
{1,...,#(E)} — E; to each cycle c of G the element 
pc) = (u1,... , U#(2)) of 277 is associated, defined 
Bs l if p(i) is an edge of c, 
Ui = 
0 otherwise. 
Let c1,... , Ch be n cycles of G and their respectives 
pu(c1),-..,/ (Ch) as defined above. c,...,c, are said 
to be dependent if there is à non empty subset Q C 
{1,...,n} such that 
> u(ci) = 0, 
i€Q 
where, recall, the summation is taken in Z9. Other- 
wise they are called independent. ? 
A cycle basis of G is a set (c1,..., cx) of indepen- 
dent cycles such that any cycle c of G can be written 
  
ZUsually, it is also written SN eq Ci instead of the formally 
correct Y ed pci).