,BeF, 
subject 
by non- 
subclass 
blems of 
omplete 
n in NP 
me algo- 
hm that 
step. À 
an algo- 
ps which 
2LS 
discrete 
ion with 
'olved in 
ehensive 
ling dis- 
s in our 
n is the 
a graph 
a graph 
nnecting 
s are in- 
h G(N) 
f a block 
if N is 
ne prob- 
he net- 
A = 
ich that 
vertices 
rs related 
the three 
, also the 
alibration 
up. 
V(H). Then, consider the map € 
€: (L...,m) —  E(H) 
i ny E; 
where €(i) — E; if E; — (p(i1),...,p(i;)) and the 
only non zero elements of row i in A are iis 
«3 Qj, . 
€ may be non bijective. 
H does contain all structural information of the 
network, including the observations. The problem of 
finding an optimal sequence for loading the partial 
normal equations —if required— can be formulated 
in terms of finding a proper numbering for the hyper- 
edges of H. 
G(NE) can be obtained from H(NE) as follows 
H(NE)-9. H(NE) -. L(H(NEY), (1) 
where G(NE) = L(H(NE)*), L(H(NE)*) is the rep- 
resentative graph of H(NE)" and H(NE)' is the dual 
hypergraph of H(NE). 
Vil = wm, 5 {8,7 
graph, the dual hypergraph H* 
H* x (ey, 0m (Vi Va) 
is defined through the relation 
,Em}) is a hyper- 
e; € V; © v; € E; 
for 1€ í € m and 1 € j € n. It is apparent that 
(H*)* — H. 
The representative graph L(H) of H is a graph of 
order m -i.e., V(L(H)) — (z1,...,24]- defined with 
the equivalence 
Íriz; € E(L(H)) e Ei NE; z 9, 
fori«ij«m. 
In the above two definitions, for the sake of a sim- 
pler notation, the existence of a one-to-one correspon- 
dence between sets of same cardinality has been high- 
lighted with subindices. 
In transformation (1), step a is a discrete trans- 
pose, step f) is a discrete —symbolic— product of dis- 
crete matrices. The composition of them is a discrete 
transpose product. (There are algorithms available 
that given H (NE) and a numbering p of its vertices, 
directly generate the elimination graph of G,(NE).) 
H(NE) can be introduced as the network discrete 
model —for hystorical reasons one could call G(NE) 
the network [associated] graph— although it is an 
open question whether one should allow for multi- 
plicities in the edges of the hypergraph H(NE). If 
so, then the map in 1 would be one-to-one. 
A last observation is that network discrete mod- 
els provide the skeleton for the network abstract data 
617 
types to be used in the adjustment systems. More- 
over, since graphs, hypergraphs, lists and sets are ba- 
sic mathematical objects, the fundamental operations 
and algorithms on them can be borrowed from stan- 
dard discrete mathematical software packages. 
4 A REMARK ON CLASSICAL 
PHOTOGRAMMETRIC NETWORKS 
Graphs associated to photogrammetric blocks, for 
both bundle or independent model methods, are bi- 
partite. A graph G is called bipartite if V(G) can be 
partitioned into two subsets —parts— in a way that 
an edge always connects vertices of different parts. In 
the case of a bundle network, one part has as many 
vertices as points are in the network and the other 
part has a number of vertices that equals the number 
of images. 
n-partite graphs are defined in a similar way. For 
a given graph G, its chromatic number x(G) is the 
smallest n for which G is n-partite. In general, com- 
puting x(G) is NP-complete. Note that a bundle net- 
work with additional selfcalibration parameters can 
be associated to a tripartite graph. 
For photogrammetric blocks, in the frame of a 
general network adjustment program, the traditional 
steps of forming the reduced normal equations and 
numbering of their group unknowns, can be put in 
an abstract form as follows: 
e check the network graph for bi- or tripartiteness. 
If the answer is yes, then proceed and 
1. generate the two or three partitions, 
2. generate a partial elimination graph R, 
3. number the vertices of a suitable subgraph of R. 
Testing whether a graph is bipartite and generating 
the vertex parts is easy (the well known equivalence 
between bipartite graphs and graphs with no cycles 
of odd length must be used). For tripartite graphs 
the generation of the parts is more involved but it 
still can be done [3]|Chapter 3]. This solves step 1. 
For step 2, consider the following less restrictive 
definition of graph numbering than the one given in 
Section 2.2: any map p : V — {1,...,#(V)}. If p 
is taken as p(any point) — 1 and p (any image) — 2, 
then the elimination graph R generated by applying 
the path theorem to p corresponds to the graph of the 
intermediate symmetric matrix obtained after factor- 
ization of the point unknowns [3][Chapter 2]. 
For the last step, it suffices to extract the subgraph 
of R corresponding to the image unknowns and apply 
your favorite numbering algorithm to it.