A linear algorithm of checking of the graph connectness
An algorithm of sorting of all simply laced graph such that subalgorithm of checking of that the graph is connected is of linear dependence on the number of vertices of the graph.
Gespeichert in:
| Veröffentlicht in: | Algebra and Discrete Mathematics |
|---|---|
| Datum: | 2012 |
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | English |
| Veröffentlicht: |
Інститут прикладної математики і механіки НАН України
2012
|
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/152185 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | A linear algorithm of checking of the graph connectness / I. Dudchenko, M. Plakhotnyk // Algebra and Discrete Mathematics. — 2012. — Vol. 13, № 1. — С. 43–51. — Бібліогр.: 5 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-152185 |
|---|---|
| record_format |
dspace |
| spelling |
Dudchenko, I. Plakhotnyk, M. 2019-06-08T09:46:44Z 2019-06-08T09:46:44Z 2012 A linear algorithm of checking of the graph connectness / I. Dudchenko, M. Plakhotnyk // Algebra and Discrete Mathematics. — 2012. — Vol. 13, № 1. — С. 43–51. — Бібліогр.: 5 назв. — англ. 1726-3255 https://nasplib.isofts.kiev.ua/handle/123456789/152185 An algorithm of sorting of all simply laced graph such that subalgorithm of checking of that the graph is connected is of linear dependence on the number of vertices of the graph. en Інститут прикладної математики і механіки НАН України Algebra and Discrete Mathematics A linear algorithm of checking of the graph connectness Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
A linear algorithm of checking of the graph connectness |
| spellingShingle |
A linear algorithm of checking of the graph connectness Dudchenko, I. Plakhotnyk, M. |
| title_short |
A linear algorithm of checking of the graph connectness |
| title_full |
A linear algorithm of checking of the graph connectness |
| title_fullStr |
A linear algorithm of checking of the graph connectness |
| title_full_unstemmed |
A linear algorithm of checking of the graph connectness |
| title_sort |
linear algorithm of checking of the graph connectness |
| author |
Dudchenko, I. Plakhotnyk, M. |
| author_facet |
Dudchenko, I. Plakhotnyk, M. |
| publishDate |
2012 |
| language |
English |
| container_title |
Algebra and Discrete Mathematics |
| publisher |
Інститут прикладної математики і механіки НАН України |
| format |
Article |
| description |
An algorithm of sorting of all simply laced graph such that subalgorithm of checking of that the graph is connected is of linear dependence on the number of vertices of the graph.
|
| issn |
1726-3255 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/152185 |
| citation_txt |
A linear algorithm of checking of the graph connectness / I. Dudchenko, M. Plakhotnyk // Algebra and Discrete Mathematics. — 2012. — Vol. 13, № 1. — С. 43–51. — Бібліогр.: 5 назв. — англ. |
| work_keys_str_mv |
AT dudchenkoi alinearalgorithmofcheckingofthegraphconnectness AT plakhotnykm alinearalgorithmofcheckingofthegraphconnectness AT dudchenkoi linearalgorithmofcheckingofthegraphconnectness AT plakhotnykm linearalgorithmofcheckingofthegraphconnectness |
| first_indexed |
2025-11-25T22:45:08Z |
| last_indexed |
2025-11-25T22:45:08Z |
| _version_ |
1850570601774710784 |
| fulltext |
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 13 (2012). Number 1. pp. 43 – 51
c© Journal “Algebra and Discrete Mathematics”
A linear algorithm of checking
of the graph connectness
Irina Dudchenko, Makar Plakhotnyk
Communicated by V. V. Kirichenko
Abstract. An algorithm of sorting of all simply laced graph
such that subalgorithm of checking of that the graph is connected
is of linear dependence on the number of vertices of the graph.
1. Introduction
The problem of checking the fact that given graph is connected is
at least so actual as studying of connected graphs is actual itself. This
problem naturally appears during solving problems which lead to sorting
of all the graphs and considering of those which are connected. So, in
[5] there is a list of all quivers with not more then 4 vertices, and it is
the illustration of the actuality of the problem of their description and of
considering problems of their sorting and properties. Problems which in
fact are reduced to sorting of matrices of strongly connected quivers are
considered also in [2] -[4].
Without loosing the generality assume that the graph is simply laced,
i.e. it does not have loops and multiple edges.
For convenience of further computations assume that vertices of the
graph are numerated and so we may identify the graph with its adjacency
matrix. Till the end of the work assume that A = (αij) is adjacency matrix
of the graph under consideration and n is the number of its vertices.
2000 Mathematics Subject Classification: ????.
Key words and phrases: ????.
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
44 Linearly checking the graph connectness
Connected quivers are interesting because their adjacency matrix
satisfies the condition of Frobenius theorem [1, p. 355], which describes
the canonical form of nonnegative matrix.
From the other hand for checking the fact is connected the non oriented
graph with given adjacency matrix there is known algorithm which have
quadratic speed.
Remind this algorithm. Its idea is to check is it correct that it is
possible to start from the vertex number 1 and to come to any other
vertex of the graph.
Algorithm 1. 1. Consider an array M , and input into this array all the
vertices of graph such that there are arrows which go into these vertices
(i.e. input into the array numbers which are equal to numbers of those
vertices for which some arrows go into them).
2. Consider the following iteration process. During each iteration we
will add to the array M all vertices, which are conjugate with some vertex
which is in the array.
3. After making the iteration step we will check if we have added any
new vertex to the array M . Is yes then come to the next iteration, if no
then check are all the vertices of the graph belong to M .
4. If it will appear that all vertices of the graph belong to M then make
conclusion that graph is connected, otherwise it is not connected.
Example 1. Consider the graph with n vertices as below
• • . . . • • .
Calculate the necessary number of operations for answering the question
on that this graph connected or not.
At the very beginning there is only number 2 in the array M . During
each iteration there is exactly one number (one vertex) which is added to
M and so it is necessary to do n− 1 iterations.
As each iteration needs at least n memory accesses to matrix A, then
all the algorithm needs at least n2 memory accesses to matrix A.
That is why the speed of the algorithm is at least quadratic.
The main result of this work is proposing of such algorithm of
The main result of the work is proposing of such algorithm of sorting
of non isomorphic graphs such that its subalgorithm of checking the their
connectness is of linear speed.
Note that renumbering of graph vertices, specified with the permutation
σ corresponds to permutating of lines and columns of the same matrix,
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
I . Dudchenko, M. Plakhotnyk 45
which is defined with the same permutation σ. The matrix which is
obtained in such a way we will call the result of an action of permutation
of the permutation σ on the former matrix.
It is known that action of the permutation on the matrix saves a lot
of its properties such as characteristic polynomial and spectra.
2. Preliminary notes
Describe how we understand the algorithm of checking that graph
which is given by its adjacency matrix is connected.
Under the matrix A = (αij) with dimension n we understand an
array of numbers such that for each its element are defined such actions
as checking of equality (inequality) of this element and zero, going to
neighbour element in the the same line or in in the same column etc.
During the formulation of ideas of this article we will let us such word
combinations as “move in the line” or “move in the row”. The meaning of
these word combinations is successive increase of the variable which notes
the number of a line or a row of an element of the matrix which is under
consideration.
We do not pay attention to the fact that the start of consideration
of the element αi,j+1 after the element αi,j needs less time then start of
consideration of the element αi+1,j after the element αi,j . The heart of
the note is the following. Traditionally n× n matrix in programming is
considered as a table with n lines and n columns. But in fact the matrix
is an array (a vector) V = (vi) with n2 elements and matrix element
αij is the same as vector element vn(i−1)+j . Of course, matrix elements
αi,j and αi,j+1 correspond to neighbour vector V elements vn(i−1)+j and
vn(i−1)+j+1 and in the same time analogous statement is wrong for matrix
A elements αi,j and αi+1,j . Note ones more that we do not consider and
do not appreciate the mentioned difference and assume that time for
consideration of some element of the matrix is independent of the elements
which was under consideration before this.
Also the connectness of the graph is connected with the notion of
decomposability of the matrix, which was presented in [1, p. 352]. Remind
that matrix A in called decomposable if there exist a permutation σ such
that the result A′ of action of this permutation on the matrix A is of the
form
A′ =
(
B 0
C D
)
, (1)
where B and D - are square matrices.
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
46 Linearly checking the graph connectness
There is the obvious property of an adjacency matrix of a connected
graph.
Lemma 1. Graph is connected if and only if its adjacency matrix is
undecomposable.
This lemma is an immediate corollary of the definition of a connected
graph and the definition of adjacency matrix.
3. Canonical form and almost canonical form
of the matrix
Somehow or other but the setting of the problem which is under
consideration in the work is the following. One needs to sort all non
isomorphic quivers and find the answer some question (for example the
number of edges, index etc.), which has algorithmically solution.
The idea of solution is to propose the canonical form of the matrix in
the class of all conjugate matrices of isomorphic graphs and so consider
only matrices of canonical form instead of considering matrices of all
graphs.
Definition 1. Call the adjacency matrix of the graph one of canonical
form, if it is maximal in the cense of lexicographical ordering in the set
of those matrices which correspond to the same isomorphic graphs set.
Note that matrices from mentioned set can be obtained one from
another by permuting of lines and columns.
Definition 2. The rectangle block of almost canonical form is
such rectangle submatrix B of matrix A which is consisted from some first
lines of square matrix A and satisfy the following inductive definition:
1. A line whose the first element is 0 and which contains 1 after 0 only
one time is a rectangle block of almost canonical form.
2. Let some number of first lines of the matrix A is a rectangle block
of almost canonical form. The rectangle matrix B1 which is constructed
by adding of one line of A to this block is a rectangle block of almost
canonical form if it can not be increased in the cense of lexicographical
order by acting on the matrix A with some permutation σ such that do
not move lines from B1.
Definition 3. Matrix is of the almost canonical form, if it is a rectangle
block of almost canonical form as its submatrix.
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
I . Dudchenko, M. Plakhotnyk 47
Note that there is and unique matrix of canonical form in the those
matrices which can be obtained from some given matrix with acing of
all permutations. Nevertheless there can be many matrices of almost
canonical form. Matrix of canonical form can be characterized with the
following lemma.
Lemma 2. The adjacency matrix A of the graph is of almost canonical
from if and only if it does not contain submatrices of the form
F =
(
x x
0 1
)
, (2)
above its diagonal, where x is a column which starts with the first line of
A all whose elements are equal to x ∈ {0, 1}. Also left lower 0 of F is not
diagonal element of A.
Note that columns x in the formulation can not be just numbers.
Example 2. Give the example of matrix matrix in almost canonical form
which contains the detailed submatrix of the form (2), is x is a number.
A =
0 1 1 1 0
1 0 1 1 1
1 1 0 0 1
1 1 0 0 0
0 1 1 0 0
.
It is obvious that matrix is of the almost canonical form.
During the solution of the given problem on the matrices ordering con-
sider only matrices of canonical form with ordering them in lexicographic
order. For each of them check its connectness.
The almost canonical form of the adjacency matrix has the following
important property.
Theorem 1. If conjugate matrix of the graph is of almost canonical from
then graph is connected if and only if matrix is not of the form (1).
Proof. The sufficient of theorem condition for the non connectness of the
graph is obvious.
In fact the theorem states that if graph is not connected and its
adjacency matrix is in almost canonical form them it is in the form (1).
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
48 Linearly checking the graph connectness
As matrix A is is almost canonical form then its the first line is of the
form
(0 1 . . . 10 . . . 0).
Let i - be the number of a vertex which corresponds to the last number
1 in a line. As graph is not directed then make conclusion about possibility
to connect the first vertex with all others which have numbers 2, . . . , i.
Correspond path looks like 1 → 2 → 1 → 3 → 1 → . . . → i.
Existence of such path is equal to existence of the subgraph
Γ1 : 2
1 3
i
Answer the question on possibility to connect the graph Γ1 with the
vertex number i+ 1.
So, the first two lines of matrix A are as following
(
0 1 1 . . . 1 1 . . . 1 0 . . . 0
∗ 0 1 . . . 1 0 . . . 0 ?
)
,
where question-mark means an element α2 i+1.
As the matrix A is of almost canonical form then for its the second
line one have the following proposition. If α2 i+1 = 0 then α2 k = 0 for all
k > i. If it is not so (i.e. α2 i+1 = 0, but α2 s = 1 for some s), then one
can act with permutation τ = (i+ 1, s) on the matrix A. After this the
first line will not be changed but second line will increase in the cense of
lexical ordering which contradicts to that A is in almost canonical form.
The analogous reasoning are correct for each other line of A for which
αp i+1 = 0 till this condition holds. So, consider two cases - if such p exists
and if not.
It does not exist such p that αp i+1 = 0 then matrix A is of the form (1),
where B is a square matrix of dimension i, and D is square matrix of
dimension n− i.
That is why consider the case when there exists a number p such that
αp i+1 = 1 and let p be the lowest number with this property (this means
that p ≤ i). In this case the matrix will look like as follows, where bold
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
I . Dudchenko, M. Plakhotnyk 49
font in separate cell is an element αp i+1, which is equal to 1.
0 1 · · · 1 0 · · · 0
0
...
... · · ·
...
. . . 0 · · · 0
0 1
0
...
.
Like as during studying of the properties of the second column of the
matrix and paying attention to the almost canonical form of the matrix
make a conclusion that the line number s have the following property.
After an element αp i+1 there is a series of 1-s and all other elements of
the line number i+ 1 are equal to 0.
Let q be a maximal number such that αp q = 1. It is obvious that
q ≥ i+ 1. We have that the quiver, which is under consideration, contains
a connected subquiver
Γ2 : 2 i+ 1
1 p i+ 2
i q
The existence of subquiver Γ2 means the following form of some the
first line of A
0 1 · · · 1 0 · · · 0 0 · · · 0
0
...
... · · ·
...
... · · · 0
. . . 0 · · · 0 0 · · · 0
0 1 · · · 1 0 · · · 0
0
... ?
.
With repeating if necessary (may be more then once) the same as we
have made for α2 i+1 for the element αp+1 q+1 obtain either a graph Γ3 as
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
50 Linearly checking the graph connectness
follows
Γ3 : 2 i+ 1 r
1 p . . .
i q n
or make a conclusion that matrix A is of the form (1).
The last finishes the proof.
4. The algorithm of checking the connectness
A theorem 1 which is proved (especially its proving) lets us to formulate
the algorithm of checking the connectness of the graph and this algorithm
will de linearly dependent on n.
We will find the path from the first vertex to the last one (n-th) which
goes through all the vertices.
Algorithm 2. 1. Go through the first line of the matrix A and find the
first element α1 j such that α1 j = 1 and α1 j+1 = 0. If such element does
not exist and α1n = 1, then graph is connected. If the necessary element
does not exist and α1n = 0, then graph is not connected. Is the element
α1j with the property mentioned above is found then go to the next step.
2. After finding the element which we have called α1j, find the first
nonzero element in the column number j + 1. If we have found it (call
αk, j+1), the go through the block of ones in the line number k, find there
the last 1 and repeat all the actions which we have done for α1j.
3. This process will finished with either coming to the last column or
with the conclusion that graph is connected. It we will not come to the last
column of the matrix then conclude that graph is not connected.
As answering the question about being/unbeing equal to zero of some
elements of the matrix A we mowed only right and down, then we have
made not more then 2n checkings which gives that algorithm of checking
the connectness of the graph is not quadratic but not linear.
References
[1] F.R.Gantmaher, Matrices theory // Nauka. - M. - 1966, - 576 p. (in russian)
[2] I. V. Dudchenko, Strongly connected quivers, their indices and eigenvalues //
Kyiv. - 2007, - 28p. (Preprint of NASU mathematical inst.) (in russian)
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
I . Dudchenko, M. Plakhotnyk 51
[3] I. V. Dudchenko, Fujiita Algebras properties // Sci. Bull. of National Dragomanov
Univ. - Ser: Phys.-Math. - 2005. - N 6. - p. 126-130. (in ukrainian)
[4] I. V. Dudchenko, Fujiita Algebras // Bull. of Taras Shevchenko National University
of Kyiv. - Ser: Phys.-Math. - 2011. - N 2, p. and N 3 (in progress) (in ukrainian)
[5] F. Harari, Graph theory, M. 1973 (in russian)
Contact information
I. Dudchenko Sloviansk pedagogical university, Generala
Batuka str.,19, 84116, Sloviansk, Ukraine
E-Mail: dudchira@meta.ua
M. Plakhotnyk Department of Mechanics and Mathemat-
ics, Kyiv National Taras Shevchenko Univ.,
Volodymyrska str., 64, 01033 Kyiv, Ukraine
E-Mail: makar_plakhotnyk@ukr.net
Received by the editors: 02.10.2011
and in final form 24.10.2011.
I. Dudchenko, M. Plakhotnyk
|