Skew-symmetric Graph

In graph theory, a branch of mathematics, a skew-symmetric graph is a directed graph that is isomorphic to its own transpose graph, the graph formed by reversing all of its edges, under an isomorphism that is an involution without any fixed points. Skew-symmetric graphs are identical to the double covering graphs of bidirected graphs.

Skew-symmetric graphs were first introduced under the name of antisymmetrical digraphs by Tutte (1967), later as the double covering graphs of polar graphs in Zelinka (1976b), and still later as the double covering graphs of bidirected graphs in Zaslavsky (1991). They arise in modeling the search for alternating paths and alternating cycles in algorithms for finding matchings in graphs, in testing whether a still life pattern in Conway's Game of Life may be partitioned into simpler components, in graph drawing, and in the implication graphs used to efficiently solve the 2-satisfiability problem.

Read more about Skew-symmetric Graph:  Definition, Examples, Polar/switch Graphs, Double Covering Graphs, and Bidirected Graphs, Matching, Still Life Theory, Satisfiability

Famous quotes containing the word graph:

    When producers want to know what the public wants, they graph it as curves. When they want to tell the public what to get, they say it in curves.
    Marshall McLuhan (1911–1980)