One-dimensional Gromov minimal filling 1 1 A.O. Ivanov and A.A. Tuzhilin 0 2 January 13, 2011 n a J 2 Abstract 1 The present paper opens a new branch in the theory of variational problems with branching extremals, the investigation of one-dimensional ] G minimalfillingsoffinitepseudo-metricspaces. Ontheonehand,thisprob- M lem isaone-dimensional version ofageneralization ofGromov’sminimal fillingsproblemtothecaseofstratifiedmanifolds(thefillinginourcaseis . aweightedgraph). Ontheotherhand,thisproblemisinterestinginitself h t and also can be considered as a generalization of another classical prob- a lem,namely,theSteinerproblemontheconstructionofashortestnetwork m joiningagivensetofterminals. Besidesthestatementoftheproblem,we [ discussseveralpropertiesoftheminimalfillings,describeminimalfillings of additive spaces, and state several conjectures. We also include some 2 announcementsconcerning thevery recent resultsobtained in ourgroup, v including a formula calculating the weight of the minimal filling for an 6 0 arbitrary finite pseudo-metric space and the concept of pseudo-additive 1 space which generalizes the classical concept of additive space. We hope 0 thatthetheoryofone-dimensionalminimalfillingsrefreshestheinterestin . theSteinerproblemandgivesanopportunitytosolveseverallongstand- 1 ingproblems,suchasthecalculationoftheSteinerratio,inparticularthe 0 verification of the Gilbert–Pollack conjecture on the Steiner ratio of the 1 1 Euclidean plane. : Bibliography: 33 items. v i X r Introduction a The problem considered in this paper appears as a result of a synthesis of two classicalproblems: theSteinerproblemontheshortestnetworks,andGromov’s problem on minimal fillings. Recall briefly the history of these questions. The Steiner problem is a problem on optimal connection of a finite set of points of a metric space. Apparently, the first problems of that type appeared in works of P. Fermat, who stated the question on finding the location of a point in the plane, such that the sum of the distances from it to the vertices of agiventriangleisminimal. Ittook afew centuriestoobtainacomplete answer (Torricelli,Simpson,etc.,seedetailsin[2]),whichdemonstratesthatjoiningthe points in the plane it might be profitable to add an additional point-fork. The 1 Introduction. 2 importance of such additional points was quite clear to C. F. Gauss discussing in his letters to Schuhmacher the construction of the shortest road network joining famous German cities Hamburg,Bremen, Hannowerand Braunschweig. In 1934 Jarnik and K¨ossler [3] stated the general problem which is now known as Classical Steiner Problem. In fact, their problem generalizes the problems of Fermat and Gauss on the shortest connection to the case of an arbitrary finite set of points in the plane. As concerns Steiner, he works with another generalizationofthe Fermatproblem: tofindapointinthe spacesuchthatthe sumofthedistancesfromittothegivenonesisminimal. Noticethatthepriority misunderstandingappears due to popular book of Courantand Robbins “What isMathematics?” [4],whereFermatproblemis referredasSteiner problem,and the Jarnik and K¨ossler problem is called just a generalization of the Steiner problem. There are a lot of publications devoted to the classicalSteiner problem and its numerous generalizations, for example, to the cases of normed spaces, Rie- mannian manifolds, and more general metric spaces, say, spaces of words. An interestedreader could find a review in [2]. Another surge of interest in Steiner problem is connected to Gilbert–Pollack Conjecture [1] on the Steiner ratio of Euclidean plane. Numerous attempts to prove it have failed. The best known attemptbelongstoDuandHwang[5],butitturnsoutthattheirreasoningcon- tainsseriousgaps,see[6],[2],[7],[8],[9]. IdeasofDuandHwangwereadvertised in the stage of announcing publications [13] that has led to popularization of thewrongconstruction. Severalpapersappeared(forexample,[14],[15])where the ideas of Du and Hwang were adopted to the case under consideration,and, asaresult,someunfoundedconclusionsgotthe statusoftheorems. Noticethat the validity of Gilbert–Pollack conjecture itself seems undoubted, therefore at- tempts to prove it appear again and again. In particular, numerous authors, including the authors of the present paper, tried to improve the construction of Du and Hwang, but did not succeed. It might make sense to search for a completelydifferentapproachto the problem. The minimalfillingsdiscussedin the present paper could be a base for such an approach. The concept of a minimal filling appeared in papers of Gromov [16] in the following form. Let M be a smooth closed manifold endowed with a distance function ρ. Consider all possible films W spanning M, i.e. compact manifolds withthe boundaryM. ConsideronW adistancefunction dnon-decreasingthe distancesbetweenthe pointsfromM. Suchametricspace =(W,d)iscalled W by a filling of the metric space = (M,ρ). The Gromov Problem consists in M describing the infimum of the volumes of the fillings and in searching for the spaces where this infimum is achieved and which are called minimal fillings. W An interest in minimal fillings is inspired, first of all, by the fact that many classical geometrical inequalities can be stated in terms of the fillings; see de- tails and exact references in the monograph [18] and also in the dissertation of S. V. Ivanov [19]. For example, the Bezikovich inequality, which says that the volumeofaRiemanniancube is greaterthanorequalto the productofthedis- tances between its opposite faces, follows from the fact that the standard cube in the Euclidean space is the minimal filling of its boundary. Another example Introduction. 3 is the Pu inequality giving a lower estimate for the length of the shortest non- contractible loop on the projective plane. This inequality follows from the fact thatthestandardhalf-sphereisaminimalfillingofits boundarycircleendowed with the intrinsic metric. Notice also that minimal fillings possess numerous applications in dynamic systems theory, asymptotic geometry, mathematical physics, etc. In the scope of Steiner problem, it is natural to consider M as a finite metricspace. Thenthepossiblefillingsaremetricspaceshavingthestructureof one-dimensional stratified manifolds which can be considered as edge-weighted graphswithnon-negativeweightfunction. Thisleadstothefollowingparticular case of generalized Gromov problem. Let M be an arbitrary finite set, and G=(V,E) be a connected graph. We say,that G joins M, if M V. Now, let =(M,ρ) be a finite pseudo-metric ⊂ M space(distancesbetweenthedistinctpointscanbeequaltozero),G=(V,E)be a connected graph joining M, and ω: E R is a mapping into non-negative + → numbers, which is usually referred as a weight function and which generates a weighted graph = (G,ω). The function ω generates on V the pseudo-metric G d , namely, the distance between the vertices of the graph is defined as the ω G leastpossibleweightofthepathin joiningthesevertices. Ifforanytwopoints G pandqfromM theinequalityρ(p,q) d (p,q)isvalid,thentheweightedgraph ω ≤ is called by a filing of the space , and the graph G is referred as the type G M of this filing. The value mf( )=infω( ), where infimum is takenover all the M G filings of the space is called by the weight of minimal filling, and a filling G M such that ω( )=mf( ) is called by a minimal filling. The main problem is G G M to learn how to calculate mf( ) and how to describe minimal fillings. M Notice that stratified manifolds have appeared naturally in geometric prob- lems; see for example [20], [21], [23], and in such applications as quantum physics [24], [22]. Letusdescribebrieflythecontentandthemainresultsofthepaper. InPre- liminaries we introduce the main objects of our investigation and discuss some relations between them. In general these objects may have very complicated topologies, however, one can essentially simplify the structure without loss of the sense of the problem. Section 2, Reduction to trees, is devoted to such simplifications. It turns out that in the case of shortest networks and minimal fillings one can consider only trees without interior vertices of degree 2; more- over,ifwealowthedegenerateedges(theedgesofzeroweightorlength)thenit issufficienttouseonlybinarytrees,i.e. thetreeswithverticesofdegree1and3 only,seeTheorem2.1. Section3,Minimalrealization,showsthateachminimal fillingcanbe representedasashortesttreewithsomespecialboundaryinsome special metric space. Namely, see Corollaries 3.2 and 3.3, if = (M,ρ) is a M finite pseudo-metric space consisting of n points, then the Kuratowski isomet- rical embedding ϕ : M ℓn can be extended to an isometrical embedding M → ∞ of a minimal (parametric) filling = (G,ω), such that the image ϕ (G) is a M G shortest tree (a minimal parametric tree) joining the boundary ϕ (M) ℓn . M ⊂ ∞ In Section 4 we discuss the relations between the concepts of minimal filling, shortest tree, and minimal spanning tree. It is shown that the weight of mini- Introduction. 4 malfilling canbe foundasinfimumofthelengths ofminimalspanningtreesfor so-calledextensionsofthe initialfinite metricspace,seeCorollaries4.2and4.3. In Section 5 we show that each minimal parametric filling is a solution to a linear programmingproblem. Using this idea, we prove that for any finite met- ric space the set of all its minimal parametric fillings of a fixed topology G is a non-empty convex compact in the configuration space of all weighted trees (G,ω), see Assertion 5.1. Further, in Section 6 the concept of an exact path in a filling is introduced. By definition of filling, for any two points p and q of a finite metric space = M (M,ρ) and any its filling = (G,ω), the inequality ω(γ ) ρ(p,q) is valid, pq G ≥ whereγ is the pathin Gjoining p andq. Sucha boundary path γ is saidto pq pq be exact, if ω(γ )= ρ(p,q), and a path (an edge, a vertex) is said to be exact pq if it is contained in an exact boundary path. Section 6 describes the structure of the set of exact paths in minimal (parametric) fillings. In the subsequent sections this technique gets severalapplications. Firstsuch applicationappears inSection7. Foranycyclicorderπ: M M onM wedefinethecorresponding → half-perimeter p( ,π) of the pseudo-metric space =(M,ρ) as follows: M M 1 p( ,π)= ρ p,π(p) . M 2 p∈M X (cid:0) (cid:1) Let G be a tree joining M. A cyclic order is called a tour around G, if it corresponds to an Euler tour of the doubling of G. Then, see Corollary7.1, for any filling = (G,ω) of a finite pseudo-metric space = (M,ρ), we prove G M that ω(G) max p( ,π), ≥π∈O(G) M where (G) stands for the set of all the tours around G. Hence, if the equality O ω(G)= max p( ,π) π∈O(G) M holds, then is a minimal parametric filling, and G mpf( ,G)= max p( ,π). ( ) M π∈O(G) M † We prove,see Assertion7.3, that the tour π where this maximum is achievedis exact,i.e.,theboundarypathsjoiningthepointsof consecutivewithrespect M to π, are exact. Vice versa, if a tour π around G is exact, then = (G,ω) G is a minimal parametric filling and the equality holds. But it is not difficult to construct an example of a minimal parametric filling with degenerate non- exact edges and without exact tours. Moreover, there exist non-degenerate minimal parametric fillings which do not possess exact tours, see Example of Z. Ovsjannikov in Section 7. Hence, Formula ( ) is not valid in general case. † However,theminimalparametricfillingsintheaboveexamplesarenotminimal fillings, and the authors conjectured, see Conjecture 7.1, that each minimal Introduction. 5 filling mustpossessanexacttour and,moreover,see Conjecture 7.3,the weight of minimal filling can be calculated by the next formula: mf( )=min max p( ,π). ( ) M G π∈O(G) M ‡ Recent results of our group, see [10], [11], [12], and Sections 8 and 9, show thatsometimesitisusefulltoallowtheweightfunctionofafillingtotakenega- tivevalues. Thecorrespondingobjectsdefinedin[10]arereferredasgeneralized fillings. It turns out, that among minimal generalized fillings of an arbitrary pseudo-metric space there exists a minimal filling, see Theorem 8.1. Therefore one can calculate the weight of minimal generalized filling instead of ordinary minimal filling. Investigating the generalized fillings, A. Eremin has found out that Conjectures 7.1 and 7.3 are not valid, but Formula ( ) can be turned to a ‡ trueformula,seeTheorem8.2,by meansofthe generalizedfillingsandthe con- cept of a multi-tour introduced by Eremin in [11]. A multi-tour of multiplicity k arounda tree G joining M canbe defined as a setofboundary paths forming an Euler tour in the 2k-plication of G (that is, the multigraph obtained from G by taking 2k copies of each its edge). The half-perimeter of a multi-tour is defined as the sum of the corresponding kn distances divided by 2k. Eremin proved that even Formula ( ) becomes true providing its left-hand part means † the weight of minimal parametric generalized filling, and the maximum in the right-hand part is taken over all multi-tours around G. Section9isdevotedtotheadditivespacesthatappearinmanyapplications. Recall that a pseudo-metric space = (M,ρ) is additive, if there exists a M weighted tree = (G,ω) joining M, such that d = ρ. In this case the tree ω G G is said to be generating. A well-known description of additive spaces is given in terms of so-called 4-points rule: the space is additive, if and only if for any four points p , p , p , p , the values ρ(p ,p )+ρ(p ,p ), ρ(p ,p )+ρ(p ,p ), i j k l i j k l i k j l ρ(p ,p )+ρ(p ,p ) are the lengths of sides of an isosceles triangle whose base i l j k does not exceed its other sides. Effective algorithms restoringa generatingtree are well-known also. For additive spaces we obtain a complete description of minimalfilling,seeTheorem9.1,namely,weshowthatthesetofminimalfillings of an additive space coincides with the set of its generating trees. Moreover, since a non-degenerate generating tree of an additive space is unique, then a non-degenerate minimal filling of an additive space is unique as well, see Corollary 9.4. Further, the half-perimeter of a pseudo-metric space =(M,ρ) is defined M as the value p( ) = min p( ,σ), where minimum is taken over all cyclic σ M M orders on M. For an additive space, the weight of its minimal filling is equal to the half-perimeter of the space and is also equal to the half-perimeter of the minimal filling with respect to each its tour, see Corollary 9.5. Moreover, O. Rubleva shows, see [32] and Assertion 9.4, that a pseudo-metric space is additive, if and only if the weight of its minimal filling is equal to the half- perimeter of the space. Since all the half-perimeters corresponding to a minimal filling of an ad- ditive space are the same, the authors stated the problem to describe all the Introduction. 6 spaces =(M,ρ) suchthat all the half-perimeters correspondingto the tours M around some tree joining M are the same. The complete answer is obtained by Z. Ovsjannikov [12]. He shows that the distance function of such a space = (M,ρ) is generated by a weighted tree with possibly negative weights of M someedges(suchtreeis alsosaidto be generating). Z.Ovsjannikovsuggeststo call such spaces pseudo-additive and shows that each such space possesses the aboveproperty. Similarly to additive spaces,the pseudo-additive spacescan be described in terms of so-calledweak 4-points rule: the space is pseudo-additive, if and only if for any four points p , p , p , p , the values ρ(p ,p )+ρ(p ,p ), i j k l i j k l ρ(p ,p )+ρ(p ,p ), ρ(p ,p )+ρ(p ,p ) are the lengths of sides of an isosceles i k j l i l j k triangle, see [12]. There exist effective algorithms restoring a generating tree, similar to classical ones. In Section 10 we consider families of pseudo-metric spaces referred as rays. Themultiplicative ray generatedbyapseudo-metricspace =(M,ρ)consists M of all the spaces of the form (M,λρ), λ 0. The additive ray generated by ≥ =(M,ρ)consistsofallthespacesoftheform(M,ρ+a),a a ,wherea M M M ≥ is a non-positive constant depending on . Theorem 10.1 describes minimal M fillingsoftheelementsoftheraysintermsofminimalfillingsoftheinitialspace. Inparticular,itisshownthatallthe spacesfromthe family (M,λρ+a),λ>0, a>λa , have the same set of types of minimal fillings. M In Section 11 we consider finite pseudo-metric spaces, all whose non-zero distances are linearly independent over the field Q of rational numbers. We call such spaces incommensurable. It is shown that any minimal filling of such space consisting of more than 3 points can not be “very degenerate”, namely, it must contain a non-degenerate interior edge. Moreover,boundary edges of any minimalfilling ofanincommensurablemetric spacearealsonon-degenerate(see Section 6). InSection12wegiveseveralexamplesofminimalfillingfinding. Inparticu- lar,itcontainscompleteanswersforthree-pointsandfour-pointspseudo-metric spaces,for any regularsimplex (a metric space with constantnon-zerodistance function), etc. Section 13 is inspired by Steiner ratio investigations,see above. Recall that the Steiner ratio of a finite subset M ofa metric space =(X,ρ)is defined as X smt(M,ρ) sr(M)= , mst(M,ρ) where mst(M,ρ) and smt(M,ρ) stand for the lengths of minimal spanning tree and Steiner minimal tree of M X, respectively. Then the Steiner ratio sr ⊂ X of the metric space and the degree n Steiner ratio sr of the space can n X X X be defined as follows sr =inf sr(M):M X, M n , sr( )= inf sr . n n X ⊂ | |≤ X n≥2 X (cid:8) (cid:9) We suggest to consider the values mf(M,ρ) mf(M,ρ) sgr(M)= , ssr(M)= , mst(M,ρ) smt(M,ρ) 1. Preliminaries. 7 which we call the Steiner–Gromov ratio and the Steiner subratio of M X, ⊂ respectively. Similarly to Steiner ratio case, one can define the values sgr , nX sgr , ssr , and ssr . We hope that the calculation of these values can be n X X X simplerthantheoneofclassicalSteinerratio,anthattherearesomeconnections between the three values sgr , ssr , and sr . Section 13 contains several X X X preliminaryresultsconcerningthe ratios. Itis shownthat1/2 sgr( ) 1for ≤ X ≤ anypseudo-metricspaceandthereexistsametricspacewhoseSteiner–Gromov ratio equals 1/2. Also it is shown, that if a pseudo-metric space contains an X equilateraltriangle,thensgr =3/4. FortheSteinersubratio,itisshownthat 3X ssr (Rn) = √3/2 and ssr (R2) = √3/2, see E. Filonenko [33]. We conjecture, 3 4 seeConjecture13.1,thatthe Steiner subratioofthe Euclideanplane isequalto √3/2 and is achieved at the vertex set of an equilateral triangle. The authors use the opportunity to express their heartfelt gratitude to A.T.Fomenkoforhislongstandingattentiontoourwork,toN.P.Strelkovafor attentivereadingofthemanuscriptandseveralusefulremarks,toF.Morganfor many remarks improved essentially the quality of our English translation, and toalltheparticipantsoftheseminar“MinimalNetworks” whichtheauthorsled at mechanical and mathematical faculty of Moscow State University for their interest and numerous fruitful discussions. 1 Preliminaries In the present paragraph we discuss a few more optimization problems closely related with description of minimal fillings. In particular, we give formal defi- nition of the shortest networks. Let =(X,d) be a pseudo-metric space and G =(V,E) an arbitrary con- X nected graph. Any mapping Γ: V X is called a network in parameterized → X by the graph G=(V,E), or a network of the type G. The vertices and edges of thenetworkΓaretherestrictionsofthemappingΓ,respectivelyonthevertices and edges of the graph G. The length of the edge Γ: vw X is the value → d Γ(v),Γ(w) , and the length d(Γ) of the network Γ is the sum of lengths of all its edges. In what follows we shall consider various boundary value problems (cid:0) (cid:1) for graphs. To do that, we fix some subsets ∂G of the vertex sets V of our graphs G = (V,E), and we call such ∂G the boundaries. We always suppose that in each graph under consideration there was chosen a boundary, possibly, an empty one. The boundary ∂Γ of a network Γ is the restriction of Γ to ∂G. If M X is finite and M Γ(V), then we saythat the network Γ joins the set ⊂ ⊂ M. The verticesof graphs andnetworkswhich are not boundary are saidto be interior. The value smt(M)=inf d(Γ) Γ is a network joining M { | } is called the length of shortest network. Notice that the network Γ which joins M and satisfies d(Γ) = smt(M) may not exist, see [6] and [26] for non-trivial examples. If sucha network exists, it is called a shortest network joining M, or 2. Reduction to trees. 8 for M. One variant of the Steiner problem is to describe the shortest networks 1 joining finite subsets of pseudo-metric spaces. Now let us define minimal parametric networks in a pseudo-metric space = (X,d). Let G = (V,E) be a connected graph with some boundary ∂G, X and let ϕ: ∂G X be a mapping. By [G,ϕ] we denote the set of all networks → Γ: V X of the type G such that ∂Γ=ϕ. We put → mpn(G,ϕ)= inf d(Γ) Γ∈[G,ϕ] and the value obtained we call by the length of minimal parametric network. If there exists a network Γ [G,ϕ] such that d(Γ) = mpn(G,ϕ), then Γ is called ∈ a minimal parametric network of the type G with the boundary ϕ. Assertion 1.1 Let = (X,d) be an arbitrary pseudo-metric space and M be X a finite subset of X. Then smt(M)=inf mpn(G,ϕ) ϕ(∂G)=M . { | } Thus,theproblemofcalculatingthelengthoftheshortestnetworkisreduced to investigation of minimal parametric networks. Let = (M,ρ) be a finite pseudo-metric space and G = (V,E) be an M arbitrary connected graph joining M. In this case we always assume that the boundary of such graph G is fixed and equal M. By Ω( ,G) we denote the M set of all weight functions ω: E R such that (G,ω) is a filling of the space → . We put M mpf( ,G)= inf ω(G) M ω∈Ω(M,G) and the value obtained we call the weight of minimal parametric filling of the type G for the space . If there exists a weight function ω Ω( ,G) which M ∈ M ω(G)=mpf( ,G)for,then(G,ω) iscalledaminimal parametric filling of the M type G for the space . M Assertion 1.2 Let =(M,ρ) be a finite pseudo-metric space. Then M mf( )=inf mpf( ,G) . M M (cid:8) (cid:9) 2 Reduction to trees In this paragraphwe show that investigating minimal fillings and shortest net- works, one can restrict himself by trees with special boundaries. Also, it is sufficient to consider not all but some graphs, rather simple ones, in the study of minimal parametric fillings and networks. To start with, we give definitions of fillings and networks in the most general terms of multigraphs. 1Thedenotation smtisanabbreviationof“SteinerMinimalTree” whichisasynonym for theshortest networkwhoseedges arenon-degenerate and,thus,itmustbeatree. 2. Reduction to trees. 9 2.1 Multigraphs, fillings, and networks Recall that multigraph is a triple G = (V,E,I), where V and E are finite sets which are called the sets of vertices and edges of G, respectively, and I is a mapping from E to the set of 1- or 2-element subsets of V. The mapping I is called the incidence. If I(e) = v , then e is called a loop incident to v. { } For simplicity reasons we sometimes denote the 1-element set v by v,v . { } { } Moreover,we sometimes denote an edge e E such that I(e)= x,y by xy. ∈ { } Further, if I−1(x) = , then the number of elements in I−1(x) is called the 6 ∅ multiplicity of each of the edges e I−1(x). Each edge with multiplicity more ∈ than 1 is called multiple. A graph without loops and multiple edges is called simple. ForsuchgraphstheimageofthemappingI isasetof2-elementsubsets of V (loops are absent) and I is one-to-one with its image (multiple edges are absent), thus in this case E may be identified with I(E), i.e., with a family of 2-element subsets of V, and the mapping I is usually omitted. Notice that in previous paragraphs we handled just the simple graphs, and called them by graphssimply. In the currentparagraphwe use the term graph for multigraphs as a rule. The concepts of paths, cycles, connectivity, weight function, filling, network canbe defined formultigraphsinthe samemannerasfor simple graphs. Letus note that in any network all its loops have zero lengths, and all multiple edges joining the same pair of vertices have the same lengths. The next construction will be useful in what follows. Let G = (V,E,I) be an arbitrary graph, X be some set, and f: V X be a mapping. We use f to → denote the extension of f to the set of all subsets of V also. Define the image f(G) of the graph G as f(G) = f(V),E,f I . If M is the boundary of G, ◦ then the boundary of graph f(G) is the set f(M) X. (cid:0) (cid:1) ⊂ Now we give a list of some simplest properties of minimal fillings and net- works considering in such generality. These properties will show that such gen- erality is redundant. We start from minimal parametric fillings. In what follow we call the edges of zero length by degenerate ones, and the edges of non-zero length by non-degenerate ones. A weighed graph without degenerate edges is said to be non-degenerate. Assertion 2.1 Let be a minimal parametric filling of the type G of some G pseudo-metric space . Then M (1) all interior vertices of degree 1 of the graph G are incident to degenerate edges; (2) ifoneremoves aninteriorvertexofdegree2incident todifferentedgesfrom the graph G and afterwards glues this two edges to one and assigns to the edge obtained the sum of weights of its generating edges, then the resulting weighted graph is a minimal parametric filling of as well; M (3) each loop of the graph G is degenerate; (4) multiple edges of G have the same weights; 2. Reduction to trees. 10 (5) the weight of each edge of G being a part of a cycle does not exceed the sum of weights of the remaining edges of the cycle. Proof. (1) Changing the weights of edges incident to vertices of degree 1, one preservesthepropertyofthe weightedgraphtobe afilling,thus,byminimality reasons,such edges must have zero weights. (2)Gluingthetwoedgesincidenttoaninteriorvertexofdegree2tooneedge ofthetotalweightdoesnotchangeasthepropertyofgraphtobeafilling,soas theweightofthe graph,thus theobtainedgraphmustbeaminimalparametric filling as well. (3) The proof is similar with the one of (1). (4) If multiple edges have different weights, then decreasing the biggest weightslightly,wepreservethepropertyofthegraphtobeafilling,butdecrease the total weight of the graph. (5) Otherwise, one can decreasethe weight ofthe edge preservingG to be a filling. The proof is complete. Now let us pass to minimal fillings. Since each of them is a minimal para- metricfilling, ithasallthe propertiesfromAssertion2.1. However,someofthe properties can be reinforced. Assertion 2.2 In any minimal filling (1) each multiple edge is degenerate; (2) each edge contained in a cycle is degenerate. Proof. From each family of non-degenerate multiple edges one can remove an edge and the resulting graph remains a filling but with less weight. Thus, in eachminimalfillingallmultipleedgesmustbedegenerate. Thesamearguments can be applied to non-degenerate edges in cycles. The proof is complete. Similarly to the case of fillings, we call the zero-length edges of a network by degenerate ones, and all the remaining edges by non-degenerate. A network which has no degenerate edges is said to be non-degenerate. Assertion 2.3 LetΓbeaminimalparametricnetworkofthetypeG=(V,E,I) in a pseudo-metric space (X,d). Then (1) all vertices of degree 1 of the network Γ are incident to degenerate edges; (2) eachinteriorverticesofdegree2ofthenetworkΓincidenttodifferentedges is placed between the vertices adjacent to it, i.e., if v, vw , and vw are 1 2 the corresponding vertices and edges of the parametric graph G, then d Γ(w ),Γ(v) +d Γ(v),Γ(w ) =d Γ(w ),Γ(w ) , 1 2 1 2 thus, if one(cid:0)removes v (cid:1)from(cid:0)G and chan(cid:1)ges t(cid:0)he edges vw (cid:1)to the edge i w w , then the network obtained by the restriction of Γ to the set V v 1 2 \{ } of the reconstructed graph G is a minimal parametric network with the same boundary;