Graph Theory. 1. Fragmentation of Structural Graphs from Leonardo Electronic Journal of Practices and Technologies

Graph Theory.

1. Fragmentation of Structural Graphs

Lorentz JÄNTSCHI

Technical University Cluj-Napoca

http://lori.academicdirect.ro

Abstract

The investigation of structural graphs has many fields of applications in engineering, especially in applied sciences like as applied chemistry and physics, computer sciences and automation, electronics and telecommunication.

The main subject of the paper is to express fragmentation criteria in graph using a new method of investigation: terminal paths. Using terminal paths are defined most of the fragmentation criteria that are in use in molecular topology, but the fields of applications are more generally than that, as I mentioned before.

Graphical examples of fragmentation are given for every fragmentation criteria. Note that all fragmentation is made with a computer program that implements a routine for every criterion.[1]

A web routine for tracing all terminal paths in graph can be found at the address: http://vl.academicdirect.ro/molecular_topology/tpaths/.

Keywords

Graph theory, Graph fragmentation, Vertex descriptors, Molecular topology, Graph coloring, Graph partitioning.

1. Introduction

The fragmentation of structural graphs has various applications, starting from electric circuits and internet routing and ending with computational chemistry and molecular topology.

Partitioning of graph in classes of vertices may be done in different ways [2],[3]. The most frequently used discriminating criteria are well-known square matrices that collect contributions of pairs of vertices from the graph. The adjacency matrix is the simplest matrix of this type.

Some authors use characteristic polynomial and its eigenvalue to characterize a given graph [4].

The sequence of eigenvalues forms the graph spectrum [5]. A basic result in spectral geometry is the theorem of Cheng [6].

Let us consider a sequence matrix. It is of dimension n×(n-1), where n is the number of vertices.

Such a matrix can be used to compare different graphs (interstructural similarity), when analyzing the columns of sequence matrices, the sums by columns or global sums (generic indices) [7].

It is also possible to compare the vertices of a graph (intrastructural similarity), when analyzing the rows of sequence matrices and the sums by rows [8],[9]. With this observation, a sequence matrix is an elegant method to investigate graphs [10].

Note that the ordering of graph vertices by using sequence matrices is of a partially ordered type [11],[12].

Prior, Dobrynin reported the degeneracy of some sequence matrices [13],[14]. Decomposition of graphs into congruent factors has interesting chemical implications [15],[16]. Dobrynin [17] and Diudea [18],[19] reported distance degree sequences (DPS in our notation) and their chemical applications.

The path sequence matrix (APS in our notation) is calculated in order to study molecular similarity [20].

2. Terminal Paths

Let G = (V, E) be an un-oriented graph. We are note the set of all paths in G with P(G). The distance from i to j in G is d(G)_i,j and detour is δ(G)_i,j. For p Î P(G), l(p) denotes the length of path p.

t = (v_i)_1≤i≤n is named terminal path if:

v_i Î V, t Î P(G) and

"v Î V s. th. (v_n, v) Î E then t È (v_n, v) Ï P(G)

(1)

The set of terminal paths in G is T(G) = (T(G)_v)_v_Î_V where T(G)_i is:

T(G)_i = {t = (v_i)_1≤i≤n s. th. v₁ = i and t terminal path}

(2)

Note that if G = (V, E) is a connected graph, then " v Î V, " e Î E $ t Î T(G)_v s. th. e Í t. Thus, any connected graph can be reconstructed from the terminal path list starting from an arbitrary vertex.

Also, " i, j Î V, T(G)_j can be constructed from T(G)_i. Consequently, the sets of terminal paths T(G)_v, v Î V are equivalent by construction.

For exemplification of terminal paths, let us consider the graph G from fig. 1:

Fig. 1. Graph G

G = (V, E); V = {1, …, 8}; E = {(1, 2), (1, 3), (2, 4), (3, 5), (3, 6), (4, 5), (4, 7), (6, 7), (7,8)}

All terminal paths starting from vertex 1 are computed using graph G from figure 1 and definitions (1) and (2). The solution is:

T(G)₁ = {

}

{1, 2, 4, 5, 3, 6, 7, 8}, {1, 2, 4, 7, 8}, {1, 2, 4, 7, 6, 3, 5},

{1, 3, 6, 7, 8}, {1, 3, 6, 7, 4, 2}, {1, 3, 6, 7, 4, 5},

{1, 3, 5, 4, 7, 6}, {1, 3, 5, 4, 7, 8}, {1, 3, 5, 4, 2}

(3)

Note that according to definition (1) and (2), T(G) Í P(G) for any graph G.

3. Graph Partitioning in Sets

Let G = (V, E) be a connected graph and i, j Î V two vertices. Let p Î P(G)_i,j a path from i to j in G.

CJ_i,j,p = {k : k Î V} is named CJ set of i vs. j and p if:

d(G)_k,i < d(G)_k,j

$ q Î P_k,i s. th. p Ç q = {i}

(4)

The set of sets of vertices CJS_i,j = {CJ_i,j,p: pÎP(G)_i,j} are named set of CJ sets of i vs. j.

CJDi_i,j,p = {k : k Î V} is named CJDi set of i vs. j and p if:

CJDi_i,j,p Î CJS_i,j

l(p) = d(G)_i,j

(5)

The set of sets of vertices CJDiS_i,j = {CJDi_i,j,p : p Î P(G)_i,j} are named set of CJDi sets of i vs. j.

CJDe_i,j,p = {k | k Î V} is named CJDe set of i vs. j and p if:

CJDi_i,j,p Î CJS_i,j

l(p) = δ(G)_i,j

(6)

The set of sets of vertices CJDeS_i,j = {CJDe_i,j,p | p Î P(G)_i,j} are named set of CJDe sets of i vs. j. CJDi^M_i,j = {s : s Î CJDiS_i,j} is named CJDi^M set of i vs. j if l(s) = max{ |cjdi| : cjdi Î CJDiS_i,j}. CJDe^M_i,j = {s : s Î CJDeS_i,j} is named CJDe^M set of i vs. j if l(s) = max{ |cjde| : cjde Î CJDeS_i,j}. The sets CJDi can be constructed as follows:

CJDi_i,j,p= Æ; CJDi_j,i,p= Æ;

For (v = 1; v ≤ |V|; v++)

If (d(G)_v,i < d(G)_v,j) and ($p' Î P(G)_v,i s.th. p' Ç p == {i})

then CJDi_i,j,p= CJDi_i,j,p È {v};

EndIf;

If (d(G)_v,j < d(G)_v,i) and ($p' Î P(G)_v,j s.th. p' Ç p == {j})

then CJDi_j,i,p= CJDi_j,i,p È {v};

EndIf;

EndFor;

(7)

Note that the algorithm (7) can be applied for any distance operator in place of d(∙), such as detour operator δ(∙).

Through CJ sets there exist inclusions relations:

CJDiS^M_i,j Í CJDiS_i,j Í CJS_i,j and CJDeS^M_i,j Í CJDeS_i,j Í CJS_i,j

(8)

that are obviously from the definitions (4)-(6). Figurative, inclusions are:

Fig. 2. Inclusions relations in CJ sets

Note that in generally the sets CJDiS^M_i,j, CJDiS_i,j, CJS_i,j, CJDeS^i,j, CJDeS^M_i,j are not distinct; more, in trees the sets are equals.

To prove that the sets CJDiS^M_i,j, CJDiS_i,j, CJS_i,j, CJDeS^i,j, CJDeS^M_i,j are not banal, let’s apply the algorithm (7) to construct sets for graph G from fig. 1.

Following example shows that sets CJDiS^M and CJDeS^M are not identically:

CJDiS^M_1,2 = {CJ_1,2,[1,2]}; CJ_1,2,[1,2] = {1, 3, 6, 8}

CJDiS^M_2,1 = {CJ_2,1,[2,1]}; CJ_2,1,[2,1] = {2, 4, 7}

CJDeS^M_1,2 = {CJ_{1,2,[1,3,6,7,4,2]}}; CJ_{1,2,[1,3,6,7,4,2]} = {1}

CJDeS^M_1,2 = {CJ_{2,1,[2,4,7,6,3,1]}}; CJ_{2,1,[2,4,7,6,3,1]} = {2}

and graphical representation of them are in fig. 3:

Fig. 3. CJDi and CJDe sets for vertices 1 and 2 and graph G from fig. 1

The following example shows that CJDe sets are not included in CJDi sets:

CJDiS^M_4,8 = {CJ_{4,8,[4,7,6,8]}}; CJ_{4,8,[4,7,6,8]} = {1, 2, 4, 5}

CJDiS^M_8,4 = {CJ_{8,4,[8,6,7,4]}}; CJ_{8,4,[8,6,7,4]} = {8}

CJDeS^M_4,8 = {CJ_{4,8,[4,2,1,3,6,8]}}; CJ_{4,8,[4,2,1,3,6,8]} = {4, 5, 7}

CJDeS^M_8,4 = {CJ_{8,4,[8,6,3,1,2,4]}}; CJ_{8,4,[8,6,3,1,2,4]} = {8}

and graphical representation of them are in fig. 4:

Fig. 4. CJDi_{4,8,[4,7,6,8]} and CJDe_{4,8,[4,2,1,3,6,8]} sets for graph G from fig. 1

The following example shows that sets CJDiS^M can contain more than one set:

CJDiS^M_2,8 = {CJ_{2,8,[2,4,7,6,8]} = {1, 2, 5}, CJ_{2,8,[2,1,3,6,8]} = {4, 2, 5}};

CJDiS^M_8,2 = {CJ_{8,2,[8,6,3,1,2]} , CJ_{8,2,[8,6,3,1,2]}}; CJ_{8,2,[8,6,3,1,2]} = CJ_{8,2,[8,6,7,4,2]} = {8};

and graphical representation of them are in fig. 5:

Fig. 5. CJDi_2,8,[24768] and CJDi_2,8,[21368] sets of graph G from fig. 1

4. G_p Subgraph

Let p = (i = v₁, …, v_l(p) = j) Î P(G) a path starting from vertex i and ending in vertex j. The G_p subgraph of graph G and path p is defined by:

G_p = (V_p, E_p),

V_p = {v Î V : v Ï p\{i, j}},

E_p = {e = (e_a, e_b) Î E : e_a, e_b Ï p\{i, j}}

(9)

Note that G_p subgraph associated of graph G and path p is not necessary a connected subgraf, even if G is a connected graph. More, if G is a tree, G_p has at least two connected components.

For path p = [1, 3, 5, 4, 7] and graph G from fig. 1 the graph G_{[1, 3, 5, 4, 7]} = G\[1, 3, 5, 4, 7] is not a connected graph. G_p has two connected components: [1, 2] and [7, 6, 8]. Also, from original graph G, p\{1,7} is also a connected component. Using comparison operator ≤ between graphs is obviously that G_p È p ≤ G. In fig. 6 are graphically represented the components of G by path p:

Fig. 6. Graph G, path p = [1, 3, 5, 4, 7], path p\{1, 7} = [3, 5, 4] and subgraph G_p

G_p = (V_p, E_p), V_p = {1, 2, 6, 7, 8}, E_p = {(1,2), (6, 7), (6, 8)}

Note that G = G_p È p È [2, 4] È [3, 6].

3. Graph Partitioning in Fragments

Let G = (V, E) be a connected graph and i, j Î V two vertices. Let p Î P(G)_i,j a path from i to j in G.

CF_i,j,p = {k : k Î V} is named CF fragment of i vs. j and p if:

d(G_p)_k,i < d(G_p)_k,j

(10)

where subgraph G_p is obtained from graph G and path p according to definition (9).

Note that in definition (10) is used term of fragment for CF_i,j,p. Indeed, CF_i,j,p is an fragment, a connected set of vertices from graph G.

The set of sets of vertices CFS_i,j = {CF_i,j,p: p Î P(G)_i,j} are named set of CF sets of i vs. j.

More, in CFS_i,j,p fragment, there exist the relation:

"kÎCFS_i,j,p, $qÎP(G_p)_k.i path from k to i in G_p s. th. qÇp = {i}

(11)

Similar to definitions (5) and (6), CFDi and CFDe fragments are defined:

CFDi_i,j,p={k : kÎV} is named CFDi fragment of i vs. j and p if:

CFDi_i,j,p Î CFS_i,j

l(p) = d(G_p)_i,j

(12)

The fragments set CFDiS_i,j = {CFDi_i,j,p : p Î P(G)_i,j} are named set of CFDi fragments of i vs. j.

CFDe_i,j,p={k : kÎV} is named CFDe fragment of i vs. j and p if:

CFDe_i,j,p Î CFS_i,j

l(p) = δ(G_p)_i,j

(13)

The fragments set CFDeS_i,j = {CFDe_i,j,p : pÎP(G)_i,j} are named set of CFDe fragments of i vs. j. CFDi^M_i,j = {f : f Î CFDiS_i,j} is named CFDi^M fragment of i vs. j if l(f) = max{ |cfdi| : cfdi Î CFDiS_i,j}. CFDe^M_i,j = {f : f Î CFDeS_i,j} is named CFDe^M set of i vs. j if l(f) = max{ |cfde| : cfde Î CFDeS_i,j}. The sets CFDi can be constructed as follows:

CFDi_i,j,p= Æ; CFDi_j,i,p= Æ;

For (v = 1; v ≤ |V|; v++)

If (d(G_p)_v,i < d(G_p)_v,j) then CFDi_i,j,pÈ= {v}; EndIf;

If (d(G_p)_v,j < d(G_p)_v,i) then CFDi_j,i,pÈ= {v}; EndIf;

EndFor;

(14)

Note that the algorithm (14) can be applied for any distance operator in place of d(∙), such as detour operator δ(∙).

Based on construction (14) the sets CFDi are always fragments. Through CF sets it exist inclusions relations:

CFDiS^M_i,j Í CFDiS_i,j Í CFS_i,j and

CFDeS^M_i,j Í CFDeS_i,j Í CFS_i,j

(15)

that are obviously from the definitions (11)-(13). Figurative, inclusions are:

Fig. 7. Inclusions relations for CF sets

Note that in generally the sets CF are not distinct. In trees are even equals.

To prove that the sets CFDiS^M_i,j, CFDiS_i,j, CFS_i,j, CFDeS^i,j, CFDeS^M_i,j are not banal, let’s apply the algorithm (14) to construct sets for graph G from fig. 1.

Following example shows that sets CFDiS^M and CFDeS^M are not identically:

CFDiS^M_1,2 = {CF_1,2,[1,2]}; CF_1,2,[1,2] = {1, 3, 6, 8}

CFDiS^M_2,1 = {CF_2,1,[2,1]}; CF_2,1,[2,1] = {2, 4, 7}

CFDeS^M_1,2 = {CF_{1,2,[1,3,6,7,4,2]}}; CF_{1,2,[1,3,6,7,4,2]} = {1}

CFDeS^M_1,2 = {CF_{2,1,[2,4,7,6,3,1]}}; CF_{2,1,[2,4,7,6,3,1]} = {2}

and graphical representation of them are in fig. 3:

Fig. 8. CFDi_1,2,[1,2] and CFDi_{1,2,[1,2,6,7,4,2]} fragments of graph G from fig. 1

The following example shows that CFDe sets are not included in CFDi sets:

CFDiS^M_4,8 = {CF_{4,8,[4,7,6,8]}}; CF_{4,8,[4,7,6,8]} = {1, 2, 3, 4, 5};

CFDeS^M_4,8 = {CF_{4,8,[4,2,1,3,6,8]}}; CF_{4,8,[4,2,1,3,6,8]} = {4, 5, 7};

CFDiS^M_8,4 = {CF_{8,4,[8,6,7,4]}} = {{8}} = {CF_{8,4,[8,6,3,1,2,4]}} = CFDeS^M_8,4

and fragments are depicted in fig. 9:

Fig. 9. CFDi_{4,8,[4,7,6,8]} and CFDe_{4,8,[4,2,1,3,6,8]} fragments of graph G from fig. 1

The following example shows that sets CFDiS^M can contain more than one fragment:

CFDiS^M_7,1 = {CF_{7,1,[7,4,2,1]} , CF_{7,1,[7,6,3,1]}};

CF_{7,1,[7,4,2,1]} = {6, 7, 8}; CF_{7,1,[7,6,3,1]} = {4, 5, 7}

and graphical representation of them are in fig. 10:

Fig. 10. CFDi_{7,1,[7,4,2,1]} and CFDi_{7,1,[7,6,3,1]} fragments of graph G from fig. 1

The Szeged (SzDi) fragments are defined by:

SzDi_i,j = {k : k Î V} is named SzDi fragment of i vs. j if:

d(G)_k,i < d(G)_k,j

(16)

The SzDi sets are connected subgraphs (fragments). Looking at (5) and (16) definitions, is easy to observe that:

CJDi Í SzDi,

(17)

and also:

CFDi Ë SzDi,

(18)

The following construction collects the fragments SzDi for all i and j pairs of vertices:

For (i = 1; i < |X|; i++)

For (j = i + 1; j ≤ |X|; j++)

SzDi_i,j:= Æ; SzDi_j,i:= Æ;

For (v = 1; v ≤ |X|; v++)

dvi = maxint; dvj = maxint;

For (ct Î T(G)_v)

For (k = 1; k ≤ ct[0]; k++)

If (ct[k] == i) and (dvi > k) then dvi = k; EndIf;

If (ct[k] == j) and (dvj > k) then dvj = k; EndIf;

EndFor;

If dvi > dvj then SzDi_i,j È= {v}; EndIf;

If dvi > dvj then SzDi_j,i È= {v}; EndIf;

EndFor;

(19)

A graphical example of SzDi fragments for vertices 2 and 6 and graph G from fig. 1 is depicted in fig. 11:

Fig. 11. SzDi_2,6 and SzDi_6,2 fragments of graph G from fig. 1

Like CJ and CF, SzDe sets can be defined as:

SzDi_i,j = {k : k Î V} is named SzDe set of i vs. j if:

δ(G)_k,i < δ(G)_k,j

(20)

SzDe sets are not fragments (connected subgraphs). An example is depicted in fig. 12:

Fig. 12. SzDe_2,6 = {2,3} and SzDe_6,2 = {4, 6, 8} sets for graph G from fig. 1

4. A Comparison between Graph Partitioning Methods

Let us to consider the graph from fig. 13. If CFDi, CJDi and SzDi partitioning methods are applied for graph G from fig. 13 and (1,4) pair of vertices, we have:

CFDi_{1,4,[1,2,3,4]} = {1, 8, 9, 10}; CFDi_{4,1,[4,3,2,1]} = {4, 5, 6, 7};

CJDi_{1,4,[1,2,3,4]} = {1, 9, 10}; CJDi_{4,1,[4,3,2,1]} = {4, 5, 6, 7, 8};

SzDi_1,4 = {1, 2, 9, 10}, SzDi_4,1 = {3, 4, 5, 6, 7, 8}.

Fig. 13. Graph G = (V, E); V = {1, …, 10}; E = {(i, i+1) : 1 ≤ i ≤ 10} È {(10, 1), (8, 3)} and

CFDi_{1,4,[1,2,3,4]}, CFDi_{4,1,[4,3,2,1]}, CJDi_{1,4,[1,2,3,4]}, CJDi_{4,1,[4,3,2,1]}, SzDi_1,4, SzDi_4,1 sets

From fig. 13, some conclusions are immediate:

· The sets CFDi and CJDi are distinct: CF_{4,1,[4,3,2,1]} Ì CJ_{4,1,[4,3,2,1]} and CF_{1,4,[1,2,3,4]} Ì CJ_{1,4,[1,2,3,4]};

· The sets SzDi and CJDi are distinct: CJ_{4,1,[4,3,2,1]} Ì Sz_4,1 and CJ_{1,4,[1,2,3,4]} Ì Sz_1,4;

· The sets SzDi and CFDi are distinct: CF_{4,1,[4,3,2,1]} Ì Sz_4,1 and CF_{1,4,[1,2,3,4]} Ë Sz_1,4;

· The sets CFDi are not contained in sets SzDi: CF_{4,1,[4,3,2,1]} Ì Sz_4,1 and CF_{1,4,[1,2,3,4]} Ë Sz_1,4;

· The CJDi sets are contained in SzDi sets: CJ_{4,1,[4,3,2,1]} Ì Sz_4,1 and CJ_{1,4,[1,2,3,4]}Ì Sz_1,4;

Let us consider another two fragmentation methods, the minimal set that contain i vertex and not contain j vertex MI_i,j:

MI_i,j = {i}

(21)

and maximal set that contain i vertex and not contain j vertex:

MA_i,j = G\{j}

(22)

Some interesting properties are also available now:

· MI_i,j is a set that is contained in all sets generated for (i,j) pair of vertices:

MI_i,j Í CJ_i,j,p; MI_i,j Í CF_i,j,p; MI_i,j Í Sz_i,j

(23)

· MA_i,j it contain all fragments generated for (i,j) pair of vertices:

CJ_i,j,p Ê MA_i,j; CF_i,j,p Ê MA_i,j; Sz_i,j Ê MA_i,j

(24)

The inclusions and intersections of sets are depicted in fig. 14:

Fig. 14. Inclusions between MI, CJ, CF, SZ and MA sets

5. Graph Edges Coloring

The edges of a graph can be colored depending on which fragment are included. To apply the coloring process, is necessary to decompose the graph into connected fragments. From presented methods, connected subgraphs are obtained for CFDi, CFDe and SzDi criteria.

The CFDi criterion partition a graph G for a pair of vertices (i, j) into four regions:

· region of i’s belonging versus j, that is CFDi_i,j,p;

· region of j’s belonging versus i, that is CFDi_j,i,p;

· the path p\{i, j};

· indifferent region G\{p\{i, j} È CFDi_i,j,p È CFDi_j,i,p}

An important observation is that first three regions are connected sets of vertices (fragments) and last one (indifferent region) it can be a disconnected subgraph.

In fig. 15 are depicted partitioning of graph G from fig. 1 into four regions:

Fig. 15. Graph G from fig. 1 edges coloring in two cases: (3, 6) and (3,4) pairs of vertices

yellow: CFDi_i,j; turquoise: CFDi_j,i; pink: p\{i, j}; red: rest;

The fragments from fig. 15 are:

CFDi_3,6,[3,6] = [1,2,3,5]; CFDi_6,3,[6,3] = [6,7,8];

CFDi_3,4,[3,5,4] = [1,3,6,8]; CFDi_4,3,[4,5,3] = [2,4,7];

Note that for (3,4) pair of vertices, the remaining zone of graph, {(1, 2, 6, 7), (1, 2), (6, 7)} are not connected one.

With a similar deduction, The CFDe criterion partition a graph G for a pair of vertices (i, j) into four regions:

· region of i’s belonging versus j, that is CFDe_i,j,p;

· region of j’s belonging versus i, that is CFDe_j,i,p;

· the path p\{i, j};

· indifferent region G\{p\{i, j} È CFDe_i,j,p È CFDe_j,i,p}

An important observation is that first three regions are connected sets of vertices (fragments) and last one (indifferent region) it can be a disconnected subgraph.

In fig. 16 are depicted partitioning of graph G from fig. 1 into four regions:

Fig. 16. Graph G from fig. 1 edges coloring in two cases: (3, 6) and (3,4) pairs of vertices

yellow: CFDe_i,j; turquoise: CFDe_j,i; pink: p\{i, j}; red: rest;

The fragments from fig. 16 are:

CFDi_{3,6,[3,1,2,4,7,6]} = [3,5]; CFDi_{6,3,[6,7,4,2,1,3]} = [6,8];

CFDi_{3,4,[3,1,2,4]} = [3,6,8]; CFDi_{4,3,[4,2,1,3]} = [4,7];

Note that for (3,4) pair of vertices, the remaining zone of graph, {(1, 2, 6, 7), (1, 2), (6, 7)} are not connected one.

With a similar deduction, The SzDi criterion partition a graph G for a pair of vertices (i, j) into three regions:

· region of i’s belonging versus j, that is CFDe_i,j,p;

· region of j’s belonging versus i, that is CFDe_j,i,p;

· the equidistant region {k : d(k,i) = d(k,j)}.

An important observation is that first two regions are connected sets of vertices (fragments) and last one (equidistant region) it can be a disconnected subgraph.

In fig. 17 are depicted partitioning of graph G from fig. 1 into three regions:

Fig. 17. Graph G from fig. 1 edges coloring in two cases: (3, 6) and (3,4) pairs of vertices

yellow: CFDe_i,j; turquoise: CFDe_j,i; red: equidistant region {k : d(k,i) = d(k,j)};

The fragments from fig. 17 are:

SzDi_3,6 = [1,2,3,5]; SzDi_6,3 = [6,7,8];

SzDi_3,4 = [1,3,6,8]; SzDi_4,3 = [2,4,7];

6. Theoretical Results (Theorems)

Theorem 1. CF is a fragment.

" i, j Î V,  p Î P(G)_i,j path in G from i to j then F_i,j,p fragment

Demonstration:

Fig. 18. Auxiliary construction for theorem 1 demonstration

Let v Î CF_i,j,p. Then:

(Case 1) d(G_p)_v,i < ¥, d(G_p)_v,j = ¥ and respectively

(Case2) d(G_p)_v,i < ¥, d(G_p)_v,j < ¥, d(G_p)_v,i < d(G_p)_v,j

(Case 1, demonstration):

d(G_p)_v,i< ¥ Þ $p_v,iÎ P(G_p)_v,i (P(G_p)_k,i¹ Æ). Let k Î p_v,i Þ $p_k,iÎ P(G_p)_k,i (p_k,iÍ p_v,i) Þ

d(G_p)_k,i< ¥ Þ $p_v,kÎ P(G_p)_v,k (p_v,kÍ p_v,i)

(25)

If d(G_p)_k,j< ¥ Þ $p_k,jÎ P(G_p)_k,j (P(G_p)_k,j¹ Æ). Let w_v,j= p_v,kÈ p_k,j; w_v,jÎ W(G_p)_v,j (W(Gp)_v,j¹ Æ) Þ d(Gp)_v,j£ l(p_v,k) + l(p_k,j) < ¥ contradiction with d(G_p)_v,j= ¥ Þ

d(G_p)_k,j= ¥

(26)

From (25) and (26) Þ k Î CF_i,j,p Þ p_v,iÍ CF_i,j,p Þ v connected with i in CF_i,j,p Þ

CF_i,j,p connected

(27)

(Case 2, demonstration):

d(G_p)_v,i< ¥ Þ $p_v,iÎ P(G_p)_v,i s. th. l(p_v,i) = min{l(q), q Î P(G_p)_v,i} (P(G_p)_v,i¹ Æ; l(p_v,i) = d(G_p)_v,i). Let k Î p_v,iÞ

$ p_k,iÎ P(G_p)_k,i (p_k,iÍ p_v,i) , $p_v,kÎ P(G_p)_v,k (p_v,kÍ p_v,i)

(28)

Because a geodesic path can contain only geodesic paths, from (28) it results:

l(p_k,i) = d(G_p)_k,i, l(p_v,k) = d(G_p)_v,k , l(p_v,i) = l(p_v,k) + l(p_k,i) Þ d(G_p)_v,i= d(G_p)_v,k+ d(G_p)_k,i

d(G_p)_v,j£ d(G_p)_v,k+ d(G_p)_k,j (d(G_p) a metric); (28) Þ d(G_p)_v,j-d(G_p)_v,i£ d(G_p)_k,j- d(G_p)_k,i

From d(G_p)_v,i< d(G_p)_v,j Þ 0 <d(G_p)_v,j- d(G_p)_v,i£d(G_p)_k,j-d(G_p)_k,i and then:

d(G_p)_k,i < d(G_p)_k,j Þ k Î CF_i,j,p Þ p_v,iÍ CF_i,j,p Þ

v connected with i in CF_i,j,p Þ CF_i,j,p connected

(29)

From (27) and (29) it result that CF_i,j,p is a connected subgraph (q.e.d.).

Theorem 2. SzDi is a fragment.

"i, j Î V then SZDi_i,j fragment

Demonstration:

Let v Î SZDi_i,j. Then d(G)_v,i< ¥, d(G)_v,j< ¥, d(G)_v,i< d(G)_v,j (G connected graph).

From d(G)_v,i< ¥ Þ $p_v,iÎ P(G)_v,i s. th. l(p_v,i) = min{l(q), qÎ P(G)_v,i} (P(G)_v,i¹ Æ; l(p_v,i) = d(G)_v,i). Let k Î p_v,iÞ

$ p_k,iÎ P(G)_k,i (p_k,iÍ p_v,i) , $p_v,kÎ P(G)_v,k (p_v,kÍ p_v,i)

(30)

Because a geodesic path can contain only geodesic paths, from (28) it results:

l(p_k,i) = d(G)_k,i, l(p_v,k) = d(G)_v,k , l(p_v,i) = l(p_v,k) + l(p_k,i) Þ d(G)_v,i= d(G)_v,k+ d(G)_k,i

d(G)_v,j£ d(G)_v,k+ d(G)_k,j (d(G) a metric); (30) Þ d(G)_v,j- d(G)_v,i£ d(G)_k,j- d(G)_k,i

Because d(G)_v,i< d(G)_v,j Þ 0 < d(G)_v,j-d(G)_v,i£ d(G)_k,j-d(G)_k,i and then

d(G)_k,i< d(G)_k,j Þ k Î SzDi_i,jÞ p_v,iÍ SzDi_i,j Þ v connected with i in SzDi_i,j Þ

SzDi_i,j connected subgraph (q.e.d.).

Theorem 3. CJDi sets are contained in SzDi fragments.

CJDi_i,j,p Ì SzDi_i,j

Demonstration:

Let v Î CJDi_i,j,p. According to definition of CJDi set,

d(G)_v,i < d(G)_v,j

(31)

This is (according to the definition of SzDi fragment) a necessary and enough such that v Î SzDi_i,j,p. From here, it result immediately that CJDi_i,j,p Ì SzDi_i,j (q.e.d.).

References