- Skew-symmetric graph
In

graph theory , a branch of mathematics, a**skew-symmetric graph**is adirected graph that is isomorphic to its owntranspose graph , the graph formed by reversing all of its edges. The isomorphism is required to be aninvolution without any fixed points.Skew-symmetric graphs were first introduced under the name of "antisymmetrical digraphs" by harvtxt|Tutte|1967. They arise in modeling the search for alternating paths and alternating cycles in algorithms for finding

matching s in graphs, in testing whether a still life pattern inConway's Game of Life may be partitioned into simpler components, ingraph drawing , and in theimplication graph s used to efficiently solve the2-satisfiability problem.**Definition**As defined, e.g., by harvtxt|Goldberg|Karzanov|1996, a skew-symmetric graph "G" is a directed graph, together with a function σ mapping vertices of "G" to other vertices of "G", satisfying the following properties:

# For every vertex "v", σ("v") ≠ "v"

# For every vertex "v", σ(σ("v")) = "v"

# For every edge ("u","v"), (σ("v"),σ("u")) must also be an edgeOne may use the third property to extend σ to an orientation-reversing function on the edges of "G".The

transpose graph of "G" is the graph formed by reversing every edge of "G", and σ defines agraph isomorphism from "G" to its transpose. However, in a skew-symmetric graph, it is additionally required that the isomorphism pair each vertex with a different vertex, rather than allowing a vertex to be mapped to itself by the isomorphism or to group more than two vertices in a cycle of isomorphisms.A path or cycle in a skew-symmetric graph is said to be "regular" if, for each vertex "v" of the path or cycle, the corresponding vertex σ("v") is not part of the path or cycle.

**witch graphs and bidirected graphs**A skew-symmetric graph may equivalently be defined in terms of a "switch graph" (to use the terminology of harvtxt|Cook|2003), an undirected graph in which the edges incident to each vertex are partitioned into two subsets. Each vertex of the switch graph corresponds to two vertices of the skew-symmetric graph, and each edge of the switch graph corresponds to two edges of the skew-symmetric graph. This equivalence is the one used by harvtxt|Goldberg|Karzanov|1996 to model problems of matching in terms of skew-symmetric graphs; in that application, the two subsets of edges at each vertex are the unmatched edges and the matched edges. Cook visualizes the vertices of a switch graph as points where multiple tracks of a

train track come together: if a train enters a switch via a track that comes in from one direction, it must exit via a track in the other direction. The problem of finding non-self-intersecting smooth curves between given points in a train track comes up in testing whether certain kinds ofgraph drawing s are valid harv|Hui|Schaefer|Štefankovič|2004 and may be modeled as the search for a regular path in a skew-symmetric graph.A closely related concept is the

bidirected graph of harvtxt|Edmonds|Johnson|1970, a graph in which each of the two ends of each edge may be either a head or a tail, independently of the other end. A bidirected graph may be interpreted as a switch graph by letting the partition of edges at each vertex be determined by the partition of endpoints at that vertex into heads and tails; however, swapping the roles of heads and tails at a single vertex produces a different bidirected graph but the the same switch graph. For the correspondence between bidirected graphs and skew-symmetric graphs see harvtxt|Babenko|2006.To form a skew-symmetric graph from a switch graph "G", create for each vertex "v" of "G" two vertices "v"

_{0}and "v"_{1}, and let σ("v"_{"i"}) = "v"_{1 − "i"}. For each edge "e" = ("u","v") of "G", create two directed edges in the skew-symmetric graph, one oriented from "u" to "v" and one oriented from "v" to "u". If "e" is in the first subset of edges at "v", connect these two edges out of "v"_{0}and into "v"_{1}, while if "e" is in the second subset, connect these two edges out of "v"_{1}and into "v"_{0}.In the other direction, given a skew-symmetric graph "G", one may form a switch graph that has one vertex for every corresponding pair of vertices in "G" and one undirected edge for every corresponding pair of edges in "G". The undirected edges at each vertex of the switch graph may be partitioned into two subsets according to which vertex of the switch graph they go out of and come in to.A regular path or cycle of a skew-symmetric graph corresponds to a path or cycle in the switch graph that uses at most one edge from each subset of edges at each of its vertices.

**Matching**In constructing

matching s in undirected graphs, it is important to find "alternating paths", paths of vertices that start and end at unmatched vertices, in which the edges at odd positions in the path are not part of a given partial matching and in which the edges at even positions in the path are part of the matching. By removing the matched edges of such a path from a matching, and adding the unmatched edges, one can increase the size of the matching. Similarly, cycles that alternate between matched and unmatched edges are of importance in weighted matching problems.As harvtxt|Goldberg|Karzanov|1996 showed, an alternating path or cycle in an undirected graph may be modeled as a regular path or cycle in a skew-symmetric directed graph. To create a skew-symmetric graph from an undirected graph "G" with a specified matching "M", view "G" as a switch graph in which the edges at each vertex are partitioned into matched and unmatched edges; an alternating path in "G" is then a regular path in this switch graph and an alternating cycle in "G" is a regular cycle in the switch graph.harvtxt|Goldberg|Karzanov|1996 generalized alternating path algorithms to show that the existence of a regular path between any two vertices of a skew-symmetric graph may be tested in linear time. Given additionally a non-negative length function on the edges of the graph that assigns the same length to any edge "e" and to σ("e"), the shortest regular path connecting a given pair of nodes in a skew-symmetric graph with "m" edges and "n" vertices may be tested in time O("m" log "n"). If the length function is allowed to have negative lengths, the existence of a negative regular cycle may be tested in polynomial time.

Along with the path problems arising in matchings, skew-symmetric generalizations of the

max-flow min-cut theorem have also been studied (harvnb|Goldberg|Karzanov|2004; harvnb|Tutte|1967).**till life theory**harvtxt|Cook|2003 shows that a still life pattern in

Conway's Game of Life may be partitioned into two smaller still lifes if and only if an associated switch graph contains a regular cycle. As he shows, for switch graphs with at most three edges per vertex, this may be tested in polynomial time by repeatedly removing bridges (edges the removal of which disconnects the graph) and vertices at which all edges belong to a single partition until no more such simplifications may be performed. If the result is anempty graph , there is no regular cycle; otherwise, a regular cycle may be found in any remaining bridgeless component.Similar bridge-removal techniques in the context of matching were previously considered by harvtxt|Gabow|Kaplan|Tarjan|1999.

**atisfiability**An instance of the

2-satisfiability problem, that is, a Boolean expression inconjunctive normal form with two variables or negations of variables per clause, may be transformed into animplication graph by replacing each clause $scriptstyle\; ulor\; v$ by the two implications$scriptstyle(lnot\; u)Rightarrow\; v$ and $scriptstyle(lnot\; v)Rightarrow\; u$. This graph has a vertex for each variable or negated variable, and a directed edge for each implication; it is, by construction, skew-symmetric, with a correspondence σ that maps each variable to its negation.As harvtxt|Aspvall|Plass|Tarjan|1979 showed, a satisfying assignment to the 2-satisfiability instance is equivalent to a partition of this implication graph into two subsets of vertices, "S" and σ("S"), such that no edge starts in "S" and ends in σ("S"). If such a partition exists, a satisfying assignment may be formed by assigning a true value to every variable in "S" and a false value to every variable in σ("S"). This may be done if and only if nostrongly connected component of the graph contains both some vertex "v" and its complementary vertex σ("v"). If two vertices belong to the same strongly connected component, the corresponding variables or negated variables are constrained to equal each other in any satisfying assignment of the 2-satisfiability instance. The total time for testing strong connectivity and finding a partition of the implication graph is linear in the size of the given 2-CNF expression.**References***citation

last1 = Aspvall | first1 = Bengt

last2 = Plass | first2 = Michael F.

authorlink3 = Robert Tarjan | last3 = Tarjan | first3 = Robert E.

title = A linear-time algorithm for testing the truth of certain quantified boolean formulas

journal = Information Processing Letters

volume = 8 | issue = 3 | pages = 121–123 | year = 1979.*citation

last = Babenko | first = Maxim A.

contribution = Acyclic bidirected and skew-symmetric graphs: algorithms and structure

title = Computer Science – Theory and Applications

publisher = Springer-Verlag | series = Lecture Notes in Computer Science | year = 2006 | volume = 3967

pages = 23–34 | doi = 10.1007/11753728_6.*citation

authorlink = Matthew Cook

last = Cook | first = Matthew

contribution = Still life theory

date = 2003

title = New Constructions in Cellular Automata

publisher = Santa Fe Institute Studies in the Sciences of Complexity, Oxford University Press

pages = 93–118.*citation

last1 = Edmonds | first1 = Jack | authorlink1 = Jack Edmonds

last2 = Johnson | first2 = Ellis L.

contribution = Matching: a well-solved class of linear programs

title = Combinatorial Structures and their Applications: Proceedings of the Calgary Symposium, June 1969

publisher = Gordon and Breach | location = New York | year = 1970 . Reprinted in "Combinatorial Optimization — Eureka, You Shrink!", Springer-Verlag, Lecture Notes in Computer Science 2570, 2003, pp. 27–30, .*citation

last1 = Gabow | first1 = Harold N.

last2 = Kaplan | first2 = Haim

last3 = Tarjan | first3 = Robert E. | authorlink3 = Robert Tarjan

contribution = Unique maximum matching algorithms

title = Proc. 31st ACM Symp. Theory of Computing (STOC)

year = 1999 | pages = 70–78

doi = 10.1145/301250.301273.*citation

last1 = Goldberg | first1 = Andrew V.

last2 = Karzanov | first2 = Alexander V.

title = Path problems in skew-symmetric graphs

journal = Combinatorica

volume = 16 | issue = 3 | year = 1996 | pages = 353–382

doi = 10.1007/BF01261321.*citation

last1 = Goldberg | first1 = Andrew V.

last2 = Karzanov | first2 = Alexander V.

title = Maximum skew-symmetric flows and matchings

journal = Mathematical programming

volume = 100 | issue = 3 | year = 2004 | pages = 537–568

doi = 10.1007/s10107-004-0505-z.*citation

last1 = Hui | first1 = Peter

last2 = Schaefer | first2 = Marcus

last3 = Štefankovič | first3 = Daniel

contribution = Train tracks and confluent drawings

title = Proc. 12th Int. Symp. Graph Drawing

publisher = Springer-Verlag

series = Lecture Notes in Computer Science

volume = 3383 | year = 2004 | pages = 318–328.*citation

last = Tutte | first = W. T. | authorlink = W. T. Tutte

title = Antisymmetrical digraphs

journal = Canadian Journal of Mathematics

volume = 19 | pages = 1101–1117 | year = 1967.

*Wikimedia Foundation.
2010.*

### Look at other dictionaries:

**Graph automorphism**— In graph theoretical mathematics, an automorphism of a graph is a form of symmetry in which the graph is mapped onto itself while preserving the edge vertex connectivity.Formally, an automorphism of a graph G = ( V , E ) is a permutation sigma;… … Wikipedia**Matching (graph theory)**— In the mathematical discipline of graph theory, a matching or independent edge set in a graph is a set of edges without common vertices. It may also be an entire graph consisting of edges without common vertices. Covering packing dualities… … Wikipedia**Bidirected graph**— In the mathematical domain of graph theory, a bidirected graph (introduced by harvnb|Edmonds|Johnson|1970) is a graph in which each edge is given an independent orientation (or direction, or arrow) at each end. Thus, there are three kinds of… … Wikipedia**Distance-regular graph**— Graph families defined by their automorphisms distance transitive distance regular strongly regular … Wikipedia**Distance-transitive graph**— The Biggs Smith graph, the largest 3 regular distance transitive graph. Graph families defined by their automorphisms distance transitive … Wikipedia**Implication graph**— In mathematical logic, an implication graph is a skew symmetric directed graph G ( V , E ) composed of vertex set V and directed edge set E . Each vertex in V represents the truth status of a Boolean literal, and each directed edge e ( u , v )… … Wikipedia**List of mathematics articles (S)**— NOTOC S S duality S matrix S plane S transform S unit S.O.S. Mathematics SA subgroup Saccheri quadrilateral Sacks spiral Sacred geometry Saddle node bifurcation Saddle point Saddle surface Sadleirian Professor of Pure Mathematics Safe prime Safe… … Wikipedia**2-satisfiability**— In computer science, 2 satisfiability (abbreviated as 2 SAT or just 2SAT) is the problem of determining whether a collection of two valued (Boolean or binary) variables with constraints on pairs of variables can be assigned values satisfying all… … Wikipedia**Still life (cellular automaton)**— In cellular automata, a still life is a pattern that does not change from one generation to the next. A still life can be thought of as an oscillator of period 1. A strict still life is an indecomposable still life pattern, while a pseudo still… … Wikipedia**List of matrices**— This page lists some important classes of matrices used in mathematics, science and engineering: Matrices in mathematics*(0,1) matrix a matrix with all elements either 0 or 1. Also called a binary matrix . *Adjugate matrix * Alternant matrix a… … Wikipedia