Clever Geek Handbook
📜 ⬆️ ⬇️

Pseudoles

1-forest (maximum pseudo-forest) formed by three 1-trees

In graph theory, pseudo-processes is an undirected graph [1] , in which any connected component has at most one cycle . That is, it is a system of vertices and edges connecting pairs of vertices, such that no two cycles have common vertices and cannot be connected by a path. A pseudo - tree is a connected pseudo- tree .

The names are taken by analogy with well-known trees and forests (a tree is a connected graph without cycles, a forest is a union of disconnected trees). Gabov and Taryan [2] ascribe the study of pseudo-books in the 1963 book of Danzig on linear programming , in which pseudo-wheels appear in the solution of certain problems of traffic flows [3] . Pseudo-processes also form theoretical graph models of functions and appear in some algorithmic problems. Pseudo-wolves are sparse graphs — they have a very small number of edges relative to the number of vertices, and their matroid structure allows some other families of rare graphs to be decomposed into a union of forests and pseudo-wolves. The name "psevdoles" came from an article by Picard and Kerann [4] .

Content

Definitions and structure

We define an undirected graph as a set of vertices and edges , such that each edge contains two vertices (possibly coinciding) as end points. That is, multiple edges (edges with the same finite vertices) and loops (edges whose finite vertices coincide) are allowed [1] . A graph subgraph is a graph formed by a subset of vertices and edges, such that any edge in this subset has finite vertices in the subset of vertices. The connected component of an undirected graph is a subgraph consisting of vertices and edges that can be reached by following the edges, starting from one starting vertex. A graph is connected if any vertex or edge can be reached by following from any other vertex or edge. A cycle in an undirected graph is a connected subgraph in which any vertex is incident to exactly two edges or is a loop.

 
21 graphs with one cycle and a maximum of six vertices

A pseudo-diagram is an undirected graph in which each connected component contains at most one cycle [5] . Equivalently, it is an undirected graph in which each connected component of the edges has no more than vertices [6] . Components that do not have cycles are simply trees , and components that have a single cycle are called 1-trees or single-cycle graphs . That is, a 1-tree is a connected graph containing exactly one cycle. A pseudo-wale with a single connected component (usually called a pseudo - tree , although some authors define a pseudo-tree as a 1-tree) is either a tree or a 1-tree. In the general case, pseudo-trees can contain several connected components, all of which are trees or 1-trees.

If we remove from the 1-tree one of the edges of the cycle, we end up with a tree. In the opposite direction, if we add a new edge to the tree connecting any two vertices, we get a 1-tree. The path in the tree connecting the two end points of the added arc, together with the added arc itself, forms a single cycle of the 1-tree. If we add to the 1-tree an edge connecting one of the vertices of the tree with the newly formed vertex, as a result, we again get a 1-tree with another vertex. Another method of constructing a 1-tree begins with a single cycle, and vertices are successively added to the 1-tree vertex an arbitrary number of times. The edges of any 1-tree can be divided in one way into two subgraphs, one of which is a cycle and the second is a forest, with each tree of the forest containing exactly one vertex of the cycle [7]

We also study somewhat narrower types of pseudo-wolves.

A 1-forest , sometimes called a maximal pseudo-forest , is a forest to which one cannot add an edge without forming a graph with more than one cycle. If a pseudo-forest contains a tree as one of the components, it cannot be a 1-forest, because you can add an edge to this component to form a cycle in this component or add an edge that will attach the tree to another component. Thus, 1-forests are exactly pseudo-wolves in which any component is a 1-tree.
The core axis of a non - oriented graph G is a core subgraph that is a pseudo- axis , that is, the pseudo- axis of G containing all vertices of G. Such pseudo-processes are not required to have any edges, because, for example, an empty subgraph (that is, containing all vertices of the graph G and not having any edges) is a pseudo-forest (and its components are trees, each of which consists of a single vertex ).
The maximum pseudo-processes of the graph G are the subgraphs of the graph G , which are pseudo-processes which are not contained in any larger pseudo-field contained in G. The maximum pseudo-tree of a graph G is always a spanning pseudo-tree, but the converse is not true. If G has no connected components that are trees, then its maximal pseudo-paths are 1-forests, but in the case when the graph G contains a tree as a component, its maximal pseudo-patterns will not be 1-forests. More precisely, in any graph G its maximal pseudo-waves consist of all the forests of the graph G together with one or more 1-tree covering the remaining vertices of the graph G.

Oriented pseudo-wheels

Versions of these definitions are also used for directed graphs . Like undirected graphs, oriented graphs consist of vertices and edges, but each edge has a direction (oriented edge is usually called an arc). Oriented pseudo-waves is a directed graph in which each vertex has at most one outgoing arc. That is, the graph has a degree of outcome that does not exceed one. An oriented 1-forest , often called a functional graph (see below ), and sometimes a maximum oriented pseudo-forest , is a directed graph in which each vertex has an outgoing degree exactly equal to one [8] . If D is an oriented pseudo-diagram, the undirected graph formed by removing directions from the edges of the graph D is an non-oriented pseudo-curve.

Edge number

Any pseudo-pattern on a set of n vertices has a maximum of n edges, and any maximal pseudo-pattern on a set of n vertices has exactly n vertices. In the opposite direction, if the graph G has the property that for any subset S of the vertices of the graph the number of edges in the generated subgraph of the graph S does not exceed the number of the vertices of the graph S , then G is a pseudo-sequence. 1-trees can be defined as connected graphs with the same number of vertices and edges [2] .

For families of graphs, if a family of graphs has the property that every subgraph of a graph in a family belongs to the same family and every graph in the family has no more edges than vertices, then the family contains only pseudo-paths. For example, any subgraph of a track (a graph drawn in such a way that any pair of edges has one intersection point) is also a track, so that Conway’s hypothesis that any track has no more edges than vertices can be restated that every track is a pseudo-forest. More precisely, if the hypothesis is true, then the tracks are exactly pseudo-processes without cycles with four vertices and a maximum of one cycle with an odd number of vertices [9] [10] .

Strain and Teran [11] generalized the properties of sparsity in the definition of pseudo-paths — it defines a graph as ( k , l ) -responsive if any non-empty subgraph with n vertices has a maximum kn - l edges, and ( k , l ) -dense if ( k , l ) is rarefied and has exactly kn - l edges. Thus, pseudo-processes are (1, 0) -free graphs, and maximal pseudo-processes are (1, 0)-dense graphs. Some other important families of graphs can be defined for other values ​​of k and l , and if l ≤ k , ( k , l ) -free graphs can be described as graphs formed by the union of l forests without common edges and k - l pseudo-forests [12] .

Almost any fairly rare random graph is a pseudo-worm [13] . That is, if c is a constant (0 < c <1/2) and P c ( n ) is the probability that the graph chosen randomly among graphs with n vertices and cn edges is pseudo-wiring, then P c ( n ) tends to unity in limit with growth n . However, for c > 1/2, almost any random graph with cn edges has a large component that is not single-cycle.

Enumeration

A graph is simple if it has no loops and multiple edges. The number of simple 1-trees with n labeled vertices is [14]

nΣk=onen(-one)k-onekΣnone+⋯+nk=nn!none!⋯nk!((none2)+⋯+(nk2)n).{\ displaystyle n \ sum _ {k = 1} ^ {n} {\ frac {(-1) ^ {k-1}} {k}} \ sum _ {n_ {1} + \ cdots + n_ {k } = n} {\ frac {n!} {n_ {1}! \ cdots n_ {k}!}} {\ binom {{\ binom {n_ {1}} {2}} + \ cdots + {\ binom {n_ {k}} {2}}} {n}}.}  

Values ​​for n up to 18 can be found in the sequence A057500 Encyclopedia of integer sequences .

The number of maximal oriented pseudo-paths with n vertices in which loops are allowed is n n , since for any vertex there are n possible finite vertices of outgoing arcs. used this fact for bijective proof [15] of the Cayley formula that the number of non-oriented trees on n vertices is n n - 2 by finding a bijection between the maximal oriented pseudo-forests and non-oriented trees with two different vertices [16] . If loops are allowed, the number of maximal oriented pseudo-paths is ( n - 1) n .

Function Graphs

 
Function on the set {0,1,2,3,4,5,6,7,8} on itself and the corresponding functional graph

Oriented pseudo-processes and maps to themselves are in some sense mathematically equivalent. Any mapping ƒ on a set X onto itself (that is, an endomorphism on X ) can be interpreted as a definition of an oriented pseudo-sequence that has an arc from x to y , when ƒ ( x ) = y . The resulting oriented pseudo-axis is maximal and can include loops if for some x ƒ ( x ) = x . The exclusion of loops leads to non-maximal pseudo-wolves. In the opposite direction, any maximal oriented pseudo-axis defines a mapping ƒ, for which ƒ ( x ) equals the final vertex of the arc originating from x , and any non-maximal oriented pseudo-mass can be made maximal by adding loops and converting it to a function in the same way. For this reason, maximal oriented pseudo-wheels are sometimes called functional graphs [2] . Representing a function as a functional graph gives a convenient language for describing properties that are not easy to describe from the point of view of function theory. Such a technique is especially useful for tasks that use that correspond to paths in graph theory.

The search for cycles , the task of tracing paths in a functional graph for finding a cycle in it, has applications in cryptography and as part of the Pollard po-algorithm for factoring integers and as a method for finding conflicts in cryptographic hash functions . In these applications, предполагается is assumed to be random. and [17] studied the properties of functional graphs obtained from random mappings. In particular, it follows from one of the variants of the birthday paradox that in a random functional graph with n vertices, the path starting from a randomly selected vertex usually loops after O (√ n ) steps. Konyagin et al. Carried out an analysis and computational statistical studies [18] .

Martin, and Wolfram [19] investigated pseudo-wheels simulating the dynamics of cellular automata . These are functional graphs, they called them state transition diagrams , they have one vertex for each possible configuration in which cells of the cellular automaton can be located, and arcs connect each configuration that is derived from it according to the rules of the cellular automaton. You can obtain the properties of an automaton from the structure of these diagrams, such as the number of components, the length of finite cycles, the depth of the trees connecting the non-finite states of these cycles, or the symmetry of the diagram. For example, any vertex without an incoming arc corresponds to the Garden of Eden , and vertices with a loop correspond to a still life .

Another early application of functional graphs is in chains [20] , used to study Steiner triples systems [21] [22] [23] . The chain of system of triples is a functional graph containing a vertex for each possible triple of symbols. Each triple pqr is represented by a function ƒ in stu , where pqs , prt and qru are triples belonging to the system of triples and contain the pairs pq , pr and qr, respectively. It was shown that chains are a powerful invariant of the system of triples, although their calculation is cumbersome.

Bicyclic Matroid

A matroid is a mathematical structure in which certain sets of elements are defined as independent, in the sense that independent sets satisfy properties that model the properties of linear independence in a vector space . One of the standard examples of matroids is a , in which independent sets are sets of edges in the forests of a graph. The matroid structure of forests is important for the algorithms for computing the minimum spanning tree of a graph. Similarly, it is possible to define matroids for pseudo-roads.

For any graph G = ( V , E ), we can define a matroid on the edges of the graph G , in which the set of edges is independent if and only if this set forms a pseudo-curve. This matroid is known as the graph G [24] [25] . The minimal dependent sets for this matroid are minimal connected subgraphs of the graph G that have more than one cycle, and these subgraphs are sometimes called bicycles. There are three possible types of bicycles - the theta graph has two vertices connected by three paths that have no internal common points, the “eight” consists of two cycles having one common vertex, and the “handcuffs” are formed by two cycles that have no common vertices connected by [ 26] . A graph is a pseudo-forest if and only if it does not contain a bicycle as a subgraph [11] .

Forbidden Minors

 
“Butterfly” (left) and diamond (right), forbidden minors of pseudo-roads

Formation of the pseudo-wheel minor by tightening some edges and removing some other edges forms a new pseudo-wheel. Thus, the family of pseudo-processes is closed in minors, and it follows from the Robertson-Seymour theorem that pseudo-processes can be described in terms of a finite set of forbidden minors , similar to Wagner's theorem for describing planar graphs as graphs that do not have either a full K 5 graph or a full bipartite graph K 3.3 as minors. As discussed earlier, any graph that is not a pseudo-wolf contains “handcuffs”, “eight” or “theta” as a subgraph. Any “handcuffs” and “eights” can be drawn to a “butterfly” (“eight” with five vertices), and any “theta” graph can be pulled to a “ diamond ” (“theta” graph with four vertices) [27] , so that any graph that is not a pseudo-forest contains either a butterfly or a diamond as a minor, and only these graphs are minimal graphs not belonging to the family of pseudo-waves. If we prohibit only “diamond”, but not “butterfly”, we get a wider family of graphs consisting of and an isolated association of a set of “cacti” [28] .

If we consider multigraphs with loops , there is only one forbidden minor, a vertex with two loops.

Algorithms

The early algorithmic application of pseudo-processes used the network simplex algorithm and its application to the generalized problem of flows in networks to simulate the transformation of products from one type to another [3] [29] . In these tasks, a transport network is defined in which vertices model each product, and edges model the admissibility of transformation from one product to another. Each edge is marked by bandwidth (the amount of product that can be converted per unit of time), flow (conversion speed between products) and price (how much we lose when converted per unit of product). The task is to determine how much each product needs to be converted on each arc of the transportation network in order to minimize the price or maximize revenue without breaking the limits and not allowing any type of product to remain unused. This type of problem can be formulated as a linear programming problem and solved using the simplex method . Intermediate solutions derived from this algorithm, as well as the final optimal solution, have special structures — each arc of the transport network is either not used, or uses the maximum throughput value, with the exception of a subset of arcs that form a core pseudo-axis of the transport network, and on this subset of the arc flow can range from zero to maximum throughput. In this application, single-cycle graphs are sometimes also called supplemented trees , and maximal pseudo-weights are called supplemented forests [29] .

The minimum spanning pseudo-forest task uses the finding of a spanning pseudo-wheel of minimum weight in a larger graph G with weights. Due to the matroid structure of pseudo-wheels, maximum pseudo-wheels with minimal weight can be found using greedy algorithms like the problem of finding the minimum spanning tree . However, Gabov and Taryan found a more efficient linear time approach for this case [2] .

The pseudo-woodness of the graph G is determined by analogy with the woodness as the minimum number of pseudo- paths into which the edges can be divided. Equivalently, this is the minimum number k , such that the graph G is ( k , 0) -reduced, or the minimum number k , such that the edges of the graph G can be given directions, so that the resulting directed graph will have an outcome not exceeding k . Due to the matroid structure of the pseudo-wheel, pseudo-woodness can be calculated in polynomial time [30]

A random bipartite graph with n vertices on each of its lobes with cn edges selected randomly and independently for each pair of n 2 possible pairs of vertices is most likely a pseudo-wale with a constant c strictly less than one. This fact plays a key role in the analysis of [31] , the data structure for finding key-value pairs by viewing one of the two hash tables at the location determined by the key — you can form a “pair graph” whose vertices correspond to the position location in the hash tables, and the edges link two locations in which one of the keys can be found. Pair hashing finds all keys if and only if the pair graph is a pseudo-forest [32] .

Pseudo-processes also play a key role in parallel graph coloring and related problems [33] [34] .

Notes

  1. ↑ 1 2 The undirected graphs considered here are multigraphs or pseudographs, not simple graphs .
  2. ↑ 1 2 3 4 Gabow, Tarjan, 1988 .
  3. ↑ 1 2 Dantzig, 1963 .
  4. ↑ Picard, Queyranne, 1982 .
  5. ↑ This definition, for example, uses Gabov and Westermann ( Gabow, Westermann (1992 )).
  6. ↑ This definition is used by Gabov and Taryan ( Gabow, Tarjan (1988 )).
  7. ↑ See, for example, the proof of Lemma 4 in the article by Alvarez, Bles and Sern ( Àlvarez et al (2002 )).
  8. ↑ Kruska, Rudolf and Snir ( Kruskal et al (1990 )) instead use the inverse definition in which each vertex has an incoming power of one. The resulting graphs, which they call single-cycle , are transposed graphs considered in this article.
  9. ↑ Woodall, 1969 .
  10. ↑ Lovász et al, 1997 .
  11. ↑ 1 2 Streinu, Theran, 2009 .
  12. ↑ Whiteley, 1988 .
  13. ↑ Bolobás ( 1985 ). See, in particular, Corollary 24, on p.120, on the boundary of the number of vertices belonging to single-cycle components in a random graph, and Corollary 19, p.113, on the boundary of the number of different labeled single-cycle graphs.
  14. ↑ Riddell (1951 ); see A057500 in the Encyclopedia of Integer Sequences .
  15. ↑ About the method of bijective proof can be found in the article of Vershik ( Vershik (1986 ))
  16. ↑ Aigner, Ziegler, 1998 .
  17. ↑ Flajolet, Odlyzko, 1990 .
  18. ↑ Konyagin et al, 2016 .
  19. ↑ Martin, Odlyzko, Wolfram, 1984 .
  20. ↑ In English version - trains
  21. ↑ White, 1913 .
  22. ↑ Colbourn, Colbourn, Rosenbaum, 1982 .
  23. ↑ Stinson, 1983 .
  24. ↑ Simoes-Pereira, 1972 .
  25. ↑ Matthews, 1977 .
  26. ↑ Glossary of Signed and Gain Graphs and Allied Areas
  27. ↑ For this terminology, see the list of small graphs from Information Systems on Graph Class Inclusions . However, a butterfly may belong to another family of graphs associated with hypercubes .
  28. ↑ El-Mallah, Colbourn, 1988 .
  29. ↑ 1 2 Ahuja, Magnanti, Orlin, 1993 .
  30. ↑ Gabow, Westermann (1992 ). See also fast Kovalik approximation schemes ( Kowalik (2006 )).
  31. ↑ Generally speaking, the term is unsuccessful, but it stuck in Russian-language literature (as a direct translation of cuckoo hashing ). Apparently, the term arose because of the pairing "Koo-koo" The method should be called pairwise or two-step hashing.
  32. ↑ Kutzelnigg, 2006 .
  33. ↑ Goldberg, Plotkin, Shannon, 1988 .
  34. ↑ Kruskal et al, 1990 .

Literature

  • Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin. Network Flows: Theory, Algorithms and Applications. - Prentice Hall, 1993. - ISBN 0-13-617549-X .
  • Martin Aigner, Günter M. Ziegler. Proofs from THE BOOK . - Springer-Verlag , 1998. - p. 141–146.
  • Carme Àlvarez, Maria Blesa, Maria Serna. Proc. 14th ACM Symposium on Parallel Algorithms and Architectures . - 2002. - p. 183–197. - DOI : 10.1145 / 564870.564903 .
  • Béla Bollobás. Random graphs. - Academic Press, 1985.
  • Marlene J. Colbourn, Charles J. Colbourn, Wilf L. Rosenbaum. Trains: an invariant for Steiner triple systems // . - 1982. - T. 13 . - p . 149-162 .
  • GB Dantzig. Linear Programming and Extensions. - Princeton University Press, 1963.
  • Ehab El-Mallah, Charles J. Colbourn. // IEEE Transactions on Circuits and Systems. - 1988. - V. 35 , no. 3 - p . 354–362 . - DOI : 10.1109 / 31.1748 .
  • P. Flajolet, A. Odlyzko. Advances in Cryptology - EUROCRYPT '89: Workshop on the Theory and Application of Cryptographic Techniques . - Springer-Verlag, 1990. - T. 434. - p. 329-354.
  • HN Gabow, RE Tarjan. Spanning pseudoforest // Information Processing Letters. - 1988. - V. 27 , no. 5 - p . 259-263 . - DOI : 10.1016 / 0020-0190 (88) 90089-0 . .
  • HN Gabow, HH Westermann. Forests, frames, and games: Algorithms for matroid sums and applications // Algorithmica. - 1992. - V. 7 , no. 1 . - p . 465–497 . - DOI : 10.1007 / BF01758774 .
  • AV Goldberg, SA Plotkin, GE Shannon. Parallel symmetry-breaking graphs sparse // SIAM Journal on Discrete Mathematics . - 1988. - V. 1 , no. 4 - p . 434-446 . - DOI : 10.1137 / 0401044 .
  • Sergei Konyagin, Florian Luca, Bernard Mans, Luke Mathieson, Igor E. Shparlinski. Functional Graphs of Polynomials over Finite Fields // Journal of Combinatorial Theory. - 2016. - T. 116 .
  • Ł. Kowalik. Proceedings of the International Symposium on Algorithms and Computation / Tetsuo Asano. - Springer-Verlag, 2006. - V. 4288. - P. 557–566. - (Lecture Notes in Computer Science). - DOI : 10.1007 / 11940128 .
  • Clyde P. Kruskal, Larry Rudolph, Marc Snir. Efficient parallel algorithms for graph problems // Algorithmica. - 1990. - V. 5 , no. 1 . - p . 43–64 . - DOI : 10.1007 / BF01840376 .
  • Jean-Claude Picard, Maurice Queyranne. A network flow solution is a 0–1 programming problem. - 1982. - T. 12 . - pp . 141–159 . - DOI : 10.1002 / net.3230120206 .
  • Reinhard Kutzelnigg. Fourth Colloquium on Mathematics and Computer Science. - 2006. - T. AG. - p. 403–406. - (Discrete Mathematics and Theoretical Computer Science). (inaccessible link)
  • L. Lovász, J. Pach, M. Szegedy. On Conway's thrackle conjecture // Discrete and Computational Geometry . - 1997. - V. 18 , no. 4 - p . 369-376 . - DOI : 10.1007 / PL00009322 .
  • O. Martin, AM Odlyzko, S. Wolfram. Algebraic properties of cellular automata // Communications in Mathematical Physics. - 1984. - V. 93 , no. 2 - p . 219–258 . - DOI : 10.1007 / BF01223745 . - .
  • LR Matthews. Bicircular matroids // The Quarterly Journal of Mathematics. Oxford. Second Series. - 1977. - V. 28 , no. 110 . - p . 213–227 . - DOI : 10.1093 / qmath / 28.2.213 .
  • RJ Riddell. Contributions to the Theory of Condensation. - Ann Arbor: University of Michigan, 1951. - (Ph.D. thesis). .
  • JMS Simoes-Pereira. On subgraphs as matroid cells // Mathematische Zeitschrift . - 1972. - V. 127 , no. 4 - p . 315–322 . - DOI : 10.1007 / BF01111390 . .
  • DR Stinson. A comparison of two invariants for Steiner triple systems: fragments and trains // Ars Combinatoria. - 1983. - V. 16 . - pp . 69–76 . .
  • I. Streinu, L. Theran. Sparsity-certifying Graph Decompositions // Graphs and Combinatorics . - 2009. - V. 25 , no. 2 - p . 219 . - DOI : 10.1007 / s00373-008-0834-4 .
  • HS White. Triple-systems as transformations, among triads // Transactions of the American Mathematical Society . - American Mathematical Society, 1913. - Vol. 14 , no. 1 . - p . 6–13 . - DOI : 10.2307 / 1988765 .
  • W. Whiteley. The union of matroids and the rigidity of the frameworks // SIAM Journal on Discrete Mathematics . - 1988. - V. 1 , no. 2 - p . 237–255 . - DOI : 10.1137 / 0401025 .
  • DR Woodall. Combinatorial Mathematics and Its Applications / DJA Welsh. - Academic Press, 1969. - P. 335–348. .
  • A. M. Vershik. A bijective proof of the Jacobi identity and the rearrangement of Jung diagrams // Zap. scientific this LOMI. - 1986. - T. 155 . - p . 3-6 .

Links

  • Weisstein, Eric W. Unicyclic Graph (English) on Wolfram MathWorld .
Source - https://ru.wikipedia.org/w/index.php?title=Psevdoles&oldid=98650842


More articles:

  • Andreeva, Elena Leonidovna
  • Lekerica, Jose Felix de
  • Flight Span
  • Kubasov, Valery Nikolaevich
  • Bazilevich, Alexander Ivanovich
  • Petri, Julius Richard
  • Special Needs
  • SES Ouarzazat
  • Månegarm
  • Avrosoglu, Ioannis

All articles

Clever Geek | 2019