Subgraph
The term subgraph in describing graph theory a relationship between two graphs . Another word for subgraph is subgraph . A graph is a subgraph of the graph if all nodes and edges of are also included in . In other words: A subgraph is created from a graph by removing some nodes and edges from . When removing a node, all incident edges must also be removed.
Definitions
A graph is called a subgraph or subgraph or subgraph of if its node set is a subset of and its edge set is a subset of , i.e. and holds.
The reverse is then called supergraph or upper graph of .
These terms are not uniform. In the below text book by Klaus Wagner , only the term in this general subgraph used, and a sub-graph defined as a subgraph, which additionally has the property that each edge of the two nodes from connecting also an edge in is. In Claude Berge's textbook , subgraph also means that is, and subgraph means that and every edge out that connects two nodes in is also an edge in , the general case is then called part-subgraph there . It is therefore advisable to check the definition used with each author.
In the case of a node-weighted or edge-weighted graph , it is also required of a subgraph that the weight function of must be compatible with the weight function of , i. H. for each node is valid and for each edge is considered .
If it is also true for a subgraph that all edges between the nodes in contains that are also present in, then one denotes the subgraph of induced by and also notes this down . An induced subgraph is therefore always uniquely determined by the supergraph and the selected node set. For a node-set is denoted by the induced subgraphs consisting by omitting the node is created and their incident node edges, ie .
A subgraph of that contains all nodes of its supergraph is called a spanning subgraph or factor .
Examples
In the following figure, the graphs , and subgraphs of , but only and are induced subgraphs. arises from by omitting the nodes and their incident edges, so is . At the same time there is also an induced subgraph of .
See also
literature
- Reinhard Diestel: graph theory. 4th edition. Springer-Verlag, Berlin Heidelberg 2010, ISBN 978-3-642-14911-5 . (354 pages, online )
- Lutz Volkmann: Fundamente der Graphentheorie , Springer (Vienna) 1996, ISBN 3-211-82774-9 ( newer online version "Graphs on all corners and edges" ; PDF; 3.51 MB)