Skew-symmetric graph (original) (raw)
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.
| Property | Value |
|---|---|
| dbo:abstract | 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 , later as the double covering graphs of polar graphs by , and still later as the double covering graphs of bidirected graphs by . 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. (en) No campo da matemática da teoria dos grafos, um grafo antissimétrico é um grafo orientado que é isomórfico ao seu próprio , o grafo formado pela inversão de todas as suas arestas. O isomorfismo necessita ser uma involução sem nenhum ponto fixo. Grafos antissimétricos foram primeiramente introduzidos sob o nome de "dígrafos antissimétricos" por W.T. Tutte em 1967. Eles surgiram quando da modelagem da busca de caminhos alternados e ciclos alternados em algoritmos para encontrar acoplamentos em grafos, em testes se um padrão still life no jogo da vida, desenvolvido pelo matemático britânico John Horton Conway, pode ser dividido em componentes mais simples, em , e em usados para resolver eficientemente o problema da . (pt) Кососимметрический граф — ориентированный граф, изоморфный своему собственному транспонированному графу. Этот граф образуется путём обращения всех дуг с изоморфизмом и является инволюцией без неподвижных точек. Кососимметрические графы идентичны двойным покрытиям . Кососимметрические графы введены сначала под именем антисимметричные орграфы Таттом, позднее под именем двойные накрывающие графы полярных графов их использовал Зелинка, а позже под именем графов двойных накрытий двунаправленных графов использовал Заславский. Они возникают, например, в моделировании поиска чередующихся путей и циклов, в алгоритмах для поиска паросочетания в графах для тестирования, в задаче разложения конфигурации в игре «Жизнь» на меньшие компоненты, в задаче визуализации графов и в задаче построения , используемых для эффективного решения задачи . (ru) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Implication_graph.svg?width=300 |
| dbo:wikiPageID | 17283742 (xsd:integer) |
| dbo:wikiPageLength | 17484 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1095805232 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Bipartite_double_cover dbc:Graph_families dbr:Path_graph dbc:Matching_(graph_theory) dbr:Matching_(graph_theory) dbr:Max-flow_min-cut_theorem dbr:Orientation_(graph_theory) dbr:NP-complete dbr:Conjunctive_normal_form dbr:Conway's_Game_of_Life dbr:Still_life_(cellular_automaton) dbr:Train_track_(mathematics) dbc:Directed_graphs dbr:Transpose_graph dbr:Cycle_graph dbr:Fixed_point_(mathematics) dbr:Bridge_(graph_theory) dbr:Directed_graph dbr:Graph_drawing dbr:Graph_isomorphism dbr:Graph_theory dbr:Strongly_connected_component dbr:2-satisfiability dbr:Involution_(mathematics) dbr:Bidirected_graph dbr:Bipartite_graph dbr:Empty_graph dbr:Implication_graph dbr:File:Implication_graph.svg |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Doi dbt:Harvtxt dbt:Reflist dbt:Sfnp dbt:Short_description dbt:Sic dbt:Graph_families_defined_by_their_automorphisms |
| dct:subject | dbc:Graph_families dbc:Matching_(graph_theory) dbc:Directed_graphs |
| rdf:type | yago:Abstraction100002137 yago:Family108078020 yago:Group100031264 yago:Organization108008335 yago:WikicatGraphFamilies yago:YagoLegalActor yago:YagoLegalActorGeo yago:YagoPermanentlyLocatedEntity yago:SocialGroup107950920 yago:Unit108189659 |
| rdfs:comment | 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. (en) No campo da matemática da teoria dos grafos, um grafo antissimétrico é um grafo orientado que é isomórfico ao seu próprio , o grafo formado pela inversão de todas as suas arestas. O isomorfismo necessita ser uma involução sem nenhum ponto fixo. (pt) Кососимметрический граф — ориентированный граф, изоморфный своему собственному транспонированному графу. Этот граф образуется путём обращения всех дуг с изоморфизмом и является инволюцией без неподвижных точек. Кососимметрические графы идентичны двойным покрытиям . (ru) |
| rdfs:label | Skew-symmetric graph (en) Grafo antissimétrico (pt) Кососимметрический граф (ru) |
| owl:sameAs | freebase:Skew-symmetric graph yago-res:Skew-symmetric graph wikidata:Skew-symmetric graph dbpedia-hu:Skew-symmetric graph dbpedia-pt:Skew-symmetric graph dbpedia-ru:Skew-symmetric graph https://global.dbpedia.org/id/4ukug |
| prov:wasDerivedFrom | wikipedia-en:Skew-symmetric_graph?oldid=1095805232&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Implication_graph.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Skew-symmetric_graph |
| is dbo:wikiPageDisambiguates of | dbr:Skew |
| is dbo:wikiPageWikiLink of | dbr:Representation_theory dbr:Matching_(graph_theory) dbr:Still_life_(cellular_automaton) dbr:Transpose_graph dbr:Graph_automorphism dbr:2-satisfiability dbr:Bidirected_graph dbr:Antisymmetric dbr:Skew dbr:Implication_graph dbr:Singly_and_doubly_even |
| is foaf:primaryTopic of | wikipedia-en:Skew-symmetric_graph |
