Citation
Packing of 2-dimension and 3-dimension grid graphs

Material Information

Title:
Packing of 2-dimension and 3-dimension grid graphs
Creator:
Grant, Deborah T
Publication Date:
Language:
English
Physical Description:
50 leaves : ; 28 cm

Subjects

Subjects / Keywords:
Graph theory ( lcsh )
Algorithms ( lcsh )
Algorithms ( fast )
Graph theory ( fast )
Genre:
bibliography ( marcgt )
theses ( marcgt )
non-fiction ( marcgt )

Notes

Bibliography:
Includes bibliographical references (leaf 50).
General Note:
Department of Mathematical and Statistical Sciences
Statement of Responsibility:
by Deborah T. Grant.

Record Information

Source Institution:
University of Colorado Denver
Holding Location:
Auraria Library
Rights Management:
All applicable rights reserved by the source institution and holding location.
Resource Identifier:
40462273 ( OCLC )
ocm40462273
Classification:
LD1190.L622 1998m .G73 ( lcc )

Downloads

This item has the following downloads:


Full Text
PACKING OF 2-DIMENSION AND 3-DIMENSION
GRID GRAPHS
by
Deborah T. Grant
B.B.A., Southern Methodist University, 1977
A thesis submitted to the
University of Colorado at Denver
in partial fulfillment
of the requirements for the degree of
Master of Science
Applied Mathematics
1998


This thesis for the Master of Science
degree by
Deborah T. Grant
has been approved
by
David C. Fisher
fn-t?
Date


Grant, Deborah T. Grant (M.S., Applied Mathematics)
Packing of 2-Dimensional and 3-Dimensional Grid Graphs
Thesis directed by Professor David C. Fisher
ABSTRACT
A packing S' of a graph G is a set of nodes such that every pair of
nodes in S is more that two apart. The packing number P(G) is the maximum
size of a packing of G. What is the maximum size of a packing of an to x n
grid graph? Through ad hoc methods, Dr. David Fisher answered this for all
to and n. Using max-plus algebra, an algorithm is developed to determine the
solution to this question. This algorithm is designed to be easily modified to
answer other packing questions.
This abstract accurately represents the content of the candidates thesis. I
recommend its publication.
m
Signed
David C. Fisher


ACKNOWLEDGEMENTS
My sincere thanks to my husband, Kerry; my sons, Ryan and Connor;
and my parents, Charles and Bobbie Temple. Without their loving support,
kindness and encouragement, I would not have been able to complete this goal.
IV


CONTENTS
Chapter
1. Introduction.................................................. 1
2. Max-Plus Algebra............................................. 2
3. Finding a Packing Number for a 3 x n Grid Graph.............. 4
4. Size of Vector.............................................. 11
5. Decoding a Specific Packing State........................... 18
6. Encoding a Specific Packing State........................... 28
7. Conclusions for 2-Dimensional Grid Graphs................... 34
8. Developing a Transfer Matrix for a 3-D Packing.............. 38
8.1 Determining the Vector States for a 3-D Grid Graph ... 40
8.2 Decoding a 3-D Packing.................................. 42
8.3 Encoding a 3-D Packing.................................. 45
9. Conclusions for 3-Dimensional Grid Graph ................... 48
References....................................................... 50
v


FIGURES
e
.. 1 An example of a valid packing for a 4 x 3 grid graph....... 1
1.1 All valid packings for a 3 x 1 grid graph.................. 4
5.2 The nine valid packings for a 3 x 2 grid graph developed
from the 3x1 grid graph.................................... 5
1.3 Transfer Matrix A for a 3 x n grid graph........'.......... 9
.1 Transfer Matrix A for a 2 x 2 grid graph..................... 11
.2 Summing the elements of each vector state will give the num-
ber of packings for an 2 x n grid graph................. 12
.3 Transfer Matrix A for 3 x 2 grid graph where = 1 for
valid packings and = 0 otherwise......................... 14
.4 Summing the elements of each vector state will give the num-
ber of packings for an 3 x n grid graph................. 15
.1 Vectors associated with a 2 x 6 grid graph derived from max-
plus algebra............................................... 19
vi


5.2 Transfer Matrix for 2 x 2 grid graph. The third row corre-
sponds to the 3rd element of the vector. The beginning of the
packing is the packing of the 3rd row. To continue the trace
back, consider the valid packings in the 1st and 4th column. . 20
5.3 Same vectors associated with a 2 x 6 grid graph showing the
traceback for the vector..................................... 21
5.4 Transfer Matrix for 2 x 2 grid graph. The first row corre-
sponds to the 1st element of the x5 vector. The 1st row is
attached to the front of the packing. To continue the trace
back, consider the valid packings in the 1st, 2nd and 4th
columns........................................................ 22
5.5 Same vectors associated with a 2 x 6 grid graph showing the
traceback for the vector. . ................................. 23
5.6 Transfer Matrix for 2 x 2 grid graph. The second row cor-
responds to the 2nd element of the x4 vector. The 2nd row is
attached to the front of the packing. To continue the trace-
back, consider the valid packings in the 3rd column......... 23
5.7 Same vectors associated with a 2 x 6 grid graph showing the
traceback for the x3 vector.................................. 24
Vll


5.8 Transfer Matrix for 2 x 2 grid graph. The third row corre-
sponds to the 3rd element of the X3 vector. The 3rd row is
attached to the front of the packing. To continue the trace-
back, consider the valid packings in the 1st and 4th columns. . 25
5.9 Same vectors associated with a 2 x 6 grid graph showing the
traceback for the x2 vector............................... 26
5.10 Transfer Matrix for 2 x 2 grid graph. The fourth row corre-
sponds to the 4th element of the x2 vector. The 4th row is
attached to the front of the packing................... 26
5.11 The 31st packing state for a 2 x 6 grid graph................ 27
6.1 A packing configuration for a 2 x 6 grid graph................ 28
6.2 The transfer matrix for a 2 x 2 grid graph. Row 2 corresponds
to the last 2 columns of the packing configuration given. ... 29
6.3 The associated vectors for the 2x6 grid graph............... 29
6.4 The transfer matrix for a 2 x 2 grid graph. Row 2 corresponds
to the 5th and Qth columns of the packing configuration given.
To continue tracing forward, consider the only valid column
which is the 3rd column................................ 30
Vlll


6.5 The transfer matrix for a 2 x 2 grid graph. Row 3 corresponds
to the 4th and 5th columns of the packing configuration given.
The only valid columns are the ls£ and 4th columns......... 31
6.6 The transfer matrix for a 2 x 2 grid graph. Row 4 corresponds
to the 3rd and 4th columns of the packing configuration given.
The only valid packings is in the 5th column............... 32
6.7 The transfer matrix for a 2 x 2 grid graph. Row 5 corresponds
to the 2nd and 3rd columns of the packing configuration given.
Valid packings are in the 1st and 2nd columns................. 33
8.1 The valid packings for a 2 x 2 x 2 grid graph................. 38
8.2 Transfer Matrix A developed for a 2 x 2 x 2 grid graph. ... 39
8.3 Transfer Matrix A developed for a 2 x 2 x 2 grid graph where
a,ij 1 for valid packings and a^- = 0 otherwise.......... 41
8.4 Summing the elements of each vector state will give the num-
ber of packings for an 2 x 2 x n grid graph............... 42
8.5 Vectors associated with a 2 x 4 x 2 grid graph derived from
max-plus algebra........................................... 43
8.6 Transfer Matrix A developed for a 2 x 2 x 2 grid graph where
a,ij = 1 for valid packings and a^- = 0 otherwise............. 44
8.7 The 77th packing state of a 2 x 4 x 2 grid graph.............. 45
IX


8.8 A packing configuration of a 2 x 4 x 2 grid graph.
45
8.9 Transfer Matrix A developed for a 2 x 2 x 2 grid graph where
dij = 1 for valid packings and 0 otherwise.............. . 46
8.10 Vectors associated with a 2 x 4 x 2 grid graph derived from
max-plus algebra........................................... 47
x


TABLES
Table
4.1 This table shows the number of packings for 1 x n, 2 x n, and
3 x n grid graphs. Note: by adding = 1 in the transfer
matrix for a 2 x n grid graph will give the total number of
packings for a 3 x n grid graph.............................. 17
7.1 This table shows the solutions for m x n grid graph with to < 7 36
7.2 This table shows the solutions for m x n grid graph made
by Fisher.................................................... 37
9.1 This table shows the solutions for l x m x n grid graph
(l < 3 and m < 5)............................................ 48
9.2 This table shows the solutions for l x m x n grid graph
(l < 3 and m < 5)............................................ 49
xi


1. Introduction
A packing S of a grid graph G is a set of nodes such that every pair of
nodes in S is more than two apart. The packing number P(G) is the maximum
size of a packing of G. Below is an example of a 4 x 3 grid graph (see Figure
1.1). The packing number for this example is 3.
J t


Figure 1.1. An example of a valid packing for a 4 x 3 grid graph.
Through ad hoc methods, Fisher determined the maximum size of a
packing of an m x n grid graph. Using max-plus algebra, this paper presents
an algorithm to determine the solution to this question. This algorithm is also
designed to be easily modified to answer other packing questions.
1


2. Max-Plus Algebra
Max-plus algebra is similar to matrix multiplication but replaces ad-
dition (+) with maximization () and multiplication (x) with addition () .
The properties of max-plus algebra are:
An identity e for has the property that a e = a for all a.
Translating into regular notation, this is max (a, e) = a. This is true only
if e < a for all a. To have an identity for and to have the algebra in-
clude all real numbers, then oo must be added to the real numbers. Let
SR_ = 5? U oo. When adding an element, the operations must be defined. So
Va 6 5R_, let co a = a co = a and oo a = a oo = co. Then
for all a, b, c G 5ft-, the following properties are defined.
(Commutative) (i.e., a b b a.(i.e., max (a, b) = max (b, a) and
(i.e., ab = b a)(i.e., a + b = b + a);
(Associative) (i.e., a (6 c) = (a b) c
(i.e., max (a, max (b, c) = max (max (a, b), c)) and a (b c) = (ab) c
(i.e., a + (b + c) = (a + b) + c);
(Distributive) a (b c) = (a b) (a c)
(i.e., a + (max (b, c) = max (a + b,a + c));
2


(Identity) oo a = a (i.e., max (00, a) = a), and 0 0 a = a
(i.e., 0 + a = a);
(One inverse) a a = 0 (i.e., -a + a = 0);
(Consistency of identities) 00 <8> 0 = 00; and
(Idempotent) a a = a (i.e., max (a, a) = a).
An example of max-plus algebra is given below.
5 7 2 6 (5 6) (7 1) (2 0 4)
8 8 6 1 = (8 0 6) 0 (8 0 1) (6 4)
9 5 5 4 (9 0 6) (5 1) (5 4)
max (5 + 6, 7+1, 2 + 4) 11
max (8 + 6, 8 + 1, 6 + 4) - - 14
max (9 + 6, 5 + 1, 5 + 4) 15
3


3. Finding a Packing Number for a 3 x n Grid Graph
One application for max-plus algebra is to find the packing number
of an m x n grid graph. Fisher found the packing number of an m x n grid
graph for all m and n; however, the techniques used there were specific to his
problem. Using max-plus algebra, packing problems can be solved by finding
the packing number of a 3 x n grid for all n in finite time. First, consider all
of the packings for a 3 x 1 grid graph (see Figure 3.1).
A
Figure 3.1. All valid packings for a 3 x 1 grid graph.
Clearly, there are four possible packings for a 3 x 1 grid. By building
from the 3x1 grids, all of the 3x2 grids can be created simply by adding
an additional column and eliminating any packing violations. There are nine
packings for a 3 x 2 grid (see Figure 3.2).
4


Figure 3.2. The nine valid packings for a 3 x 2 grid graph
developed from the 3x1 grid graph
A vector of length 9 can be created from the number of nodes in a
packing of a 3 x 2 grid. Let Xk be a vector of length 9 whose ith component is
the maximum number of nodes in a packing of a 3 x n grid whose rightmost
two columns are the same as the ith packing found above. Thus, the entries in
x2 are the number of nodes in the relevant packing.
5


x2 =
0
1
1
1
1
2
1
1
2
The ith entry of a;3 is the maximum number of nodes in a packing of
a 3 x 3 grid with the second and third column in the ith state. So, for example,
the first entry of £3 is 1, because with the second and third column as specified
(namely both columns empty), the first column can have at most one node.
However, the second entry is 2, because with the second column empty and
the third column with one node at the top row, the first column can have at
most one node. This gives a total of two nodes.
6


1
2
2
2
^3
2
2
1
2
2
Thus, a dynamic programming algorithm can be developed as follows:
xn+i(l) = 0 + max(xn(l),xn(5),xn(7), xn(8))
*xn+l(2) l + max(xn(l),xn(7),xn(8))
^n+i(3) = 1 + max(xn(l),xn(5),xn(8))
a;n+1(4) = 1 + max(xn(l),xn(5),xn(7))
rrn+1(5) = 0 + max(xn( 2), :rn(9))
zn+i(6) = 1 + max(xn( 2))
9Xn+i(7) 0 + max(xn{8))
oa;n+1(8) = 0 + maa:(a:n(4), a;n(6))
a:n+i(9) = 1 + max(xn( 4))
For example xn+i (5) is the fifth packing configuration
7


n n +1
O
O O
O O
which has 0 nodes in the n + 1 column merges either with xn(2)
n 1 n
O
O O
O O
or xn(9).
n 1 n
O
O O
O
This algorithm can be developed into the following transfer matrix
A using the 9 configurations of a 3 x 2 grid (see Figure 3.3). The states
across the top are configurations of columns n 1 and n. The states down
the left side are configurations of columns n and n+1. The ij entry of A is:
the number of nodes in column n + 1 on the left side
if column n on the top and column n on the left matches
and there is no packing violation,
oo otherwise.
Let denote oo for ease of reading.
8


a-1 a
OO o OO OO
OO OO 0 OO
a n+ I OO OO OO 0
OO 00 00 _0
O OO 00 1 - - -
OO 0 OO 1 - - -
OO
OO 0 1
0 0
OO OO - -
0
OO 0 1
OO 0
o OO
OO
OO o 0
0
OO o - - - 1
0 o OO 00 0
OO OO 0 00 00
OO 09 00 0 90
0 ' 0 0
- - 1 1 -
1 - - 1 -
1 - 1 - -
- - - - 0
- - - - -
- - - - -
- 0 - - -
Figure 3.3. Transfer Matrix A for a 3 x n grid graph
With vector states as follows:
x2 = [0,1,1,1,1,2,1,1, 2}t, then
Z3 = Ax2 = [1,2,2, 2,2, 2,1, 2,2]r
£4 = A X3 = [2, 3,3,3,2,3, 2,2,3]T
x5 A x4 = [2,3, 3,3,3,4,3,3,4]T = 2 0 x2
Now P(Pm x -Pn) is the largest element of xn. Thus P(P3 x P3)
9


1, P(P3 X P2) = 2, P(P3 x P3) = 2, P(P3 x P4) = 3, P(P3 x P5) = 4, and
P(P3 x P6) = 4. Let y = [0, 0,0,0,0,0,0,0,0]T, then P(Pm x Pn) can be ex-
pressed with max-plus algebra as
P(P3 x Pn) = max(a;n(l)>...,icn(9)) =yTxn
Lemma 1 P(P3 x Px) = 1, P(P3 x P2) = 2, P(P3 x P3) = 2, P(P3 x P4) = 3,
P(P3 x P5) = 4, P(P3 x P6) = 4.
Theorem 1 P(P3 x P) = [y1]
Proof (by induction): Notice this is true for n = 1,2, 3. For n > 3, assume
p(p4 x pn_3) = r^i = rf-2i = rfi-2- Tlien> p{p^Pn)=vTxn =
yT(2 x_3) = 2 (yT z_3) = 2 + P(P4 x Pn_3) = 2 + - 2 = [2p]
10


4. Size of Vector
How many packing configurations are there for a m x 2 grid graph?
a m x 3 grid graph? a m x 4 grid graph? We can get these results by looking
at the transfer matrix of a 2 x 2 grid graph (see Figure 4.1) with
a,ij = 1 if there is a valid packing
ciij = 0 otherwise.
a 2 x 2 grid graph are the
n-1 n oo oo oo o o
n n+l oo o o oo oo
OO oo 1 1 0 1 0
o oo 0 0 1 0 0
o oo 1 0 0 1 0
o oo 0 0 0 0 1
o oo 1 1 0 0 0
Figure 4.1. Transfer Matrix A for a 2 x 2 grid graph.
Let x2 be a vector with 5 elements of 1 where each element represent
one of the five packing configurations of a 2 x 2 grid graph. By max-plus
matrix multiplication (A <8> x2), then additional vector states can be found.
11


Summing the components of each vector state derived will give the number of
packings for each 2 x n grid graph (See Figure 4.2).
i -i r- |
1 3 5 9 17
1 1 2 4 7
1 X = 3 2 X = 4 4 X = 5 7 X = 6 13
1 1 2 4 7
1 2 4 7 13

# of packings for an
2 x n grid graph 5 9 17 31 57
n = 2 n = 3 n = 4 n = 5 n = 6
Figure 4.2. Summing the elements of each vector state will give
the number of packings for an 2 x n grid graph.
Notice that there are 57 different packings for a 2 x 6 grid graph.
Vector xG indicates that there are 17 of these packings ending like this:
? ? ? ?o O
? ? ? ?o O
7 packings ending like this:
? ? ? ?o O
? ? ? ? O
13 packings ending like this:
? ? ? ?o O
? ? ? ? O
12


7 packings ending like this:
? ? ? ? O
? ? ? ?o o
and 13 packings ending like this:
? ? ? ?o
? ? ? ?o O
Now consider a transfer matrix for a 3 x 2 grid graph (see Figure 4.3)
with
oa,ij = 1 if there is a valid packing
aij = 0 otherwise.
13


n*l n
oo o oo oo o o oo oo o
oo oo o oo oo oo @o oo oo
n n+1 oo oo oo oo o oo o@ oo o o
oo oo 1 0 0 0 1 0 1 1 0
o
oo oo 1 0 0 0 0 0 1 1 0
oo
o oo 1 0 0 0 1 0 0 1 0
oo
oo o 1 0 0 0 1 0 1 0 0
oo oo o 0 1 0 0 0 0 0 0 1
o 0
oo o 1 0 0 0 0 0 0 0
oo
o oo 0 0 1 0 0 0 0 0 0
oo
oo o 0 0 0 1 0 1 0 0 0
o oo @0 0 0 0 1 0 0 0 0 0
Figure 4.3. Transfer Matrix A for 3 x 2 grid graph where
ciij = 1 for valid packings and = 0 otherwise.
Again, summing the components of each vector state derived from
max-plus algebra gives the numbers of packings for each 3 x n grid graph.
14


1 4 9 20
1 3 7 16
x2 = 1 X = 3 3 X = 4 8 X = 5 17
1 3 7 16
1 2 4 10
1 1 3 8
1 2 4 10
1 1 3 7
1 1 . 3 7
# of packings for an
3 x n grid graph 9 20 48 111
n = 2 n = 3 n = 4 n=5
Figure 4.4. Summing the elements of each vector state will give
the number of packings for an 3 x n grid graph.
Since the transfer matrix is always a square matrix, then each term in
the expansion of the determinant is a product of n entries containing exactly
one entry from each row and column. Thus, a characteristic polynomial p(X) of
the transfer matrix is obtained. For example, for a 1 x 2 grid graph, there are
clearly three packing solutions which gives the following 3x3 transfer matrix
A.
n n+1 n-1 n oo o o
oo 1 1 0
o 0 0 1
o 1 0 0
The characteristic equation (p(A) = 0) of A is
15


A 1 1 0
p(A) = det (A/3 A) = det
0 A -1
= A3A21 = 0 or A3 = A2+l.
-1 0 A
From the characteristic polynomial of each transfer matrix we can
determine the number of packings (an) for an m x n grid graph. Continuing
with the same example, the number of packings for a 1 x 3 grid graph (a3) is
a3 = a2 + 1. In other words, the number of packings for a 1 x 3 grid graph
equals the number of packings for a 1 x 2 grid graph (3) plus 1. Therefore, the
number of packings for a 1 x 3 grid graph is 4.
The recursive equations developed from the characteristic polynomi-
als are below:
1 x n: For n > 4, an = an_x + an_3
2 x 7i. For ?7. 6, cin dyii -1- 23 -{- 4 -|- 5
3 x 71. For 71 10, dn dyii T 5nyl_3 T 3q.^_4 T 5dn3 4- 2un__g U719
The following table shows the number of packings found using these
equations.
16


n no. of packings for 1 x n no. of packings for 2 x n no. of packings for 3 x n
1 2 3 4
2 3 5 9
3 4 9 20
4 6 17 48
5 9 31 111
6 13 57 259
7 19 79 605
8 28 241 1410
Table 4.1. This table shows the number of packings for 1 x n,
2 x n, and 3 x n grid graphs. Note: by adding ai;?- = 1 in the
transfer matrix for a 2 x n grid graph will give the total number
of packings for a 3 x n grid graph.
The eigenvalues are the real roots of the characteristic polynomial
(p( A) = 0) derived from each transfer matrix. The eigenvalue(s) for the 2xn
matrix determines the storage space needed (an = 0(An) where A is the largest
possible root at A3 = A2+1(A = 1.829) and the eigenvalue(s) for the 3xn matrix
determines the amount of work per iteration (an = 0(An) where A = 2.340).
17


5. Decoding a Specific Packing State
Given a specific packing state for an m x n grid graph, can we de-
termine a related packing configuration? Since each state is represented in
the vector (xn) of a transfer matrix for a m x n grid graph, then the packing
configuration can be determined by decoding or tracing back through the
vector states.
An example of decoding a packing state is given below beginning with
Figure 5.1.
What is state 31 out of 57 for a 2 x 6 grid graph? We must first
consider the associated vectors.
For a 2 x n grid graph, start the traceback with the associated nth
vector. Thus, for a 2 x 6, consider the vector xq and note that state 31 can
not be in the first or second elements of vector xq since they only hold the first
17 and 7 states, respectively.
18


~1 | | [ | i i- |
1 3 5 9 17
1 1 2 4 7
1 *X = 3 2 X = 4 4 X = 5 7 X = 6 13
1 1 2 4 7
1 2 4 7 13
Figure 5.1. Vectors associated with a 2 x 6 grid graph derived
from max-plus algebra.
Therefore, state 31 must be in the third element (see Figure 5.1),
which corresponds to the third packing configuration and thus, the third row
of the transfer matrix for a 2 x 2 grid graph (see Figure 5.2).
f
19


Transfer Matrix
n-l n
oo oo oo o o
n n+1 oo o o oo oo
OO oo 1 1 0 1 0
Developing oo 0 0 1 0 0
Packing State 6
o oo oo 1 0 0 1 0
o
o oo 0 0 0 0 1
0 oo 1 1 0 0 0
Figure 5.2. Transfer Matrix for 2 x 2 grid graph. The third row
corresponds to the 3rd element of the vector. The beginning of
the packing is the packing of the 3rd row. To continue the trace
back, consider the valid packings in the 1st and 4th column.
Note, the only valid packings for row 3 are in column 1 and column 4.
Thus, the 13 states in the 3rd element of xq must be in columns 1 and 4 of row
3 of the transfer matrix. This corresponds to elements 1 and 4 in vector x5.
Tracing back to vector x5, state 31 must be in the first element since there are
9 states in this element (see Figure 5.3) and there are 7 states left. (Note: since
element 3 in x§ contained more states (13) than were left (7), no subtraction
is performed. In other words, no subtraction is performed in the element in
which the state is found.)
20


1 3 5 10 17
1 1 2 4 7
1 X = 3 2 X = 4 4 X = 5 7 x 13
1 1 2 4 7
1 2 4 7 13
Figure 5.3. Same vectors associated with a 2 x 6 grid graph
showing the traceback for the vector.
This corresponds to the first row of the transfer matrix. Now, the left
hand column of the configuration is attached to the left side of the packing
(see Figure 5.4).
21


Transfer Matrix
0-1 D
ooirool oo o o
OO 90 O lool OO
Developir
Packing 5
oo
ooo
o 1 0 0 10
So 0 0 0 o 1
oo 1 1 0 0 0
Figure 5.4. Transfer Matrix for 2 x 2 grid graph.. The first row
corresponds to the 1st element of the X5 vector. The 1st row is
attached to the front of the packing. To continue the trace back,
consider the valid packings in the 1st, 2nd and 4th columns.
The only valid packings in row 1 are in column 1, column 2, and
column 4. (see Figure 5.4). Tracing back to X4, the packing state must be in
the second element of the vector since there are 7 states left (See Figure 5.5).
22


X, =
Figure 5.5. Same vectors associated with, a 2 x 6 grid graph
showing the traceback for the vector.
This corresponds to the second row of the transfer matrix (see Figure
5.6). Again, attach the left side column of the configuration to the packing.
Transfer Matrix
Developing
Packing State
n n+1 OO OO OO 0 00 0 o 00 0 00
OO OO 1 1 0 1 0
O OO 0 0 1 0 0
OO 00 1 0 0 1 0
@0 OO 0 0 0 0 1
0 OO 1 1 0 0 0
Figure 5.6. Transfer Matrix for 2 x 2 grid graph. The second
row corresponds to the 2nd element of the 24 vector. The 2nd
row is attached to the front of the packing. To continue the
traceback, consider the valid packings in the 3rd column.
23


The only valid packing in row 2 is in column 3. Tracing back to vector
X3, the packing state must be in the third element of the vector (see Figure
5.7). (recall that there is no subtraction if the state is in the current element).
1 3 5 9 17
1 1 2 4 7
1 X = 3 E = 4 4 / x = / 5 7 x 13
1 1 2 4 7
1 2 4 7 13
Figure 5.7. Same vectors associated with a 2 x 6 grid graph
showing the traceback for the X3 vector.
This corresponds to the third row of the transfer matrix and the left
hand column of the configuration is attached in the packing (see Figure 5.8).
24


Transfer Matrix
n-1 o
OO OO 00 0 0
n n+1 OO 0 0 00 00
OO OO 1 1 0 1 0
Developing Packing State OO 0 0 0 1 0 0
00 000 0 OO 1 0 0 1 0
0 00
0 OO 0 0 0 0 1
0 OO 1 1 0 0 0
Figure 5.8. Transfer Matrix for 2 x 2 grid graph. The third row
corresponds to the 3rd element of the x3 vector. The 3rd row is
attached to the front of the packing. To continue the traceback,
consider the valid packings in the 1st and 4th columns.
The only valid packings in row 3 are in column 1 and column 4.
Finally, tracing back to vector X2, the packing state must be in the fourth
element of the vector since there are only two states left (see Figure 5.9).


Figure 5.9. Same vectors associated with a 2 x 6 grid graph
showing the traceback for the x2 vector.
This corresponds to the fourth row of the transfer matrix and the left
side column of the configuration is attached to the packing (see Figure 5.10).
Transfer Matrix
0-1 0
oo oo oo o o
D n+1 oo @o o oo oo
Developing OO oo 1 1 0 1 0
Packing State oo o 0 0 1 0 0
o oooo o oo 1 0 0 1 0
oo oo
o oo 0 0 0 0 1
o oo 1 1 0 0 0
Figure 5.10. Transfer Matrix for 2 x 2 grid graph. The fourth
row corresponds to the 4t/l element of the x2 vector. The 4t/l row
is attached to the front of the packing.
Thus, a specific packing state is found (shown in Figure 5.11).
26


ooooo
Figure 5.11. The 31st packing state for a 2 x 6 grid graph.
27


6. Encoding a Specific Packing State
Again, since each state is represented in the vector (xn) of the transfer
matrix for a grid graph, then the vector states can be determined from the
packing configuration by encoding or tracing forward through the vector
states.
The following example demonstrates the algorithm to encode a vector
state beginning with Figure 6.1.
What is the vector state of the following 2x6 packing configuration?
Figure 6.1. A packing configuration for a 2 x 6 grid graph.
Consider the last two columns in the packing configuration (see Figure
6.1) and the pattern is found in the second row of the transfer matrix (see
Figure 6.2). This corresponds to the second element of vector xe (see Figure
6.3).


n-1 n
n n+1
oo
oo
oo
o
oo
o
@o
oo
o
oo
OO oo oo @o o
oo o o oo oo
1 1 0 1 0
0 0 1 0 0
1 0 0 1 0
0 0 0 0 1
1 1 0 0 0
Figure 6.2. The transfer matrix for a 2 x 2 grid graph. Row
2 corresponds to the last 2 columns of the packing configuration
given.
When a match is found in Xq, store all previous elements (Note: pre-
vious elements are circled in Figure 6.3.)
Figure 6.3. The associated vectors for the 2x6 grid graph.
29


The only valid packing for the row 2 of the transfer matrix is column
3 (see Figure 6.4). This corresponds to the third element in x5 (see Figure 6.3).
No other previous elements are circled.
Transfer Matrix
Packing
Configuration
oo o
oo o
loo
o
n-1 n
n n+1 oo oo oo o oo o o oo o oo
OO OO 1 1 0 1 0
o oo 0 0 1 0 0
oo o 1 0 0 1 0
o oo 0 0 0 0 1
o oo 1 1 0 0 0
Figure 6.4. The transfer matrix for a 2 x 2 grid graph. Row 2
corresponds to the 5th and 6th columns of the packing configura-
tion given. To continue tracing forward, consider the only valid
column which is the 3rd column.
Now consider the Ath and 5th columns of the packing configuration.
This corresponds to the third row of the transfer matrix (see Figure 6.6). The
only valid packing in the third row are in columns 1 and 4.
30


Transfer Matrix
n-1 n OO oo oo o o
oo o o oo oo
Packing OO oo 1 1 0 1 0
Configuration oo 0 1 0 0
0
oot oo 0 o
oo o D oo o 1 0 0 1 0
o oo 0 0 0 0 1
o oo 1 1 0 0 0
Figure 6.5. The transfer matrix for a 2 x 2 grid graph. Row 3
corresponds to the 4th and 5th columns of the packing configura-
tion given. The only valid columns are the 1st and 4th columns.
Since column 4, not column 1, matches the packing configuration, the
first element of the corresponding vector a;4 is circled and we continue with the
4th element.
This corresponds to the fourth row of the transfer matrix. There is
only one valid packing in column 5, which matches the packing configuration
(see Figure 6.6).
31


Transfer Matrix
Packing
Configuration
oolcobo
oolo 090
n-1 n
n n+l oo oo oo eo oo 09 o oo o oo
OO oo 1 1 0 1 0
OO o 0 0 1 0 0
oo o 1 0 0 1 0
o oo 0 0 0 0 1
o oo 1 1 0 0 0
Figure 6.6. The transfer matrix for a 2 x 2 grid graph. Row
4 corresponds to the 3rd and 4th columns of the packing config-
uration given. The only valid packings is in the 5th column.
Again, since there is only one valid packing, no other elements in %z
are circled (See Figure 6.3).
Finally, using the fifth row of the transfer matrix (see Figure 6.7),
there are two valid packings in column 1 and column 2.
32


Transfer Matrix
Packing
Configuration
n n+I oo oo oo o oo oo o oo oo oo
OO oo 1 1 0 1 0
OO o 0 0 1 0 0
oo o 1 0 0 1 0
o oo 0 0 0 0 1
o oo 1 1 0 0 0
Figure 6.7. The transfer matrix for a 2 x 2 grid graph. Row
5 corresponds to the 2nd and 3rd columns of the packing config-
uration given. Valid packings are in the 1st and 2nd columns.
Since column 2 matches the packing configuration, the number in the
first element of the vector in x2 is circled, (see Figure 6.3).
To determine the packing state, we now add all of the circled elements
in vectors x2 to xe plus one. Therefore, for this example, the packing state
would be 1 + 1 + 5 + 17 = 24 which means that this packing configuration
o o o o o
@OOOIO
is the 24th packing state out of 57 states for a 2 x 6 grid graph.
33


7. Conclusions for 2-Dimensional Grid Graphs
To determine the maximum packing ofamxn grid graph, a program
was developed to create the vector states using max-plus algebra. Again, the
maximum packing is the largest element for each vector state. A pattern even-
tually developes within the vector states. Therefore, as a grid graph becomes
larger, we will see a repetitive pattern from a smaller grid graph. This can also
be shown by decoding and encoding packing configurations. For example, the
following 5x3 grid graph
n-l n n+1
O O 9
9 o o
o o o
o o
o o
can be pulled apart into two 5x2 grid graphs.
34


n-1 n n n+1
O O O
m o o o
o o + o o
o o O 9
9 O O O
26 th packing 23rd packing
state for state for
5x2 grid 5x2 grid
The 5x3 grid graph is the 87th packing configuration and it is the
same as the 26th packing configuration for the 5x2 grid graph plus the n + 1
column. Thus, in transfer matrix A, the entry is the number of nodes in
the third column which is 2.
Therefore, 2xn grid graphs can be used to find the vector states and
3 x n grid graphs can be used to find the entry in the transfer matrix.
Finding the repetetive pattern simplifies the question of the maximum
packing of a grid graph. Once the pattern is found, the maximum packing
increases by the number required.
This approach verifies the results previously proven by Fisher. The
following table reflects the maximum packings for an m x n grid graph.
35


Grid Graph Repeat Pattern
1 x n P(Pi x Pn) = 1 0 P(Pi x Pn_3) for n > 5
2 x n P{P2 x Pn) = 1 P(P2 x Pn_2) for n > 4
3 x n P(P3 x Pn) = 2 0 P(P3 x Pn_3) for n > 5
4 x n P(P4 x Pn) = 6 0 P(Pi x Pn_7) for 7i > 9
5 x n P(P5 x Pn) = 3 P(P5 x Pn_3) for 7i > 8
6 x n P(P6 x Pn) = 6 0 P(P6 x Pn_5) for 71 > 12
7 x n P(P7 x Pn) = 7 0 P(P7 x P_5) for 7i > 17
Table 7.1. This table shows the solutions for m x n grid graph with m <7
The next table shows the results made by Fisher.
36


Grid Graph Results
1 x n m
2 x n rti
3 x n rfi
4 x n fy] if n mod 7^1 [y] + 1 if n mod 7 = 1
5 x n n + 1
6 x n 10 if n = 7
7 x n [7n+2] if n 10 17 if n = 10
m x n Pfl if (min) 7^ (8,10) 17 if (to, n) (8,10)
Table 7.2. This table shows the solutions for to x n grid graph
made by Fisher.
37


8. Developing a Transfer Matrix for a 3-D Packing
A 3-D packing is a cubic grid graph where every pair of nodes is more
than two apart. The following example displays all the valid packings of a
2x2x2 grid graph. To show the valid packings, consider the view from the
top where 1 represents a node in the top layer and 2 represents a node in the
bottom layer.
Figure 8.1. The valid packings for a 2 x 2 x 2 grid graph.
There are 13 valid packings for a 2 x 2 x 2 cubic grid graph. Using
the same algorithm as with a to x n grid graph, a transfer matrix is developed.
38


n-1 n
00 00 10 10 01 01 20
20 02 00 02 00 20 00
20 02 02
01 00 10
00 00 00
00 10 01
n n+1 00 00 0 0 - 0 - 0 - - - 0 - - -
00 10 - - 0 - - - - - - - 0 - -
00 01 1 - - 1 - 1 - - - 1 - - -
00 20 - - - - 0 - 0 - - - - - -
00 02 1 1 - - - 1 - - - 1 - - -
10 00 - - - - - - - 0 0 - - - -
10 02 - 1
01 00 1 1 - 1 - - - - - 1 - - -
01 20 - 1 -
20 00 0 0
20 01 - 1 -
02 00 1 1 - 1 - 1
02 10 - - 1
Figure 8.2. Transfer Matrix A developed for a 2 x 2 x 2 grid graph.
With vector states as follows:
z2 = [011111212121 2]r, then
x3 = Ax2 = [1 22222222222 2f
x4 = Ax 3 = [2 23232333233 3]r
X5 = A x4 = [2 33333434343 4]r = 2 x2
39


Again, the same algorithm is used to develop the transfer matrix and
determine the pattern repetition. This algorithm was performed on all? x m x n
grid graphs for l < 3 and m < 5.
8.1 Determining the Vector States for a 3-D Grid Graph
The number of valid packings can also be determined by changing the
transfer matrix as before (see Figure 8.3) with:
dij = 1 if there is a valid packing
dij = 0 otherwise.
40


n-1 n
n n+1 00 00 00 10 00 01 00 20 00 02 10 00 10 02 01 00 01 20 20 00 20 01 02 00 02 10
00 00 1 1 0 1 0 1 0 0 0 1 0 0 0
00 10 0 0 1 0 0 0 0 0 0 0 1 0 0
00 01 1 0 0 1 0 1 0 0 0 1 0 0 0
00 20 0 0 0 0 1 0 1 0 0 0 0 0 0
00 02 1 1 0 0 0 1 0 0 0 1 0 0 0
10 00 0 0 0 0 0 0 0 1 1 0 0 0 0
10 02 0 0 0 0 0 0 0 1 0 0 0 0 0
01 00 1 1 0 1 0 0 0 0 0 1 0 0 0
01 20 0 0 0 0 1 0 0 0 0 0 0 0 0
20 00 0 0 0 0 0 0 0 0 0 0 0 1 1
20 01 0 0 0 0 0 0 0 0 0 0 0 1 0
02 00 1 1 0 1 0 1 0 0 0 0 0 0 0
02 10 0 0 1 0 0 0 0 0 0 0 0 0 0
Figure 8.3. Transfer Matrix A developed for a 2 x 2 x 2 grid
graph where a^- = 1 for valid packings and = 0 otherwise.
Summing the components of each vector state derived from max-plus
algebra will give the number of packings for 2 x 2 x n grid graph.
41


1 5 13 33
1 2 5 15
*2 1 X = 3 4 X = 4 11 X = 3 28
1 2 5 15
1 4 11 28
1 2 5 15
1 1 4 11
1 4 11 28
1 1 4 11
1 2 5 15
1 1 4 11
1 4 11 28
1 1 4 11
# of packings for an
2 x 2 x n grid graph 13 33 93 249
n = 2 n = 3 n = 4 11=5
Figure 8.4. Summing the elements of each vector state will give
the number of packings for an 2 x 2 x n grid graph.
8.2 Decoding a 3-D Packing
Using the same algorithm, a vector state can be found for a 3-D
packing. An example of decoding a 3-D packing is given below.
What is state 77 out of 93 for a 2 x 4 x 2 grid graph?
42


Figure 8.5. Vectors associated with a 2 x 4 x 2 grid graph
derived from max-plus algebra.
State 77 occurs in the 11th element (see vector in Figure 8.5). The
sum of the previous elements is 74, which leaves 3 states remaining. As the
transfer matrix shows (see Figure 8.6), there is only one valid packing in the
11th row. This packing corresponds to the 12th element in vector x3 (see Figure
8.5).
43


n-I n
n n+1 00 00 00 10 00 01 00 20 00 02 10 00 10 02 01 00 01 20 20 00 20 01 02 00 02 10
00 00 1 1 0 1 0 1 0 0 0 1 0 0 0
00 10 0 0 1 0 0 0 0 0 0 0 1 0 0
00 01 1 0 0 1 0 1 0 0 0 1 0 0 0
00 20 0 0 0 0 1 0 1 0 0 0 0 0 0
00 02 1 1 0 0 0 1 0 0 0 1 0 0 0
10 00 0 0 0 0 0 0 0 1 1 0 0 0 0
10 02 0 0 0 0 0 0 0 1 0 0 0 0 0
01 00 1 1 0 1 0 0 0 0 0 1 0 0 0
01 20 0 0 0 0 1 0 0 0 0 0 0 0 0
20 00 0 0 0 0 0 0 0 0 0 0 0 1 1
20 01 0 0 0 0 0 0 0 0 0 0 0 1 0
02 00 1 1 0 1 0 1 0 0 0 0 0 0 0
02 10 0 0 1 0 0 0 0 0 0 0 0 0 0
Figure 8.6. Transfer Matrix A developed for a 2 x 2 x 2 grid
graph where a^- = 1 for valid packings and a^- = 0 otherwise.
The number of states remains at 3. The 12th element in x3 corresponds
to the 12th row in the transfer matrix (see Figure 8.6). There are 4 valid
packings in the 12th row: column 1, column 2, column 4, and column 6. Since
there are only 3 states remaining, the packing must be at column 4. Thus, the
44


77th packing state is (see Figure 8.7).
0 0 2 0
2 0 0 1
/ / 7 /

'* /
Figure 8.7. The 77th packing state of a 2 x 4 x 2 grid graph.
8.3 Encoding a 3-D Packing
Using the same algorithm, the vector states can be determined from
the 3-D packing configuration by encoding through the vector states. The
following example demonstrates this algorithm.
What is the vector state of the following 2x4x2 packing configuration
(see Figure 8.8)?
to 0 0 1
0 1 0 0
/ X / ^

' /
Figure 8.8. A packing configuration of a 2 x 4 x 2 grid graph.
45


n-1 n
n n+1 00 00 00 10 00 01 00 20 00 02 10 00 10 02 01 00 01 20 20 00 20 01 02 00 02 10
00 00 1 1 0 1 0 1 0 0 0 1 0 0 0
00 10 0 0 1 0 0 0 0 0 0 0 1 0 0
00 01 1 0 0 1 0 1 0 0 0 1 0 0 0
00 20 0 0 0 0 1 0 1 0 0 0 0 0 0
00 02 1 1 0 0 0 1 0 0 0 1 0 0 0
10 00 0 0 0 0 0 0 0 1 1 0 0 0 0
10 02 0 0 0 0 0 0 0 1 0 0 0 0 0
01 00 1 1 0 1 0 0 0 0 0 1 0 0 0
01 20 0 0 0 0 1 0 0 0 0 0 0 0 0
20 00 0 0 0 0 0 0 0 0 0 0 0 1 1
20 01 0 0 0 0 0 0 0 0 0 0 0 1 0
02 00 1 1 0 1 0 1 0 0 0 0 0 0 0
02 10 0 0 1 0 0 0 0 0 0 0 0 0 0
Figure 8.9. Transfer Matrix A developed for a 2 x 2x2 grid
graph where = 1 for valid packings and a^- = 0 otherwise.
Consider the last cube on the right. The pattern is found in the 8th
row of the transfer matrix (see Figure 8.9). Circle the previous elements in
vector x4 (see Figure 8.10).
46


Figure 8.10. Vectors associated with a 2 x 4 x 2 grid graph
derived from max-plus algebra.
From the transfer matrix (see Figure 8.9), valid packings for row 8 are
in column 1, column 2, column 4, and column 10. Considering the middle cube,
column 2 matches the packing configuration. Therefore, the first element of
vector £3 is circled (see Figure 8.10). Now consider the 2nd row of the transfer
matrix (see Figure 8.9). The only valid packings are in column 3 and column
11. Column 11 matches the left cube. Circle the 3rd element from vector x2-
Now add all circled elements in vectors x2 to X4 plus one (see Figure 8.10). In
this case, the packing state would be 1 + 1 + 5 + 13-1-5-1-11-1-5 + 11-1-5 + 4 = 61.
Then this packing configuration is the 61st packing state out of 93 states.
47


9. Conclusions for 3-Dimensional Grid Graph
A similar program was written for cubic grid graphs following the
same general algorithm. The following table shows the solutions for a Ixmxn
grid graph with l < 3 and m < 5.
Grid Graph Repeat Pattern
2x2 x n P(P2 x P2x Pn) = 2 P(P2 x P2 x Pn-3) for 7i > 5
2x3 xn P(P2 x P3 x Pn) = 2 P(P2 x P3 x Pn_2) for n > 4
2x4 xn P(P2 x P4 x P) = 4 P(P2 x P4 x P_3) forn > 7
2x5 xn P(P2 x P5 x Pn) = 5 P(P2 x P5 x Pn_3) for n >T0
3x2 x n P(P3 x P2 x Pn) = 2 P(P3 x P2 x Pn_2) forn > 4
3 x 3 x n P(P3 x P3 x P = 5 P(P3 x P3 x Pn_3 for n > 10
3x4 xn P(P3 x P4 x Pn = 4 0 P(P3 x P4 x Pn_3 for n > 7
3x5 x n P(P3 x P5 x Pn = 33 <8) P(P3 x P5 x Pn_i4 for n > 39
Table 9.1. This table shows the solutions for Ixmxn grid
graph (l < 3 and m < 5)
With the exception of the 3x5 x n cubic grid graph, all of these
packing solutions were previously proven by Beel and-.Fisher. This 3x5 x n
48


grid graph verifies the conjecture made by Beel and Fisher. The final table
shows their results.
Grid Graph Results
2x2 x n r^pi for n > 2
2x3 x n 2 rti
2x4 x n [fl for n > 4
2x5 x n l"^1] for n > 5
3x2 x n 2Tfl
3 x 3 x n ff ] for n > 5
3 x 4 x n 2 n
Table 9.2. This table shows the solutions for l x m x n grid
graph (/ < 3 and m < 5)
49


REFERENCES
[1] David C. Fisher, The 2-Packing Number of Complete Grid Graphs, Ars
Combinatoria 30: 261-270 (1993)
[2] David C. Fisher and Sarah R. Beel,The 2-Packing Number of 3-
Dimensional Grids, Ars Combinatoria.
50


Full Text

PAGE 1

PACKING OF 2-DIMENSION AND 3-DIMENSION GRID GRAPHS by Deborah T. Grant B.B.A., Southern Methodist University, 1977 A thesis submitted to the University of Colorado at Denver in partial fulfillment of the requirements for the degree of Master of Science Applied Mathematics 1998

PAGE 2

This thesis for the Master of Science degree by Deborah T. Grant has been approved by David C. Fisher William Briggs J. Richard Lundgren Date

PAGE 3

Grant, Deborah T. Grant (M.S., Applied Mathematics) Packing of 2-Dimensional and 3-Dimensional Grid Graphs Thesis directed by Professor David C. Fisher ABSTRACT A packing S of a graph G is a set of nodes such that every pair of nodes in S is more that two apart. The packing number P( G) is the maximum size of a packing of G. What is the maximum size of a packing of an m x n grid graph? Through ad hoc methods, Dr. David Fisher answered this for all m and n. Using max-plus algebra, an algorithm is developed to determine the solution to this question. This algorithm is designed to be easily modified to answer other packing questions. This abstract accurately represents the content of the candidate's thesis. I recommend its publication. Signed ________ David C. Fisher 111

PAGE 4

ACKNOWLEDGEMENTS My sincere thanks to my husband, Kerry; my sons, Ryan and Connor; and my parents, Charles and Bobbie Temple. Without their loving support, kindness and encouragement, I would not have been able to complete this goal. IV

PAGE 5

CONTENTS Chapter 1. Introduction 2. Max-Plus Algebra 3. Finding a Packing Number for a 3 x n Grid Graph 4. Size of Vector ........... 5. Decoding a Specific Packing State 6. Encoding a Specific Packing State 7. Conclusions for 2-Dimensional Grid Graphs 8. Developing a Transfer Matrix for a 3-D Packing 1 2 4 11 18 28 34 38 8.1 Determining the Vector States for a 3-D Grid Graph 40 8.2 Decoding a 3-D Packing 8.3 Encoding a 3-D Packing 9. Conclusions for 3-Dimensional Grid Graph References . . . . . . . . . . . v 42 45 48 50

PAGE 6

FIGURES Figure 1.1 An example of a valid packing for a 4 x 3 grid graph. 3.1 All valid packings for a 3 x 1 grid graph ....... 3.2 The nine valid packings for a 3 X 2 grid graph developed from the 3 x 1 grid graph 3.3 Transfer Matrix A for a 3 x n grid graph 4.1 Transfer Matrix A for a 2 X 2 grid graph. 4.2 Summing the elements of each vector state will give the num-ber of packings for an 2 x n grid graph. . . . . 4.3 Transfer Matrix A for 3 x 2 grid graph where aij = 1 for valid packings and aij = 0 otherwise. . . . . . 4.4 Summing the elements of each vector state will give the num-1 4 5 9 11 12 14 ber of packings for an 3 x n grid graph. . . . . . . 15 5.1 Vectors associated with a 2 x 6 grid graph derived from maxplus algebra. . . . . . . . . . . . . . 19 Vl

PAGE 7

5.2 Transfer Matrix for 2 x 2 grid graph. The third row corre sponds to the 3rd element of the vector. The beginning of the packing is the packing of the 3rd row. To continue the trace back, consider the valid packings in the 1st and 4th column. 20 5.3 Same vectors associated with a 2 x 6 grid graph showing the "traceback" for the vector. ..... 5.4 Transfer Matrix for 2 x 2 grid graph. The first row corre sponds to the 1st element of the x5 vector. The 1st row is attached to the front of the packing. To continue the trace back, consider the valid packings in the 1st, 2nd and 4th columns .................. 5.5 Same vectors associated with a 2 x 6 grid graph showing the 21 22 "traceback" for the vector. . . . . . . . . . 23 5.6 Transfer Matrix for 2 x 2 grid graph. The second row cor responds to the 2nd element of the x4 vector. The 2nd row is attached to the front of the packing. To continue the traceback, consider the valid packings in the 3rd column. . . 23 5. 7 Same vectors associated with a 2 x 6 grid graph showing the "traceback" for the x3 vector. . . . . . . . . . 24 Vll

PAGE 8

5.8 Transfer Matrix for 2 x 2 grid graph. The third row corre sponds to the 3rd element of the x3 vector. The 3rd row is attached to the front of the packing. To continue the traceback, consider the valid packings in the 1st and 4th columns. 25 5.9 Same vectors associated with a 2 x 6 grid graph showing the "traceback" for the x2 vector. . . . . . . . . . 26 5.10 Transfer Matrix for 2 x 2 grid graph. The fourth row corre sponds to the 4th element of the x2 vector. The 4th row is attached to the front of the packing. . . 5.11 The 31st packing state for a 2 x 6 grid graph. 6.1 A packing configuration for a 2 x 6 grid graph. 6.2 The transfer matrix for a 2 x 2 grid graph. Row 2 corresponds 26 27 28 to the last 2 columns of the packing configuration given. 29 6.3 The associated vectors for the 2 x 6 grid graph. . . 29 6.4 The transfer matrix for a 2 x 2 grid graph. Row 2 corresponds to the 5th and 6th columns of the packing configuration given. To continue tracing forward, consider the only valid column which is the 3rd column. . . . . . . . . . . 30 Vlll

PAGE 9

6.5 The transfer matrix for a 2 x 2 grid graph. Row 3 corresponds to the 4th and 5th columns of the packing configuration given. The only valid columns are the pt and 4th columns. . . 31 6.6 The transfer matrix for a 2 x 2 grid graph. Row 4 corresponds to the 3rd and 4th columns of the packing configuration given. The only valid packings is in the 5th column. . . . . 32 6. 7 The transfer matrix for a 2 x 2 grid graph. Row 5 corresponds to the 2nd and 3rd columns of the packing configuration given. Valid packings are in the 1st and 2nd columns. 8.1 The valid packings for a 2 x 2 x 2 grid graph .. 33 38 8.2 Transfer Matrix A developed for a 2 x 2 x 2 grid graph. 39 8.3 Transfer Matrix A developed for a 2 x 2 x 2 grid graph where aij = 1 for valid packings and aij = 0 otherwise. 41 8.4 Summing the elements of each vector state will give the num-ber of packings for an 2 x 2 x n grid graph. . . . . . 42 8.5 Vectors associated with a 2 x 4 x 2 grid graph derived from max-plus algebra. . . . . . . . . . . . . 43 8.6 Transfer Matrix A developed for a 2 x 2 x 2 grid graph where aij = 1 for valid packings and aij = 0 otherwise. 8. 7 The 77th packing state of a 2 x 4 x 2 grid graph. IX 44 45

PAGE 10

8.8 A packing configuration of a 2 x 4 x 2 grid graph. . . . 45 8.9 Transfer Matrix A developed for a 2 x 2 x 2 grid graph where aij = 1 for valid packings and aij = 0 otherwise. 46 8.10 Vectors associated with a 2 x 4 x 2 grid graph derived from max-plus algebra. . . . . . . . . . . . . 47 X

PAGE 11

TABLES Table 4.1 This table shows the number of packings for 1 x n, 2 x n, and 3 x n grid graphs. Note: by adding aij = 1 in the transfer matrix for a 2 x n grid graph will give the total number of packings for a 3 x n grid graph. . . . . . . . . 17 7.1 This table shows the solutions form x n grid graph with m:::; 7 36 7.2 This table shows the solutions for m x n grid graph made by Fisher. 37 9.1 This table shows the solutions for l x m x n grid graph (l :::; 3 and m:::; 5) ......... 48 9.2 This table shows the solutions for l x m x n grid graph (l :::; 3 and m:::; 5) ......... 49 Xl

PAGE 12

1. Introduction A packing S of a grid graph G is a set of nodes such that every pair of nodes in S is more than two apart. The packing number P( G) is the maximum size of a packing of G. Below is an example of a 4 x 3 grid graph (see Figure 1.1). The packing number for this example is 3. Figure 1.1. An example of a valid packing for a 4 x 3 grid graph. Through ad hoc methods, Fisher determined the maximum size of a packing of an m x n grid graph. Using max-plus algebra, this paper presents an algorithm to determine the solution to this question. This algorithm is also designed to be easily modified to answer other packing questions. 1

PAGE 13

2. Max-Plus Algebra Max-plus algebra is similar to matrix multiplication but replaces ad dition ( +) with maximization ( E9) and multiplication ( x) with addition ( 0) The properties of max-plus algebra are: An identity e for EEl has the property that a EEl e = a for all a. Translating into regular notation, this is max (a, e) = a. This is true only if e < a for all a. To have an identity for E9 and to have the algebra in clude all real numbers, then -oo must be added to the real numbers. Let = U -oo. When adding an element, the operations must be defined. So \:fa E let -oo E9 a= a EEl -oo =a and -oo 0 a= a 0 -oo = -oo. Then for all a, b, c E the following properties are defined. (Commutative) (i.e., a EEl b = b EEl a.(i.e., max (a, b) =max (b, a) and (i.e., a 0 b = b 0 a)(i.e., a+ b = b +a); (Associative) (i.e., a E9 (b EEl c) = (a EEl b) E9 c (i.e., max (a, max (b, c)= max (max (a, b), c)) and a 0 (b 0 c)= (a 0 b) 0 c (i.e., a+ (b +c) = (a+ b)+ c); (Distributive) a 0 (b 0 c) = (a 0 b) E9 (a 0 c) (i.e., a+ (max (b, c)= max (a+ b, a+ c)); 2

PAGE 14

(Identity) -oo EEl a= a (i.e., max ( -oo, a) =a), and 0 0 a= a (i.e., 0 +a= a); (One inverse) -a a= 0 (i.e., -a+ a= 0); (Consistency of identities) -oo 0 = -oo; and (Idempotent) a 0 a= a (i.e., max (a, a) =a). An example of max-plus algebra is given below. 5 7 2 6 8 8 6 0 1 (50 6) EEl (7 1) EEl (2 0 4) (8 0 6) EEl (8 1) EEl (6 0 4) (9 0 6) EEl (5 1) EEl (50 4) 9 5 5 4 max (5 + 6, 7 + 1, 2 + 4) 11 max ( 8 + 6, 8 + 1, 6 + 4) 14 max (9 + 6, 5 + 1, 5 + 4) 15 3

PAGE 15

3. Finding a Packing Number for a 3 x n Grid Graph One application for max-plus algebra is to find the packing number of an m x n grid graph. Fisher found the packing number of an m x n grid graph for all m and n; however, the techniques used there were specific to his problem. Using max-plus algebra, packing problems can be solved by finding the packing number of a 3 x n grid for all n in finite time. First, consider all of the packings for a 3 x 1 grid graph (see Figure 3.1). Figure 3.1. All valid packings for a 3 x 1 grid graph. Clearly, there are four possible packings for a 3 x 1 grid. By building from the 3 x 1 grids, all of the 3 x 2 grids can be created simply by adding an additional column and eliminating any packing violations. There are nine packings for a 3 x 2 grid (see Figure 3.2). 4

PAGE 16

8 -8 Figure 3.2. The nine valid packings for a 3 x 2 grid graph developed from the 3 x 1 grid graph A vector of length 9 can be created from the number of nodes in a packing of a 3 x 2 grid. Let xk be a vector of length 9 whose ith component is the maximum number of nodes in a packing of a 3 x n grid whose rightmost two columns are the same as the ith packing found above. Thus, the entries in x2 are the number of nodes in the relevant packing. 5

PAGE 17

0 1 1 1 x2 = 1 2 1 1 2 The ith entry of x3 is the maximum number of nodes in a packing of a 3 x 3 grid with the second and third column in the ith state. So, for example, the first entry of x3 is 1, because with the second and third column as specified (namely both columns empty), the first column can have at most one node. However, the second entry is 2, because with the second column empty and the third column with one node at the top row, the first column can have at most one node. This gives a total of two nodes. 6

PAGE 18

1 2 2 2 x3 = 2 2 1 2 2 Thus, a dynamic programming algorithm can be developed as follows: xn+1(1) = 0 + max(xn(1), Xn(5), Xn(7), Xn(8)) xn+1(2) = 1 + max(xn(1), Xn(7), Xn(8)) xn+1(3) = 1 + max(xn(1), Xn(5), Xn(8)) xn+1(4) = 1 + max(xn(1), Xn(5), Xn(7)) xn+1(5) = 0 + max(xn(2), Xn(9)) xn+1(6) = 1 + max(xn(2)) xn+1(7) = 0 + max(xn(3)) xn+1(8) = 0 + max(xn(4), Xn(6)) xn+1(9) = 1 + max(xn(4)) For example Xn+I (5) is the fifth packing configuration 7

PAGE 19

n n+ I 0 0 0 0 0 which has 0 nodes in then+ 1 column merges either with Xn(2) or Xn(9). n-1 n 0 0 0 0 0 n-1 n 0 0 0 0 This algorithm can be developed into the following transfer matrix A using the 9 configurations of a 3 x 2 grid (see Figure 3.3). The states across the top are configurations of columns n-1 and n. The states down the left side are configurations of columns n and n + 1. The ij entry of A is: the number of nodes in column n + 1 on the left side if column non the top and column non the left matches and there is no packing violation, -oo otherwise. Let denote -oo for ease of reading. 8

PAGE 20

n-1 n 00 oe 00 00 eo eo 00 00 oe 00 00 oe 00 00 00 eo 00 00 00 00 00 oe 00 oe 00 eo eo n n+l 00 0 0 0 0 00 00 oe 1 1 1 00 00 00 1 1 1 oe 00 00 00 1 1 1 oe eo 00 0 00 eo 00 -1 oe 00 0 eo 00 00 00 0 0 eo oe 00 -1 eo Figure 3.3. Transfer Matrix A for a 3 x n grid graph With vector states as follows: x2 = [0, 1, 1, 1, 1, 2, 1, 1, 2]T, then X3 =A X2 = [1, 2, 2, 2, 2, 2, 1, 2, 2]T X4 = A X3 = [2, 3, 3, 3, 2, 3, 2, 2, 3]T X5 = A X4 = [2, 3, 3, 3, 3, 4, 3, 3, 4]T = 2 0 X2 Now P(Pm x Pn) is the largest element of Xn Thus P(P3 x g) 9

PAGE 21

1, P(P3 x P2 ) = 2, P(P3 x P 3 ) = 2, P(P3 x P 4 ) = 3, P(P3 x P5 ) = 4, and P(P3 x P6) = 4. Let y = [0, 0, 0, 0, 0, 0, 0, 0, OjT, then P(Pm x Pn) can be ex pressed with max-plus algebra as P(P3 X Pn) =max (xn(1), ... Xn(9)) = YT 0 Xn Lemma 1 P(P3 x g)= 1, P(P3 x P2 ) = 2, P(P3 x P 3 ) = 2, P(P3 x P 4 ) = 3, P(P3 x P5) = 4, P(P3 x P6) = 4. Theorem 1 P(P3 x Pn) = 12;1 Proof (by induction): Notice this is true for n = 1, 2, 3. For n > 3, assume P(P4 X Pn-3) = l2(n3 3)1 = 12;21 = 12;12. Then, P(P4 X Pn) = YT Xn = YT 0 (2 0 Xn-3) = 2@ (yT 0 Xn-3) = 2 + P(P4 X Pn-3) = 2 + 12;1 -2 = 12;1 D 10

PAGE 22

4. Size of Vector How many packing configurations are there for a m x 2 grid graph? am x 3 grid graph? am x 4 grid graph? We can get these results by looking at the transfer matrix of a 2 x 2 grid graph (see Figure 4.1) with aij = 1 if there is a valid packing aij = 0 otherwise. The 5 configurations for a 2 x 2 grid graph are the row and column headers. n-1 n 00 00 00 eo oe n n+l 00 eo oe 00 00 00 1 1 0 1 0 00 00 0 0 1 0 0 eo 00 1 0 0 1 0 oe eo 0 0 0 0 1 00 oe 1 1 0 0 0 00 Figure 4.1. Transfer Matrix A for a 2 x 2 grid graph. Let x2 be a vector with 5 elements of 1 where each element represent one of the five packing configurations of a 2 x 2 grid graph. By max-plus matrix multiplication (A 0 x2), then additional vector states can be found. 11

PAGE 23

Summing the components of each vector state derived will give the number of packings for each 2 x n grid graph (See Figure 4.2). 3 5 9 17 2 4 7 x2 X= X= 4 X= 7 X= 13 3 2 4 5 6 2 4 7 2 4 7 13 # ofpackings for an 2 x n grid graph 5 9 17 31 57 n=2 n=3 n=4 n=5 n=6 Figure 4.2. Summing the elements of each vector state will give the number of packings for an 2 x n grid graph. Notice that there are 57 different packings for a 2 x 6 grid graph. Vector x6 indicates that there are 17 of these packings ending like this: ? ? ? ?o o ? ? ? ?o o 7 packings ending like this: ? ? ? ?o o ? ? ? ? 0 13 packings ending like this: ? ? ? ?o o ? ???o 12

PAGE 24

with 7 packings ending like this: ? ? ? ? 0 ? ? ? ?o o and 13 packings ending like this: ? ? ? ?o ? ? ? ?o o Now consider a transfer matrix for a 3 x 2 grid graph (see Figure 4.3) aij = 1 if there is a valid packing aij = 0 otherwise. 13

PAGE 25

n-1 n 00 oe 00 00 eo eo 00 00 oe 00 00 oe 00 00 00 eo 00 00 n n+l 00 00 00 oe 00 oe 00 eo eo 00 00 1 0 0 0 1 0 1 1 0 00 oe 00 1 0 0 0 0 0 1 1 0 00 00 oe 1 0 0 0 1 0 0 1 0 00 00 00 1 0 0 0 1 0 1 0 0 oe eo 0 1 0 0 0 0 0 0 1 00 00 eo 00 0 1 0 0 0 0 0 0 0 oe 00 eo 0 0 1 0 0 0 0 0 0 00 00 00 0 0 0 1 0 1 0 0 0 eo oe 0 0 0 1 0 0 0 0 0 00 eo Figure 4.3. Transfer Matrix A for 3 x 2 grid graph where aij = 1 for valid packings and aij = 0 otherwise. Again, summing the components of each vector state derived from max-plus algebra gives the numbers of packings for each 3 x n grid graph. 14

PAGE 26

4 9 20 3 7 16 x2 X= X= 8 X= 17 3 3 4 5 3 7 16 2 4 10 3 8 2 4 10 3 7 3 7 # of packings for an 3 x n grid graph 9 20 48 111 5 Figure 4.4. Summing the elements of each vector state will give the number of packings for an 3 x n grid graph. Since the transfer matrix is always a square matrix, then each term in the expansion of the determinant is a product of n entries containing exactly one entry from each row and column. Thus, a characteristic polynomial p(.\) of the transfer matrix is obtained. For example, for a 1 x 2 grid graph, there are clearly three packing solutions which gives the following 3 x 3 transfer matrix A. n-1 n eo oe ;j A= eo o 0 oe 1 0 The characteristic equation (p(.\) = 0) of A is 15

PAGE 27

p(A) = det (AI3 A) = det A -1 -1 0 A -1 0 0 -1 A From the characteristic polynomial of each transfer matrix we can determine the number of packings (an) for an m x n grid graph. Continuing with the same example, the number of packings for a 1 x 3 grid graph (a3 ) is a3 = a2 + 1. In other words, the number of packings for a 1 x 3 grid graph equals the number of packings for a 1 x 2 grid graph (3) plus 1. Therefore, the number of packings for a 1 x 3 grid graph is 4. The recursive equations developed from the characteristic polynomi als are below: 1 X n: For n > 4, an= an-1 + an-3 2 X n: For n > 6, an = an-1 + 2an-3 + an-4 + an-5 3 X n: For n > 10, an= an-1 + 5an-3 + 3an-4 + 5an-5 + an-6-2an-8-an-9 The following table shows the number of packings found using these equations. 16

PAGE 28

n no. of packings no. of packings no. of packings for 1 x n for 2 x n for 3 x n 1 2 3 4 2 3 5 9 3 4 9 20 4 6 17 48 5 9 31 111 6 13 57 259 7 19 79 605 8 28 241 1410 Table 4.1. This table shows the number of packings for 1 x n, 2 x n, and 3 x n grid graphs. Note: by adding aij = 1 in the transfer matrix for a 2 x n grid graph will give the total number of packings for a 3 x n grid graph. The eigenvalues are the real roots of the characteristic polynomial (p(A) = 0) derived from each transfer matrix. The eigenvalue(s) for the 2 x n matrix determines the storage space needed (an= O(An) where A is the largest possible root at A3 = A2+1(A rv 1.829) and the eigenvalue(s) for the 3xn matrix determines the amount of work per iteration (an = O(An) where A rv 2.340). 17

PAGE 29

5. Decoding a Specific Packing State Given a specific packing state for an m x n grid graph, can we de termine a related packing configuration? Since each state is represented in the vector (xn) of a transfer matrix for am x n grid graph, then the packing configuration can be determined by decoding or "tracing back" through the vector states. An example of decoding a packing state is given below beginning with Figure 5.1. What is state 31 out of 57 for a 2 x 6 grid graph? We must first consider the associated vectors. For a 2 x n grid graph, start the traceback with the associated nth vector. Thus, for a 2 x 6, consider the vector x6 and note that state 31 can not be in the first or second elements of vector x6 since they only hold the first 17 and 7 states, respectively. 18

PAGE 30

3 5 9 17 2 4 7 X= X= 4 X= 7 X= WJ 3 2 4 5 6 2 4 7 2 4 7 13 Figure 5.1. Vectors associated with a 2 x 6 grid graph derived from max-plus algebra. Therefore, state 31 must be in the third element (see Figure 5.1), which corresponds to the third packing configuration and thus, the third row of the transfer matrix for a 2 x 2 grid graph (see Figure 5.2). 19

PAGE 31

Transfer Matrix n-1 n 00 00 oe n n+l 0 eo oe 0 00 00 1 1 0 1 0 00 Developing 00 0 0 1 0 0 Packing State eo 1 0 0 1 0 oe e eo 0 0 0 0 1 00 oe 1 1 0 0 0 00 Figure 5.2. Transfer Matrix for 2 x 2 grid graph. The third row corresponds to the 3rd element of the vector. The beginning of the packing is the packing of the 3rd row. To continue the trace back, consider the valid packings in the 1st and 4th column. Note, the only valid packings for row 3 are in column 1 and column 4. Thus, the 13 states in the 3rd element of x6 must be in columns 1 and 4 of row 3 of the transfer matrix. This corresponds to elements 1 and 4 in vector x5 Tracing back to vector x5 state 31 must be in the first element since there are 9 states in this element (see Figure 5.3) and there are 7 states left. (Note: since element 3 in x6 contained more states (13) than were left (7), no subtraction is performed. In other words, no subtraction is performed in the element in which the state is found.) 20

PAGE 32

3 5 2 X= X= 4 X= 3 2 4 5 2 2 4 7 Figure 5.3. Same vectors associated with a 2 x 6 grid graph showing the "traceback" for the vector. This corresponds to the first row of the transfer matrix. Now, the left hand column of the configuration is attached to the left side of the packing (see Figure 5.4). 21

PAGE 33

Transfer Matrix n-1 n 00 oe n n+l eo oe 0 00 1 0 1 0 Developing 00 0 0 1 0 0 Packing Stat eo 00 1 0 0 1 0 e oe eo 0 0 0 0 1 00 oe 1 1 0 0 0 00 Figure 5.4. Transfer Matrix for 2 x 2 grid graph. The first row corresponds to the 1st element of the x5 vector. The 1st row is attached to the front of the packing. To continue the trace back, consider the valid packings in the 1st, 2nd and 4th columns. The only valid packings in row 1 are in column 1, column 2, and column 4. (see Figure 5.4). Tracing back to x4 the packing state must be in the second element of the vector since there are 7 states left (See Figure 5.5). 22

PAGE 34

3 5 7 0 0 4 X= X= 4 7 3 2 4 2 4 2 4 7 Figure 5.5. Same vectors associated with a 2 x 6 grid graph showing the "traceback" for the vector. This corresponds to the second row of the transfer matrix (see Figure 5.6). Again, attach the left side column of the configuration to the packing. Transfer Matrix n-1 n 00 00 eo oe n n+l 00 eo e 00 00 1 0 1 0 Developing 0 1 0 0 Packing State 00 1 0 0 1 0 oe eo 0 0 0 0 1 00 oe 1 1 0 0 0 00 Figure 5.6. Transfer Matrix for 2 x 2 grid graph. The second row corresponds to the 2nd element of the x4 vector. The 2nd row is attached to the front of the packing. To continue the traceback, consider the valid packings in the 3rd column. 23

PAGE 35

The only valid packing in row 2 is in column 3. Tracing back to vector x3 the packing state must be in the third element of the vector (see Figure 5.7). (recall that there is no subtraction if the state is in the current element). 3 5 7 0 0 4 Xz X= 0 X= 4 7 3 4 2 4 2 4 7 Figure 5.7. Same vectors associated with a 2 x 6 grid graph showing the "traceback" for the x3 vector. This corresponds to the third row of the transfer matrix and the left hand column of the configuration is attached in the packing (see Figure 5.8). 24

PAGE 36

Transfer Matrix n-1 n 00 oo leol oe n n+l eo oe oo 00 00 1 1 0 1 0 00 Developing 00 0 0 1 0 0 Packing State eo lli!Jooo 1 0 0 1 0 ooe e eo 0 0 0 0 1 00 oe 1 1 0 0 0 00 Figure 5.8. Transfer Matrix for 2 x 2 grid graph. The third row corresponds to the 3rd element of the x3 vector. The 3rd row is attached to the front of the packing. To continue the traceback, consider the valid packings in the 1st and 4th columns. The only valid packings in row 3 are in column 1 and column 4. Finally, tracing back to vector x2 the packing state must be in the fourth element of the vector since there are only two states left (see Figure 5.9). 25

PAGE 37

1 3 5 7 0 1 1 0 4 1 0 X= 4 7 / 4 OJ 1 2 4 2 4 7 Figure 5.9. Same vectors associated with a 2 x 6 grid graph showing the "traceback" for the x2 vector. This corresponds to the fourth row of the transfer matrix and the left side column of the configuration is attached to the packing (see Figure 5.10). Transfer Matrix n-1 n 00 00 00 eo oe n n+l 00 eo oe 00 00 00 1 1 0 1 0 Developing 00 00 0 0 1 0 0 Packing State eo 0 1 0 0 1 0 eooe oe 0 0 0 0 1 oe 1 1 0 0 0 00 Figure 5.10. Transfer Matrix for 2 x 2 grid graph. The fourth row corresponds to the 4th element of the x2 vector. The 4th row is attached to the front of the packing. Thus, a specific packing state is found (shown in Figure 5.11). 26

PAGE 38

eooooo ooeooe Figure 5.11. The 31st packing state for a 2 x 6 grid graph. 27

PAGE 39

6. Encoding a Specific Packing State Again, since each state is represented in the vector (xn) of the transfer matrix for a grid graph, then the vector states can be determined from the packing configuration by encoding or "tracing forward" through the vector states. The following example demonstrates the algorithm to encode a vector state beginning with Figure 6.1. What is the vector state of the following 2 x 6 packing configuration? ooeooo eoooeo Figure 6.1. A packing configuration for a 2 x 6 grid graph. Consider the last two columns in the packing configuration (see Figure 6.1) and the pattern is found in the second row of the transfer matrix (see Figure 6.2). This corresponds to the second element of vector x6 (see Figure 6.3). 28

PAGE 40

n-1 n 00 00 00 eo oe n n+l 00 eo oe 00 00 00 1 1 0 1 0 00 0 0 0 1 0 0 00 1 0 0 1 0 oe eo 0 0 0 0 1 00 oe 1 1 0 0 0 00 Figure 6.2. The transfer matrix for a 2 x 2 grid graph. Row 2 corresponds to the last 2 columns of the packing configuration given. When a match is found in x6 store all previous elements (Note: previous elements are circled in Figure 6.3.) 9 (!]) 2 4 co 4 7 4 7 13 Figure 6.3. The associated vectors for the 2 x 6 grid graph. 29

PAGE 41

The only valid packing for the row 2 of the transfer matrix is column 3 (see Figure 6.4). This corresponds to the third element in x5 (see Figure 6.3). No other previous elements are circled. Transfer Matrix n-1 n 00 00 oe n n+l 00 eo 00 00 Packing 00 1 1 0 1 0 00 Configuration 00 0 0 1 0 0 eoo oeo 00 1 0 0 1 0 oe eo 0 0 0 0 1 00 oe 1 1 0 0 0 00 Figure 6.4. The transfer matrix for a 2 x 2 grid graph. Row 2 corresponds to the 5th and 6th columns of the packing configura-tion given. To continue tracing forward, consider the only valid column which is the 3rd column. Now consider the 4th and 5th columns of the packing configuration. This corresponds to the third row of the transfer matrix (see Figure 6.6). The only valid packing in the third row are in columns 1 and 4. 30

PAGE 42

Transfer Matrix n-1 n 00 00 oe n n+l 0 eo oe 0 00 Packing 00 1 1 0 1 0 00 Configuration 00 0 1 0 0 0 eoo oe lool 1 0 0 1 0 oe eo 0 0 0 0 1 00 oe 1 1 0 0 0 00 Figure 6.5. The transfer matrix for a 2 x 2 grid graph. Row 3 corresponds to the 4th and 5th columns of the packing configura-tion given. The only valid columns are the pt and 4th columns. Since column 4, not column 1, matches the packing configuration, the first element of the corresponding vector x4 is circled and we continue with the 4th element. This corresponds to the fourth row of the transfer matrix. There is only one valid packing in column 5, which matches the packing configuration (see Figure 6.6). 31

PAGE 43

Transfer Matrix n-1 n 00 00 00 eo n n+l 00 eo oe 00 0 Packing 00 1 1 0 1 0 00 Configuration 00 0 1 0 0 0 eo eoo o o 00 oe 1 0 0 1 0 0 0 0 0 1 1 0 0 0 Figure 6.6. The transfer matrix for a 2 x 2 grid graph. Row 4 corresponds to the 3rd and 4th columns of the packing config-uration given. The only valid packings is in the 5th column. Again, since there is only one valid packing, no other elements in x3 are circled (See Figure 6.3). Finally, using the fifth row of the transfer matrix (see Figure 6.7), there are two valid packings in column 1 and column 2. 32

PAGE 44

Transfer Matrix n-1 n 00 eo oe n n+l eo oe 00 00 Packing 00 1 1 0 1 0 00 Configuration 00 0 1 0 0 eo 0 00 1 0 0 1 0 oe eo 0 0 0 0 1 00 0 1 1 0 0 0 Figure 6.7. The transfer matrix for a 2 x 2 grid graph. Row 5 corresponds to the 2nd and 3rd columns of the packing config-uration given. Valid packings are in the pt and 2nd columns. Since column 2 matches the packing configuration, the number in the first element of the vector in x2 is circled. (see Figure 6.3). To determine the packing state, we now add all of the circled elements in vectors x2 to x6 plus one. Therefore, for this example, the packing state would be 1 + 1 + 5 + 17 = 24 which means that this packing configuration ooeooo eoooeo is the 24th packing state out of 57 states for a 2 x 6 grid graph. 33

PAGE 45

7. Conclusions for 2-Dimensional Grid Graphs To determine the maximum packing of a m x n grid graph, a program was developed to create the vector states using max-plus algebra. Again, the maximum packing is the largest element for each vector state. A pattern eventually developes within the vector states. Therefore, as a grid graph becomes larger, we will see a repetitive pattern from a smaller grid graph. This can also be shown by decoding and encoding packing configurations. For example, the following 5 x 3 grid graph n-1 n n+l ooe eoo 000 ooe eoo can be pulled apart into two 5 x 2 grid graphs. 34

PAGE 46

n-1 n 00 eo 00 00 eo n n+l oe 00 + 00 oe 00 26th packing state for 23rd packing state for 5 x 2 grid 5 X 2 grid The 5 x 3 grid graph is the 87th packing configuration and it is the same as the 26th packing configuration for the 5 x 2 grid graph plus the n + 1 column. Thus, in transfer matrix A, the aij entry is the number of nodes in the third column which is 2. Therefore, 2 x n grid graphs can be used to find the vector states and 3 x n grid graphs can be used to find the aij entry in the transfer matrix. Finding the repetetive pattern simplifies the question of the maximum packing of a grid graph. Once the pattern is found, the maximum packing increases by the number required. This approach verifies the results previously proven by Fisher. The following table reflects the maximum packings for an m x n grid graph. 35

PAGE 47

Grid Graph Repeat Pattern 1 x n P(P1 X Pn) = 1 0 P(P1 X Pn-3) for n 5 2 x n P(P2 X Pn) = 1 0 P(P2 X Pn-2) for n 4 3 x n P(P3 X Pn) = 2 0 P(P3 X Pn-3) for n 5 4 x n P(P4 X Pn) = 6 0 P(P4 X Pn-7) for n 9 5 x n P(P5 X Pn) = 3 0 P(P5 X Pn-3) for n 8 6 x n P(P6 X Pn) = 6@ P(P6 X Pn-5) for n 12 7 x n P(P7 X Pn) = 7@ P(P7 X Pn-5) for n 17 Table 7.1. This table shows the solutions form x n grid graph with m 7 The next table shows the results made by Fisher. 36

PAGE 48

Grid Graph Results 1 x n 2 x n 3 x n 1 2;1 4 x n 1 6;1 if n mod 7 -11 1 6;1 + 1 if n mod 7 = 1 5 x n n + 1 6 x n 16ni21 if n -17 10 if n = 7 7 x n 17ni21 if n -1-10 17 if n = 10 mxn if (m, n) -1(8, 10) 17 if (m,n) = (8, 10) Table 7.2. This table shows the solutions form x n grid graph made by Fisher. 37

PAGE 49

8. Developing a Transfer Matrix for a 3-D Packing A 3-D packing is a cubic grid graph where every pair of nodes is more than two apart. The following example displays all the valid packings of a 2 x 2 x 2 grid graph. To show the valid packings, consider the view from the top where 1 represents a node in the top layer and 2 represents a node in the bottom layer. 00 00 00 00 00 1 0 0 1 00 1 0 0 1 20 02 00 00 20 00 02 00 20 01 01 20 02 10 10 02 Figure 8.1. The valid packings for a 2 x 2 x 2 grid graph. There are 13 valid packings for a 2 x 2 x 2 cubic grid graph. Using the same algorithm as with a m x n grid graph, a transfer matrix is developed. 38

PAGE 50

n-1 n 00 00 00 00 00 10 10 01 01 20 20 02 02 00 10 01 20 02 00 02 00 20 00 01 00 10 n n+l 00 0 0 0 0 0 00 00 0 0 10 00 1 1 1 1 01 ---00 0 0 20 00 1 1 1 1 02 10 0 0 00 10 -1 02 01 1 1 -1 --1 00 01 1 20 20 0 0 00 20 -1 01 02 1 1 -1 -1 00 02 1 10 Figure 8.2. Transfer Matrix A developed for a 2 x 2 x 2 grid graph_ With vector states as follows: x2 = [0 11111 2 1 2 1 2 1 2]T ,then X3 = A X2 = [1 2 2 2 2 2 2 2 2 2 2 2 2JT x4 = A x3 = [2 2 3 2 3 2 3 3 3 2 3 3 3]T X5 = A X4 = [2 3 3 3 3 3 4 3 4 3 4 3 4JT = 2 0 X2 39

PAGE 51

Again, the same algorithm is used to develop the transfer matrix and determine the pattern repetition. This algorithm was performed on alll x m x n grid graphs for l :::; 3 and m:::; 5. 8.1 Determining the Vector States for a 3-D Grid Graph The number of valid packings can also be determined by changing the transfer matrix as before (see Figure 8.3) with: aij = 1 if there is a valid packing aij = 0 otherwise. 40

PAGE 52

n-1 n 00 00 00 00 00 10 10 01 01 20 20 02 02 00 10 01 20 02 00 02 00 20 00 01 00 10 n n+l 00 1 1 0 1 0 1 0 0 0 1 0 0 0 00 00 0 0 1 0 0 0 0 0 0 0 1 0 0 10 00 1 0 0 1 0 1 0 0 0 1 0 0 0 01 00 0 0 0 0 1 0 1 0 0 0 0 0 0 20 00 1 1 0 0 0 1 0 0 0 1 0 0 0 02 10 0 0 0 0 0 0 0 1 1 0 0 0 0 00 10 0 0 0 0 0 0 0 1 0 0 0 0 0 02 01 1 1 0 1 0 0 0 0 0 1 0 0 0 00 01 0 0 0 0 1 0 0 0 0 0 0 0 0 20 20 0 0 0 0 0 0 0 0 0 0 0 1 1 00 20 0 0 0 0 0 0 0 0 0 0 0 1 0 01 02 1 1 0 1 0 1 0 0 0 0 0 0 0 00 02 0 0 1 0 0 0 0 0 0 0 0 0 0 10 Figure 8.3. Transfer Matrix A developed for a 2 x 2 x 2 grid graph where aij = 1 for valid packings and aij = 0 otherwise. Summing the components of each vector state derived from max-plus algebra will give the number of packings for 2 x 2 x n grid graph_ 41

PAGE 53

5 13 33 2 5 15 x2 = I x= x= II x= 28 3 4 4 5 2 5 15 4 11 28 2 5 15 4 II 4 11 28 4 II 2 5 15 4 II 4 11 28 4 II # of packings for an 2 x 2 x n grid graph 13 33 93 249 n=2 n=3 n=4 n=5 Figure 8.4. Summing the elements of each vector state will give the number of packings for an 2 x 2 x n grid graph. 8.2 Decoding a 3-D Packing Using the same algorithm, a vector state can be found for a 3-D packing. An example of decoding a 3-D packing is given below. What is state 77 out of 93 for a 2 x 4 x 2 grid graph? 42

PAGE 54

5 13 2 5 4 11 2 5 4 11 2 5 x2 = 1 x4= 4 1 4 11 1 1 4 1 1 1 1 4 Figure 8.5. Vectors associated with a 2 x 4 x 2 grid graph derived from max-plus algebra. State 77 occurs in the nth element (see vector x4 in Figure 8.5). The sum of the previous elements is 7 4, which leaves 3 states remaining. As the transfer matrix shows (see Figure 8.6), there is only one valid packing in the 11th row. This packing corresponds to the 12th element in vector x3 (see Figure 8.5). 43

PAGE 55

n-1 n 00 00 00 00 00 10 10 01 01 20 20 02 02 00 10 01 20 02 00 02 00 20 00 01 00 10 n n+l 00 1 1 0 1 0 1 0 0 0 1 0 0 0 00 00 0 0 1 0 0 0 0 0 0 0 1 0 0 10 00 1 0 0 1 0 1 0 0 0 1 0 0 0 01 00 0 0 0 0 1 0 1 0 0 0 0 0 0 20 00 1 1 0 0 0 1 0 0 0 1 0 0 0 02 10 0 0 0 0 0 0 0 1 1 0 0 0 0 00 10 0 0 0 0 0 0 0 1 0 0 0 0 0 02 01 1 1 0 1 0 0 0 0 0 1 0 0 0 00 01 0 0 0 0 1 0 0 0 0 0 0 0 0 20 20 0 0 0 0 0 0 0 0 0 0 0 1 1 00 20 0 0 0 0 0 0 0 0 0 0 0 1 0 01 02 1 1 0 1 0 1 0 0 0 0 0 0 0 00 02 0 0 1 0 0 0 0 0 0 0 0 0 0 10 Figure 8.6. Transfer Matrix A developed for a 2 x 2 x 2 grid graph where aij = 1 for valid packings and aij = 0 otherwise. The number of states remains at 3. The 12th element in x3 corresponds to the 12th row in the transfer matrix (see Figure 8.6). There are 4 valid packings in the 12th row: column 1, column 2, column 4, and column 6. Since there are only 3 states remaining, the packing must be at column 4. Thus, the 44

PAGE 56

77th packing state is (see Figure 8.7). 0 0 2 0 2 0 0 1 Figure 8.7. The 77th packing state of a 2 x 4 x 2 grid graph. 8.3 Encoding a 3-D Packing Using the same algorithm, the vector states can be determined from the 3-D packing configuration by encoding through the vector states. The following example demonstrates this algorithm. What is the vector state of the following 2 x 4 x 2 packing configuration (see Figure 8.8)? 2 0 0 1 0 1 0 0 Figure 8.8. A packing configuration of a 2 x 4 x 2 grid graph. 45

PAGE 57

n-1 n 00 00 00 00 00 10 10 01 01 20 20 02 02 00 10 01 20 02 00 02 00 20 00 01 00 10 n n+l 00 1 1 0 1 0 1 0 0 0 1 0 0 0 00 00 0 0 1 0 0 0 0 0 0 0 1 0 0 10 00 1 0 0 1 0 1 0 0 0 1 0 0 0 01 00 0 0 0 0 1 0 1 0 0 0 0 0 0 20 00 1 1 0 0 0 1 0 0 0 1 0 0 0 02 10 0 0 0 0 0 0 0 1 1 0 0 0 0 00 10 0 0 0 0 0 0 0 1 0 0 0 0 0 02 01 1 1 0 1 0 0 0 0 0 1 0 0 0 00 01 0 0 0 0 1 0 0 0 0 0 0 0 0 20 20 0 0 0 0 0 0 0 0 0 0 0 1 1 00 20 0 0 0 0 0 0 0 0 0 0 0 1 0 01 02 1 1 0 1 0 1 0 0 0 0 0 0 0 00 02 0 0 1 0 0 0 0 0 0 0 0 0 0 10 Figure 8.9. Transfer Matrix A developed for a 2 x 2 x 2 grid graph where aij = 1 for valid packings and aij = 0 otherwise. Consider the last cube on the right. The pattern is found in the 8th row of the transfer matrix (see Figure 8.9). Circle the previous elements in vector x4 (see Figure 8.10). 46

PAGE 58

1 ffi 1 CD 4 QJ) 1 2 1 4 1 2 @ x2 = 1 x3= 1 ffiJ 1 4 1 1 4 2 5 1 4 4 11 1 1 4 Figure 8.10. Vectors associated with a 2 x 4 x 2 grid graph derived from max-plus algebra. From the transfer matrix (see Figure 8.9), valid packings for row 8 are in column 1, column 2, column 4, and column 10. Considering the middle cube, column 2 matches the packing configuration. Therefore, the first element of vector x3 is circled (see Figure 8.10). Now consider the 2nd row of the transfer matrix (see Figure 8.9). The only valid packings are in column 3 and column 11. Column 11 matches the left cube. Circle the 3rd element from vector x2 Now add all circled elements in vectors x2 to x4 plus one (see Figure 8.10). In this case, the packing state would be 1 + 1 + 5 + 13 + 5 + 11 + 5 + 11 + 5 + 4 = 61. Then this packing configuration is the 61 st packing state out of 93 states. 47

PAGE 59

9. Conclusions for 3-Dimensional Grid Graph A similar program was written for cubic grid graphs following the same general algorithm. The following table shows the solutions for a l x m x n grid graph with l 3 and m 5. Grid Graph Repeat Pattern 2x2xn P(P2 X P2 X Pn) = 2 0 P(P2 X P2 X Pn-3) for n 5 2x3xn P(P2 X P3 X Pn) = 2 0 P(P2 X P3 X Pn-2) for n 4 2x4xn P(P2 X P4 X Pn) = 4 0 P(P2 X P4 X Pn-3) for n 7 2x5xn P(P2 X Ps X Pn) = 5 P(P2 X Ps X Pn-3) for n 10 3x2xn P(P3 X P2 X Pn) = 2 0 P(P3 X P2 X Pn-2) for n 4 3x3xn P(P3 X P3 X Pn = 5 P(P3 X P3 X Pn-3 for n 10 3x4xn P(P3 X P4 X Pn = 4 0 P(P3 X P4 X Pn-3 for n 7 3x5xn P(P3 X Ps X Pn = 33 0 P(P3 X Ps X Pn-14 for n 39 Table 9.1. This table shows the solutions for l x m x n grid graph (Z 3 and m 5) With the exception of the 3 x 5 x n cubic grid graph, all of these packing solutions were previously proven by Beel and Fisher. This 3 x 5 x n 48

PAGE 60

grid graph verifies the conjecture made by Beel and Fisher. The final table shows their results. Grid Graph Results 2x2xn 12 ; 1 for n 2: 2 2x3xn 2 2x4xn 14;1 for n 2: 4 2x5xn 15 ; 1 for n 2: 5 3x2xn 3x3xn 15 ; 1 for n 2: 5 3x4xn 2n Table 9.2. This table shows the solutions for l x m x n grid graph (Z :-=:; 3 and m :-=:; 5) 49

PAGE 61

REFERENCES [1] David C. Fisher, "The 2-Packing Number of Complete Grid Graphs," Ars Combinatoria 30: 261-270 (1993) [2] David C. Fisher and Sarah R. Beel, "The 2-Packing Number of 3-Dimensional Grids," Ars Combinatoria. 50