Size of the memory for storage of ordered rooted graph
The paper considers boundaries of memory necessary and sufficient for storage of undirected ordered rooted connected graphs, both numbered and unnumbered. The introduction contains the basic definitions and the problem statement. A graph is rooted if one of its vertices is marked as a root. A graph...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Ivannikov Institute for System Programming of the Russian Academy of Sciences
2018-10-01
|
| Series: | Труды Института системного программирования РАН |
| Subjects: | |
| Online Access: | https://ispranproceedings.elpub.ru/jour/article/view/251 |
| _version_ | 1828454176111198208 |
|---|---|
| author | I. B. Burdonov A. S. Kossatchev |
| author_facet | I. B. Burdonov A. S. Kossatchev |
| author_sort | I. B. Burdonov |
| collection | DOAJ |
| description | The paper considers boundaries of memory necessary and sufficient for storage of undirected ordered rooted connected graphs, both numbered and unnumbered. The introduction contains the basic definitions and the problem statement. A graph is rooted if one of its vertices is marked as a root. A graph is ordered if for each of its vertices all the incident edges are ordered (numbered). A graph is numbered if all its vertices are numbered with different integer numbers (from 0 to n -1, where n is the number of vertices). Two undirected ordered graphs G and G` are weakly isomorphic if there exists a one-to-one correspondence between their vertices, for which corresponding vertices has the same degrees (numbers of incident edges) and two edges having corresponding ends and the same numbers in these ends, also have the other ends corresponding. Isomorphism of rooted graphs should also correspond their roots. Isomorphism of numbered graphs should also correspond the vertices with the same numbers. Graphs are considered up to weak isomorphism. It is shown that the memory necessary and sufficient for storage of any graph has the size Q( mlogn ) for numbered graphs, Q( n +( m - n +1) logn ) for unnumbered graphs with the number of vertices n and the number of edges m , and Q( n2 logn ) for graphs without multiple edges and loops with the number of vertices n . It is also shown that the memory sufficient for storage of an edge sequence of length O ( n ) or a spanning tree, has the O ( nlog ( n D)) or O ( nlog D) size, respectively, where D is the maximum vertex degree. |
| first_indexed | 2024-12-11T00:18:24Z |
| format | Article |
| id | doaj.art-014885cb1c1f42c9851e67fae6579da6 |
| institution | Directory Open Access Journal |
| issn | 2079-8156 2220-6426 |
| language | English |
| last_indexed | 2024-12-11T00:18:24Z |
| publishDate | 2018-10-01 |
| publisher | Ivannikov Institute for System Programming of the Russian Academy of Sciences |
| record_format | Article |
| series | Труды Института системного программирования РАН |
| spelling | doaj.art-014885cb1c1f42c9851e67fae6579da62022-12-22T01:27:51ZengIvannikov Institute for System Programming of the Russian Academy of SciencesТруды Института системного программирования РАН2079-81562220-64262018-10-0129272610.15514/ISPRAS-2017-29(2)-1251Size of the memory for storage of ordered rooted graphI. B. Burdonov0A. S. Kossatchev1Институт системного программирования РАНИнститут системного программирования РАНThe paper considers boundaries of memory necessary and sufficient for storage of undirected ordered rooted connected graphs, both numbered and unnumbered. The introduction contains the basic definitions and the problem statement. A graph is rooted if one of its vertices is marked as a root. A graph is ordered if for each of its vertices all the incident edges are ordered (numbered). A graph is numbered if all its vertices are numbered with different integer numbers (from 0 to n -1, where n is the number of vertices). Two undirected ordered graphs G and G` are weakly isomorphic if there exists a one-to-one correspondence between their vertices, for which corresponding vertices has the same degrees (numbers of incident edges) and two edges having corresponding ends and the same numbers in these ends, also have the other ends corresponding. Isomorphism of rooted graphs should also correspond their roots. Isomorphism of numbered graphs should also correspond the vertices with the same numbers. Graphs are considered up to weak isomorphism. It is shown that the memory necessary and sufficient for storage of any graph has the size Q( mlogn ) for numbered graphs, Q( n +( m - n +1) logn ) for unnumbered graphs with the number of vertices n and the number of edges m , and Q( n2 logn ) for graphs without multiple edges and loops with the number of vertices n . It is also shown that the memory sufficient for storage of an edge sequence of length O ( n ) or a spanning tree, has the O ( nlog ( n D)) or O ( nlog D) size, respectively, where D is the maximum vertex degree.https://ispranproceedings.elpub.ru/jour/article/view/251неориентированный графупорядоченный графнумерованный графкорневой графпредставление графаперечисление графов |
| spellingShingle | I. B. Burdonov A. S. Kossatchev Size of the memory for storage of ordered rooted graph Труды Института системного программирования РАН неориентированный граф упорядоченный граф нумерованный граф корневой граф представление графа перечисление графов |
| title | Size of the memory for storage of ordered rooted graph |
| title_full | Size of the memory for storage of ordered rooted graph |
| title_fullStr | Size of the memory for storage of ordered rooted graph |
| title_full_unstemmed | Size of the memory for storage of ordered rooted graph |
| title_short | Size of the memory for storage of ordered rooted graph |
| title_sort | size of the memory for storage of ordered rooted graph |
| topic | неориентированный граф упорядоченный граф нумерованный граф корневой граф представление графа перечисление графов |
| url | https://ispranproceedings.elpub.ru/jour/article/view/251 |
| work_keys_str_mv | AT ibburdonov sizeofthememoryforstorageoforderedrootedgraph AT askossatchev sizeofthememoryforstorageoforderedrootedgraph |