Graph-Minor Relation
Jump to navigation
Jump to search
See: Graph, Graph Isomorphic Relation, Preorder Relation.
References
- (Wikipedia, 2009) ⇒ http://en.wikipedia.org/wiki/Graph-minor
- In graph theory, a graph H is called a minor of the graph G if H is isomorphic to a graph that can be obtained by zero or more edge contractions on a subgraph of G. An edge contraction is an operation which removes an edge from a graph while simultaneously merging together the two vertices it used to connect. Equivalently, H is a minor of G if a graph isomorphic to H can be obtained from G by contracting some edges, deleting some edges, and deleting some isolated vertices. The order in which a sequence of such contractions and deletions is performed on G does not affect the resulting graph H.