F\C 1234567890123456789012345678901
01 qM. T3. di. s. T1: Frs +
On ES «LL
03. TE xk, KL Uo,
04 .......….…........... NL SK KL VN
Sr A ca Ta LIIS EM
06. serve een nee mem ca xx, 4,
07 +... or +... dotes +. kk +
08 ' En *k, , Kk, ok,
00 ......……...... kk, , ok, kk, ,, k
40 o is KK, e.
11: 1... uel ® ek
12:50 0500 SE US, kk, KK, Lk
435: 4.5.5 we. mes. LLLI kt
14 sical ain dk, KK, ok
1B chu a ALL RM We
16 ines deo EUR, oes eene mies
17. ........ MMM We loro
48 3: doe, oH, Nk, LR,
19 — t..... x Me ok bk, ok LL
20.5. lem rore ik EV RII DKL...
21 we. URL NN Ll Hs ilar
22 NME MS niue
23 an Me en tee ea de +
24 ut de, de de, Lk, LL,
25 M ene d.k ak oce Lo KR s +
26 Ne Ra CNRC 10 Ne a aa a 0e au 0
27 Q«gk. Ask IL EEE aT
28 Boke iM ae we is tetris
29 Noa 0 1 Re see ue eur eee note i
30 «oH, HE Preiser ec 00e 0 ea»
31 +, A, LP, 1... T rne +
Figure 1: A cut subset for SQ 31 LD 6 (automated
nested dissection).
In general, all the different policies of dealing with
the “sorting of unknowns” in photogrammetric blocks
can be reduced to numbering alternatives of bipartite
graphs. Conversely, the extremely efficient methods
devised by photogrammetrists for their blocks over
the past two decades can be transferred to other
sparse gaussian elimination problems in other fields
where bipartite matrix graphs appear.
5 TROUBLESOME ASPECTS OF
HYBRID NETWORKS
Compared to classical networks, hybrid networks
may be troublesome because their local and regular
connectivity structure is lost. In order to illustrate
this statement, an example (Figure 1) will be given
before generalizing.
Figure 1 depicts a cut subset generated in the first
step of a nested dissection graph numbering algorithm
for arbitrary networks [8]. 4 The elements of the cut
4The nested dissection algorithm has been selected since it
618
Figure 2: A graph with a 4-distance connected sub-
graph.
subset are marked with the character *. The graph
—SQ 31 LD 6—is based on a regular grid graph —
SQ 31— whose vertices are connected to their four N,
E, S and W neighbors. Thus, SQ 31 is of order 961
and size 1860. SQ 31 LD 6 is SQ 31 plus a 6-distance
connected subgraph LD 6 (see Section 6.3 and Fig-
ure 2 with a SQ 13 LD 4 graph); it is of order 961 and
size 1920. In other words, SQ 31 LD 6 is a simplifica-
tion of a regular graph perturbed with the long edges
of LD 6. The simplification aims at being represen-
tative of a photogrammetric block which is adjusted
together with the terrestrial control network or, also,
of a conventional geodetic network readjustment that
brings together a main and a densification network.
The fill-in factor obtained after applying nested dis-
section to SQ 31 is 4.67; for SQ 31 LD 6 is 6.88
and for a graph of the type SQ 31 LD 6 LD 3
is 9.66 [3][Chapter 5]. Note that for either cases
SQ 31 LD 6 and SQ 31 LD 6 LD 3, numberings do
exist which lead to fill-in factors very close to 4.67!
The problem behind is the inability of the algorithms
to produce a clean cut subset in the presence of the
perturbing subgraphs LD 6 and LD 3 (Figure 1). Of
course, this depends on the particular numbering al-
gorithm (see [11]); this point is discussed in [3].
In [3], more cases of hybrid troublesome networks
are analysed. In general, it can be stated that graphs
of hybrid networks have a dominant structure of the
classical type plus some perturbing edges; for instance
in aerial triangulation, edges induced by drift correc-
tion parameters if aerial GPS control is used or edges
induced by the terrestrial control network which de-
stroy bipartiteness.
is the algorithm to be used in large problems [11]. If the hybrid
network is medium sized or small any sequential algorithm, for
instance the banker’s [15], will do the job reasonably well.
6.2
Let
its
COD
r(e
cle
how
bet:
be 1
som
any
the
