Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Signed_graph> ?p ?o. }
Showing items 1 to 25 of
25
with 100 items per page.
- Signed_graph abstract "In the area of graph theory in mathematics, a signed graph is a graph in which each edge has a positive or negative sign.Formally, a signed graph Σ is a pair (G, σ) that consists of a graph G = (V, E) and a sign mapping or signature σ from E to the sign group {+,−}. The graph may have loops and multiple edges as well as half-edges (with only one endpoint) and loose edges (with no endpoints). Half and loose edges do not receive signs. (In the terminology of the article on graphs, it is a multigraph, but we say graph because in signed graph theory it is usually unnatural to restrict to simple graphs.)The sign of a circle (this is the edge set of a simple cycle) is defined to be the product of the signs of its edges; in other words, a circle is positive if it contains an even number of negative edges and negative if it contains an odd number of negative edges. The fundamental fact about a signed graph is the set of positive circles, denoted by B(Σ). A signed graph, or a subgraph or edge set, is called balanced if every circle in it is positive (and it contains no half-edges). Two fundamental questions about a signed graph are: Is it balanced? What is the largest size of a balanced edge set in it? The first question is not difficult; the second is computationally intractable (technically, it is NP-hard).Signed graphs were first introduced by Harary to handle a problem in social psychology (Cartwright and Harary, 1956). They have been rediscovered many times because they come up naturally in many unrelated areas. For instance, they enable one to describe and analyze the geometry of subsets of the classical root systems. They appear in topological graph theory and group theory. They are a natural context for questions about odd and even cycles in graphs. They appear in computing the ground state energy in the non-ferromagnetic Ising model; for this one needs to find a largest balanced edge set in Σ. They have been applied to data classification in correlation clustering.".
- Signed_graph wikiPageExternalLink 1028989917.
- Signed_graph wikiPageExternalLink ds8.pdf.
- Signed_graph wikiPageID "2472618".
- Signed_graph wikiPageRevisionID "606313061".
- Signed_graph hasPhotoCollection Signed_graph.
- Signed_graph subject Category:Extensions_and_generalizations_of_graphs.
- Signed_graph subject Category:Matroid_theory.
- Signed_graph subject Category:Oriented_matroids.
- Signed_graph type Abstraction100002137.
- Signed_graph type Delay115272029.
- Signed_graph type Extension115272382.
- Signed_graph type ExtensionsAndGeneralizationsOfGraphs.
- Signed_graph type Measure100033615.
- Signed_graph type Pause115271008.
- Signed_graph type TimeInterval115269513.
- Signed_graph comment "In the area of graph theory in mathematics, a signed graph is a graph in which each edge has a positive or negative sign.Formally, a signed graph Σ is a pair (G, σ) that consists of a graph G = (V, E) and a sign mapping or signature σ from E to the sign group {+,−}. The graph may have loops and multiple edges as well as half-edges (with only one endpoint) and loose edges (with no endpoints). Half and loose edges do not receive signs.".
- Signed_graph label "Signed graph".
- Signed_graph sameAs 부호형_그래프.
- Signed_graph sameAs m.07gf82.
- Signed_graph sameAs Q11246292.
- Signed_graph sameAs Q11246292.
- Signed_graph sameAs Signed_graph.
- Signed_graph wasDerivedFrom Signed_graph?oldid=606313061.
- Signed_graph isPrimaryTopicOf Signed_graph.