Начиная с начала 2000 года осуществляется внедрение GHIS в здравоохранении, в рамках принятого проекта о реформирование информ


 
 
Mathematical Problems of Computer Science  46,  87--91, 2016. 
 

 
 

Linear Orderings of Tridimensional Grids 
 

David H. Muradian 
 

Institute for Informatics and Automation Problems of  NAS RA 
e-mail: david.h.muradian@gmail.com 

 
Abstract 

 
The minimal linear arrangement problem (MinLA) is defined as follows: given a 

graph G, find a linear ordering (layout) 𝜑𝜑 for the vertices of G on a line such that the sum 
of the edge lengths is minimized over all orderings. Edge length for an edge (x, y) is 
defined as | 𝜑𝜑(𝑥𝑥) − 𝜑𝜑(𝑦𝑦)|. In this paper we describe the class of minimal orderings of the 
special case of tridimensional grids – Cartesian product of three simple paths, when one 
of them consists of two vertices.  

Keywords: Linear ordering, Minimal Linear Arrangement Problem, Grids, 
Wirelength. 

 
 
 
 

1. Introduction 
Given a graph G=(X,U), a layout 𝜑𝜑 is a one-to-one mapping 𝜑𝜑 : X →{1,…,|X|}. For a given 
graph G=( X,U) and a layout 𝜑𝜑, we define  
 

𝐸𝐸𝜑𝜑(𝐺𝐺) = � |𝜑𝜑(𝑥𝑥) − 𝜑𝜑(𝑦𝑦)|
(𝑥𝑥,𝑦𝑦)∈𝑈𝑈

, 

 
as a wirelength of 𝜑𝜑. We define also wirelength of G as 𝐸𝐸(𝐺𝐺) = min

𝜑𝜑
𝐸𝐸𝜑𝜑(𝐺𝐺), where 𝜑𝜑 ranges 

over all layouts of G, and a layout 𝜑𝜑0 is called minimal if 𝐸𝐸𝜑𝜑0(𝐺𝐺)= 𝐸𝐸(𝐺𝐺). Let’s denote by 𝜙𝜙𝐺𝐺
𝐸𝐸 the 

class of minimal layouts of G.  
 Let 𝑋𝑋′, 𝑋𝑋′′ ⊂ 𝑋𝑋 be nonempty disjoint sets, 𝑘𝑘 ∈ 1, 𝑁𝑁����� and 𝜑𝜑 be some layout of G. Let’s 
denote: 

𝑋𝑋𝜑𝜑𝑘𝑘 = {𝜑𝜑−1(1), 𝜑𝜑−1(2), … , 𝜑𝜑−1(𝑘𝑘), } 
𝜔𝜔(𝑋𝑋′, 𝑋𝑋′′) = |{(𝑥𝑥, 𝑦𝑦) ∈ 𝑈𝑈 ⁄ 𝑥𝑥 ∈ 𝑋𝑋′; 𝑦𝑦 ∈ 𝑋𝑋′′ }| 

δ𝜑𝜑(𝑋𝑋′) =
1

|𝑋𝑋′|
(|{(𝑥𝑥, 𝑦𝑦) ∈ 𝑈𝑈 ⁄ 𝑥𝑥 ∈ 𝑋𝑋′; 𝑦𝑦 ∉ 𝑋𝑋′; 𝜑𝜑(𝑥𝑥) < 𝜑𝜑(𝑦𝑦) }|

− |{(𝑥𝑥, 𝑦𝑦) ∈ 𝑈𝑈 ⁄ 𝑥𝑥 ∈ 𝑋𝑋′; 𝑦𝑦 ∉ 𝑋𝑋′; 𝜑𝜑(𝑥𝑥) > 𝜑𝜑(𝑦𝑦) }|) 
 

 
87 
 



Linear Orderings of Tridimensional Grids 88 

Definition: We say that a set 𝑋𝑋′ (𝑋𝑋′ ⊂ 𝑋𝑋) is compact with respect to layout 𝜑𝜑, if 
 

max
𝑥𝑥∈𝑋𝑋′

𝜑𝜑(𝑥𝑥) − min
𝑥𝑥∈𝑋𝑋′

𝜑𝜑(𝑥𝑥) = |𝑋𝑋′| − 1. 
 
Definition: We say that a set 𝑋𝑋′ (𝑋𝑋′ ⊂ 𝑋𝑋) directly goes behind the set 𝑋𝑋′′ (𝑋𝑋′′ ⊂ 𝑋𝑋) (this is 
denoted by 𝑋𝑋′  

𝜑𝜑
←  𝑋𝑋′′), if  𝑋𝑋′, 𝑋𝑋′′  are compact and  𝑚𝑚𝑚𝑚𝑥𝑥

𝑥𝑥∈𝑋𝑋′
𝜑𝜑(𝑥𝑥) = 𝑚𝑚𝑚𝑚𝑚𝑚

𝑥𝑥∈𝑋𝑋′′
𝜑𝜑(𝑥𝑥) + 1. 

Definition: We say that the sets 𝑋𝑋′, 𝑋𝑋′′ are independent of one another, if  𝜔𝜔(𝑋𝑋′, 𝑋𝑋′′) = 0. 
 In the present paper the following lemma from [1] will play an essential role.  
 
Lemma: If 𝜔𝜔(𝑋𝑋′, 𝑋𝑋′′) = 0, 𝑋𝑋′  

𝜑𝜑
←  𝑋𝑋′′ and  𝜑𝜑 is a minimal layout, then  

 
. δ𝜑𝜑(𝑋𝑋′) ≤ δ𝜑𝜑(𝑋𝑋′′) 

  
Let 𝜑𝜑 be some layout of G=(X,U) and 𝐺𝐺′ be an induced subgraph with vertex set 𝑋𝑋′ ⊂ 𝑋𝑋. Let the 
vertices of 𝑋𝑋′ have the following numbers at the layout 𝜑𝜑:    
 

𝑚𝑚1 < 𝑚𝑚2 < ⋯ < 𝑚𝑚�𝑋𝑋′�. 
 
Consider the following layout 𝜑𝜑′: 
 

𝜑𝜑′�𝜑𝜑−1(𝑚𝑚𝑖𝑖)� = 𝑚𝑚    �𝑚𝑚 = 1, |𝑋𝑋′|���������. 
 
Definition: We say that a subgraph 𝐺𝐺′ is ordered minimally at 𝜑𝜑, if 𝜑𝜑′ is a minimal layout for 
𝐺𝐺′. 
 Consider the graph P2,m,n with the vertex set 𝛱𝛱2,𝑚𝑚,𝑛𝑛 = �𝑥𝑥𝑖𝑖,𝑗𝑗,𝑘𝑘/ 𝑚𝑚 = 1,2����; 𝑗𝑗 = 1, 𝑚𝑚������; 𝑘𝑘 = 1, 𝑚𝑚������ 
and the edge set U, where �𝑥𝑥𝑖𝑖,𝑗𝑗,𝑘𝑘, 𝑥𝑥𝑖𝑖′,𝑗𝑗′,𝑘𝑘′� ∈ 𝑈𝑈 if and only if |𝑚𝑚 − 𝑚𝑚

′| + |𝑗𝑗 − 𝑗𝑗′| + |𝑘𝑘 − 𝑘𝑘′| = 1.  
Let’s denote  

𝛱𝛱𝑖𝑖1,𝑗𝑗1,𝑘𝑘1
𝑖𝑖2,𝑗𝑗2,𝑘𝑘2=�𝑥𝑥𝑖𝑖,𝑗𝑗,𝑘𝑘 /  𝑚𝑚1 ≤ 𝑚𝑚 ≤ 𝑚𝑚2;  𝑗𝑗1 ≤ 𝑗𝑗 ≤ 𝑗𝑗2;  𝑘𝑘1 ≤ 𝑘𝑘 ≤ 𝑘𝑘2�, 

 
Ω0 = �𝑥𝑥1,1,1, 𝑥𝑥1,𝑚𝑚,1, 𝑥𝑥1,1,𝑛𝑛, 𝑥𝑥1,𝑚𝑚,𝑛𝑛, 𝑥𝑥2,1,1, 𝑥𝑥2,𝑚𝑚,1, 𝑥𝑥2,1,𝑛𝑛, 𝑥𝑥2,𝑚𝑚,𝑛𝑛� 

 
where 1 ≤ 𝑚𝑚1 ≤ 𝑚𝑚2 ≤ 2;  1 ≤ 𝑗𝑗1 ≤ 𝑗𝑗2 ≤ 𝑚𝑚;  1 ≤ 𝑘𝑘1 ≤ 𝑘𝑘2 ≤ 𝑚𝑚. 
Definition: We say that the set 𝑋𝑋′ ⊂ 𝛱𝛱2,𝑚𝑚,𝑛𝑛 is concise with respect to  𝑥𝑥1,1,1, if for every 𝑥𝑥𝑖𝑖,𝑗𝑗,𝑘𝑘 ∈
𝑋𝑋′ we have 𝛱𝛱1,1,1

𝑖𝑖,𝑗𝑗,𝑘𝑘 ⊆ 𝑋𝑋′. 
Definition: We say that a layout φ is concise with respect to 𝑥𝑥1,1,1, if for every 𝑘𝑘 ∈ 1,2𝑚𝑚𝑚𝑚�������� the set 
𝑋𝑋𝜑𝜑𝑘𝑘 is concise with respect to 𝑥𝑥1,1,1. 

Similarly one can define conciseness of sets and layouts with respect to other vertices 
from Ω0.  

The following statements are valid. 
1. If   𝜑𝜑 ∈ 𝜙𝜙P2,m,n 

𝐸𝐸 , then for every 𝑘𝑘 ∈ 1,2𝑚𝑚𝑚𝑚�������� the set 𝑋𝑋𝜑𝜑𝑘𝑘 is concise with respect to at least 
one vertex from Ω0. 

2. For each vertex from Ω0, there is a minimal,  concise with respect to its layout.  

We will leave out the proofs of the above statements as they are very similar to analogous 
statements from [1]  



 

D. Muradian    89 

The following theorem is a main result of this paper. 
Theorem: Let 𝜑𝜑 be concise with respect to 𝑥𝑥1,1,1. Then 𝜑𝜑 is minimal if and only if for each i,j 
(𝑚𝑚 ∈ 1, 𝑚𝑚�����; 𝑗𝑗 ∈ 1, 𝑚𝑚������)  𝑥𝑥1,𝑖𝑖,𝑗𝑗  

𝜑𝜑
←  𝑥𝑥2,𝑖𝑖,𝑗𝑗 and the subgraphs induced by the sets 𝛱𝛱1,1,1

1,𝑚𝑚,𝑛𝑛, 𝛱𝛱2,1,1
2,𝑚𝑚,𝑛𝑛 are 

ordered minimally at 𝜑𝜑. 
Proof: Only taking into consideration conciseness of 𝜑𝜑 with respect to 𝑥𝑥1,1,1, the set 𝛱𝛱2,𝑚𝑚,𝑛𝑛 is 
divided into subsets 𝛱𝛱𝑖𝑖 (regarding δ𝜑𝜑(𝑥𝑥)):  

𝛱𝛱0 = �𝑥𝑥1,1,1� 
𝛱𝛱1 = 𝛱𝛱1,2,1

1,𝑚𝑚−1,1 ∪ 𝛱𝛱1,1,2
1,1,𝑛𝑛−1; 

𝛱𝛱2 = 𝛱𝛱1,2,2
1,𝑚𝑚−1,𝑛𝑛−1 ∪ �𝑥𝑥1,𝑚𝑚,1, 𝑥𝑥1,1,𝑛𝑛, 𝑥𝑥2,1,1�; 

𝛱𝛱3 = 𝛱𝛱1,𝑚𝑚,2
1,𝑚𝑚,𝑛𝑛−1 ∪ 𝛱𝛱1,2,𝑛𝑛

1,𝑚𝑚−1,𝑛𝑛 ∪ 𝛱𝛱2,2,1
2,𝑚𝑚−1,1 ∪ 𝛱𝛱2,1,2

2,1,𝑛𝑛−1; 
𝛱𝛱4 = 𝛱𝛱2,2,2

2,𝑚𝑚−1,𝑛𝑛−1 ∪ �𝑥𝑥1,𝑚𝑚,𝑛𝑛, 𝑥𝑥2,𝑚𝑚,1, 𝑥𝑥2,1,𝑛𝑛�; 
𝛱𝛱5 = 𝛱𝛱2,𝑚𝑚,2

2,𝑚𝑚,𝑛𝑛−1 ∪ 𝛱𝛱2,2,𝑛𝑛
2,𝑚𝑚−1,𝑛𝑛; 

𝛱𝛱6 = �𝑥𝑥2,𝑚𝑚,𝑛𝑛�. 
and  δ𝜑𝜑(𝑥𝑥) = 3 − 𝑚𝑚  at  𝑥𝑥 ∈ 𝛱𝛱𝑖𝑖. 
At first we will prove that 𝑥𝑥1,1,1  

𝜑𝜑
←  𝑥𝑥2,1,1, i.e., φ(𝑥𝑥2,1,1)=2. 

Let’s assume the reverse: 𝑥𝑥1,1,1  
𝜑𝜑
←  𝑆𝑆

𝜑𝜑
← 𝑥𝑥2,1,1, and  𝑆𝑆 ≠ ∅. 

Consider a case 𝑥𝑥1,𝑚𝑚,𝑛𝑛 ∉ 𝑆𝑆. We have δ𝜑𝜑(𝑆𝑆) ≤ δ𝜑𝜑�𝑥𝑥2,1,1� = 1 by the Lemma. It is easy to see 
that for every set 𝑋𝑋′: 

δ𝜑𝜑(𝑋𝑋′) =
1

|𝑋𝑋′|
� δ𝜑𝜑(𝑥𝑥).
𝑥𝑥∈𝑋𝑋′

 

As 𝜑𝜑 is concise with respect to  𝑥𝑥1,1,1, then from 𝑥𝑥1,𝑚𝑚,𝑖𝑖 ∈ 𝑆𝑆  follows  𝑥𝑥1,1,𝑖𝑖 ∈ 𝑆𝑆, where 𝑚𝑚 ∈
2, 𝑚𝑚 − 1���������� (and from 𝑥𝑥1,𝑗𝑗,𝑛𝑛 ∈ 𝑆𝑆 follows 𝑥𝑥1,𝑗𝑗,1 ∈ 𝑆𝑆, where 𝑗𝑗 ∈ 2, 𝑚𝑚 − 1�����������). Therefore, δ𝜑𝜑(𝑆𝑆) ≥ 1  and 
δ𝜑𝜑(𝑆𝑆) = 1   if and only if  

𝑆𝑆 = 𝛱𝛱1,1,1
1,𝑚𝑚,𝑛𝑛\�𝑥𝑥1,1,1, 𝑥𝑥1,𝑚𝑚,𝑛𝑛�. 

   
Let 𝑆𝑆 

𝜑𝜑
←  𝑅𝑅

𝜑𝜑
← 𝑥𝑥1,𝑚𝑚,𝑛𝑛 (obviously 𝑥𝑥2,1,1 ∈ 𝑅𝑅). Easy to see that 𝜔𝜔�𝑅𝑅, 𝑥𝑥1,𝑚𝑚,𝑛𝑛� = 0, δ𝜑𝜑�𝑥𝑥1,𝑚𝑚,𝑛𝑛� =

−1, and from the conciseness of 𝜑𝜑 we have δ𝜑𝜑(𝑅𝑅) > −1, which contradicts the Lemma. 
 Let’s now consider the case 𝑥𝑥1,𝑚𝑚,𝑛𝑛 ∈ 𝑆𝑆. Then 𝛱𝛱1,1,1

1,𝑚𝑚,𝑛𝑛  
𝜑𝜑
← 𝛱𝛱2,1,1

2,𝑚𝑚,𝑛𝑛 and the subgraphs 𝐺𝐺1, 𝐺𝐺2  
induced with them are ordered minimally at 𝜑𝜑. Really, it is easy to see that for every ordering ψ, 
for which 𝛱𝛱1,1,1

1,𝑚𝑚,𝑛𝑛  
𝜓𝜓
← 𝛱𝛱2,1,1

2,𝑚𝑚,𝑛𝑛, we will have  𝐸𝐸𝜓𝜓(𝛱𝛱2,𝑚𝑚,𝑛𝑛) = 𝑚𝑚2𝑚𝑚2 + 𝐸𝐸𝜓𝜓1(𝐺𝐺1) + 𝐸𝐸𝜓𝜓2(𝐺𝐺2), where 
 𝜓𝜓1(𝑥𝑥) = 𝜓𝜓(𝑥𝑥)  when 𝑥𝑥 ∈ 𝛱𝛱1,1,1

1,𝑚𝑚,𝑛𝑛 and 𝜓𝜓2(𝑥𝑥) = 𝜓𝜓(𝑥𝑥) − 𝑚𝑚𝑚𝑚 when  𝑥𝑥 ∈ 𝛱𝛱2,1,1
2,𝑚𝑚,𝑛𝑛. Therefore, 𝜑𝜑 ∈

𝜙𝜙P2,m,n 
𝐸𝐸   if and only if 𝜓𝜓1 ∈ 𝜙𝜙𝐺𝐺1 

𝐸𝐸  , 𝜓𝜓2 ∈ 𝜙𝜙𝐺𝐺2 
𝐸𝐸 . So 𝐺𝐺1, 𝐺𝐺2  at 𝜑𝜑 are ordered minimally. Then from 

[1] we will have the following. If m ≤ n, then 
a) at m > 4:   𝛱𝛱1,1,1

1,𝜆𝜆0,𝜆𝜆0  
𝜑𝜑
← 𝛱𝛱1,1,1

1,𝑚𝑚,𝑛𝑛\𝛱𝛱1,1,1
1,𝜆𝜆0,𝜆𝜆0  

𝜑𝜑
← 𝛱𝛱2,1,1

2,𝜆𝜆0,𝜆𝜆0, where 2 ≤ 𝜆𝜆0 <
1
2
m; 

b) at m < 4:  𝛱𝛱1,1,1
1,𝑚𝑚,1  

𝜑𝜑
← 𝛱𝛱1,1,1

1,𝑚𝑚,𝑛𝑛\𝛱𝛱1,1,1
1,𝑚𝑚,1  

𝜑𝜑
← 𝛱𝛱2,1,1

2,𝑚𝑚,1; 
c) at m = 4:  the case а) or b) is happened. 
 
It is not difficult to compute: 

δ𝜑𝜑 �𝛱𝛱1,1,1
1,𝑚𝑚,𝑛𝑛\𝛱𝛱1,1,1

1,𝜆𝜆0,𝜆𝜆0� =
𝑚𝑚𝑚𝑚 − 𝜆𝜆02 − 2𝜆𝜆0

𝑚𝑚𝑚𝑚 − 𝜆𝜆0
2 = 1 −

2𝜆𝜆0
𝑚𝑚𝑚𝑚 − 𝜆𝜆0

2 > 0; 



Linear Orderings of Tridimensional Grids 90 

δ𝜑𝜑 �𝛱𝛱2,1,1
2,𝜆𝜆0,𝜆𝜆0� =

2𝜆𝜆0 − 𝜆𝜆02

𝜆𝜆0
2 =

2
𝜆𝜆0
− 1 ≤ 0; 

δ𝜑𝜑�𝛱𝛱1,1,1
1,𝑚𝑚,𝑛𝑛\𝛱𝛱1,1,1

1,𝑚𝑚,1� =
𝑚𝑚(𝑚𝑚 − 1) − 𝑚𝑚
𝑚𝑚(𝑚𝑚 − 1)

=
𝑚𝑚 − 2
𝑚𝑚 − 1

> 0; 

δ𝜑𝜑�𝛱𝛱2,1,1
2,𝑚𝑚,1� = 0. 

The last relations obviously contradict the Lemma. Therefore, 𝑥𝑥1,1,1  
𝜑𝜑
←  𝑥𝑥2,1,1. 

Now let’s show, that 𝑥𝑥1,𝑖𝑖,𝑗𝑗  
𝜑𝜑
←  𝑥𝑥2,𝑖𝑖,𝑗𝑗  for each i,j (𝑚𝑚 ∈ 1, 𝑚𝑚�����; 𝑗𝑗 ∈ 1, 𝑚𝑚������). We will say that the 

vertices 𝑥𝑥1,𝑖𝑖,𝑗𝑗, 𝑥𝑥2,𝑖𝑖,𝑗𝑗 are neighbors.   
Let’s assume the reverse. Let z be a vertex with the smallest number, which does not directly 

goes behind its neighbor (denote the latter by y). 
So we have 𝑦𝑦 

𝜑𝜑
←  𝑆𝑆

𝜑𝜑
←  𝑧𝑧;   S ≠ ∅; δ𝜑𝜑(𝑦𝑦) = δ𝜑𝜑(𝑧𝑧) + 2. 

By the definition of z every vertex from 𝛱𝛱2,1,1
2,𝑚𝑚,𝑛𝑛⋂𝑆𝑆 directly goes behind its neighbor. Let  

�𝛱𝛱2,1,1
2,𝑚𝑚,𝑛𝑛⋂𝑆𝑆 � = 𝑘𝑘  and 𝑦𝑦 

𝜑𝜑
←  𝑀𝑀1

𝜑𝜑
← 𝑁𝑁1

𝜑𝜑
← …  

𝜑𝜑
←  𝑀𝑀𝑘𝑘

𝜑𝜑
← 𝑁𝑁𝑘𝑘  

𝜑𝜑
←  𝑀𝑀𝑘𝑘+1

𝜑𝜑
←  𝑧𝑧, where 𝑁𝑁𝑖𝑖 − one pair of 

neighbors, and 𝑀𝑀𝑗𝑗 ⊂ 𝛱𝛱1,1,1
1,𝑚𝑚,𝑛𝑛. Then as  𝜑𝜑 is concise, we have 

𝜔𝜔(𝑆𝑆, 𝑧𝑧) = 0;   𝜔𝜔(𝑦𝑦, 𝑁𝑁𝑖𝑖) = 0;   𝜔𝜔( 𝑀𝑀𝑖𝑖, 𝑁𝑁𝑖𝑖) = 0,                                            (1) 
at  1 ≤i ≤ j ≤ k. 

Notice, that y and S cannot be independent of one another. Otherwise, by the Lemma we 
would have δ𝜑𝜑(𝑦𝑦) ≤ δ𝜑𝜑(𝑆𝑆) ≤ δ𝜑𝜑(𝑧𝑧)  which would contradict the relation δ𝜑𝜑(𝑦𝑦) = δ𝜑𝜑(𝑧𝑧) + 2. 
Therefore: ⋃𝑀𝑀𝑖𝑖≠ ∅. 

Let’s show, that δ𝜑𝜑(𝑆𝑆) > −1. Let’s assume the reverse: δ𝜑𝜑(𝑆𝑆) ≤ −1 . Then, as δ𝜑𝜑(𝑁𝑁𝑖𝑖) ≥
−1  for every 𝑚𝑚 ∈ 1, 𝑘𝑘�����, then ⋃𝑀𝑀𝑖𝑖  consists of a unique vertex  𝑥𝑥1,𝑚𝑚,𝑛𝑛. Since  𝜔𝜔(𝑦𝑦, 𝑆𝑆) ≠ 0 , then 
by (1) we will have  𝑦𝑦 ∈ 𝛱𝛱3. Therefore, δ𝜑𝜑(𝑧𝑧) = −2. But from the conciseness of 𝜑𝜑 we can 
conclude, that  𝑥𝑥1,𝑚𝑚,𝑛𝑛  

𝜑𝜑
←𝑧𝑧 , which contradicts the Lemma. From δ𝜑𝜑(𝑆𝑆) > −1  we have δ𝜑𝜑(𝑧𝑧) =

0  (δ𝜑𝜑(𝑦𝑦) = 2). Notice, that δ𝜑𝜑(𝑁𝑁𝑖𝑖)  takes values from {-1;0;1}. Let’s assume, that δ𝜑𝜑(𝑁𝑁𝑖𝑖) ≥ 0  
for each 𝑚𝑚 ∈ 1, 𝑘𝑘�����. Then it is easy to see, that δ𝜑𝜑(𝑆𝑆) > 0, which is not possible by the Lemma. 
Therefore, there would be 𝑁𝑁𝑖𝑖, for which  δ𝜑𝜑(𝑁𝑁𝑖𝑖) = −1.  

Let  𝑁𝑁𝑝𝑝 be a pair with the smallest index from {𝑁𝑁𝑖𝑖}𝑖𝑖=1,𝑘𝑘���� , for which δ𝜑𝜑(𝑁𝑁𝑖𝑖) = −1. We have 
p ≥ 1 . We will prove by induction that  𝑀𝑀𝑖𝑖 = ∅  for all  𝑚𝑚 ∈ 2, 𝑝𝑝�����.  

Really,  𝑀𝑀𝑝𝑝 = ∅    by the Lemma and (1). Let the sets  𝑀𝑀𝑖𝑖+1, 𝑀𝑀𝑖𝑖+2, … , 𝑀𝑀𝑝𝑝  be empty. We 
have  

 𝑀𝑀𝑖𝑖  
𝜑𝜑
← ⋃ 𝑁𝑁𝑗𝑗

𝑝𝑝
𝑗𝑗=𝑖𝑖+1 ;   δ𝜑𝜑(𝑀𝑀𝑖𝑖)≥0;  δ𝜑𝜑�⋃ 𝑁𝑁𝑗𝑗

𝑝𝑝
𝑗𝑗=𝑖𝑖+1 � < 0, 

and by the Lemma we will have  𝑀𝑀𝑖𝑖 = ∅ . Then  𝑦𝑦 
𝜑𝜑
←  𝑀𝑀1 

𝜑𝜑
←⋃ 𝑁𝑁𝑗𝑗

𝑝𝑝
𝑗𝑗=1 . But  δ𝜑𝜑(𝑦𝑦⋃𝑀𝑀1) > 0 ,  

δ𝜑𝜑�⋃ 𝑁𝑁𝑗𝑗
𝑝𝑝
𝑗𝑗=1 � < 0, which contradicts the Lemma. Thus, we obtained that  𝑥𝑥1,𝑖𝑖,𝑗𝑗  

𝜑𝜑
←  𝑥𝑥2,𝑖𝑖,𝑗𝑗 for each 

i,j (𝑚𝑚 ∈ 1, 𝑚𝑚�����; 𝑗𝑗 ∈ 1, 𝑚𝑚������), i.e., vertices of 𝐺𝐺1 got odd numbers, while the vertices of 𝐺𝐺2 – even 
numbers.  
 Let’s define layouts 𝜑𝜑1 and 𝜑𝜑2 for the graphs 𝐺𝐺1, 𝐺𝐺2: 

𝜑𝜑1�𝜑𝜑−1(2𝑘𝑘 − 1)� = 𝑘𝑘;     𝜑𝜑2�𝜑𝜑−1(2𝑘𝑘)� = 𝑘𝑘; 
For each ∈ 1, 𝑚𝑚𝑚𝑚������� . Then it is easy to see, that      

𝐸𝐸𝜑𝜑(𝑃𝑃2,𝑚𝑚,𝑛𝑛) = 𝑚𝑚𝑚𝑚 + 2𝐸𝐸𝜑𝜑1(𝐺𝐺1) + 2𝐸𝐸𝜑𝜑2(𝐺𝐺2).                                  (2) 
 Therefore, 𝜑𝜑 is minimal if and only if 𝜑𝜑 ∈ 𝜙𝜙𝐺𝐺𝑖𝑖

𝐸𝐸   (𝑚𝑚 ∈ 1,2����). 
This proves the theorem. Substituting the formula of 𝐸𝐸(𝐺𝐺𝑖𝑖) from [1] into (2), at m ≤ n we will 
have: 



 

D. Muradian    91 

𝐸𝐸𝜑𝜑(𝑃𝑃2,𝑚𝑚,𝑛𝑛) = 𝑚𝑚𝑚𝑚 + 4 �−
2
3
𝜆𝜆0
3 + 2𝑚𝑚𝜆𝜆02 − �𝑚𝑚2 + 𝑚𝑚 −

2
3
�𝜆𝜆0 + 𝑚𝑚(𝑚𝑚2 + 𝑚𝑚 − 1) − 𝑚𝑚�, 

 

where      �𝑚𝑚 − �𝑚𝑚
2

2
− 𝑚𝑚

2
+ 1

4
� ≤ 𝜆𝜆0 ≤ �𝑚𝑚 +

1
2
− �𝑚𝑚

2

2
− 𝑚𝑚

2
+ 1

4
�. 

 
 
References 
1. D. O. Muradian and T. E. Piliposyan, “Minimal numberings of vertices of a rectangular 
lattice”, Akad. Nauk. Armjan.SSR 1, In Russian, vol.70, pp. 21-27,  1980.  
 
 
Submitted 07.07.2016, accepted  26.10.2016. 
 

 
Գծային համարակալումներ եռաչափ ցանցերի համար 

 
Դ. Մուրադյան 

 
Ամփոփում 

 
Գրաֆի մինիմալ համարակալում գտնելու խնդիրը սահմանվում է հետևյալ 

կերպ: Պահանջվում է գտնել տրված գրաֆի գագաթների այնպիսի տեղաբաշխում 
թվային առանցքի վրա, որ էջերի երկարությունների գումարը լինի նվազագույն, 
որտեղ էջի երկարությունը նրան կից գագաթների համարների տարբերության 
բացարձակ արժեքն է: Այս աշխատանքում նկարագրվում է մինիմալ 
համարակալումների դասը եռաչափ ցանցերի մի մասնավոր դեպքի՝ երեք պարզ 
շղթաների դեկարտյան արտադրյալի համար, որոնցից մեկն ունի երկու գագաթ: 

 
 

Линейные нумерации трехмерных решеток  
 

Д. Мурадян 
 

Аннотация 
 

В работе описывается класс минимальных по длине нумераций частного случая 
трехмерных решеток – декартого произведения трех простых цепей, когда один из них 
состоит из двух вершин. Минимальная длина нумерациия графа определяется 
следующим образом: для данного графа G требуется найти такую линейную 
нумерацию его вершин, чтобы сумма длин ребер (абсолютное число разности номеров 
инцидентных ей вершин) была минимальна относительно всевозможных нумераций 
графа.  

 


	1. Introduction
	References