Subgraph
A Subgraph is a subset of the graph nodes and graph edges of a graph.
- AKA: Graph Cluster.
- Context:
- It can range from being a Connected Subgraph to being an Unconnected Subgraph.
- It can range from being a Subgraph Dataset to being a Formal Subgraph.
- It can range from being a Dense Subgraph to being a Sparse Subgraph.
- It can be found by a Subgraph Finding System (that solves a subgraph finding task).
- It can be a Common Subgraph.
- Example(s):
- a Clique.
- a Subtree.
- a Graph Edge Sequence.
- …
- Counter-Example(s):
- a Graph Set.
- See: Substructure, Proper Subgraph.
References
2013
- http://en.wikipedia.org/wiki/Glossary_of_graph_theory#Subgraphs
- A subgraph of a graph G is a graph whose vertex set is a subset of that of G, and whose adjacency relation is a subset of that of G restricted to this subset. In the other direction, a supergraph of a graph G is a graph of which G is a subgraph. We say a graph G contains another graph H if some subgraph of G is H or is isomorphic to H.
A subgraph H is a spanning subgraph, or factor, of a graph G if it has the same vertex set as G. We say H spans G.
A subgraph H of a graph G is said to be induced (or full) if, for any pair of vertices x and y of H, xy is an edge of H if and only if xy is an edge of G. In other words, H is an induced subgraph of G if it has exactly the edges that appear in G over the same vertex set. If the vertex set of H is the subset S of V(G), then H can be written as G[S] and is said to be induced by S.
A graph that does not contain H as an induced subgraph is said to be H-free.[citation needed]
A universal graph in a class K of graphs is a simple graph in which every element in K can be embedded as a subgraph.
A graph G is minimal with some property P provided that G has property P and no proper subgraph of G has property P. In this definition, the term subgraph is usually understood to mean "induced subgraph." The notion of maximality is defined dually: G is maximal with P provided that P(G) and G has no proper supergraph H such that P(H).
- A subgraph of a graph G is a graph whose vertex set is a subset of that of G, and whose adjacency relation is a subset of that of G restricted to this subset. In the other direction, a supergraph of a graph G is a graph of which G is a subgraph. We say a graph G contains another graph H if some subgraph of G is H or is isomorphic to H.
2009
- http://en.wiktionary.org/wiki/subgraph
- A section of a graph or network
- http://www2.parc.com/istl/groups/hdi/sensemaking/glossary.htm
- A connected subset of a graph. Typically, a subgraph is a connected subset of nodes and links from a larger graph. ...