Glossary of graph theory#Subgraphs

In the investigation of graph properties you close more often from local to global properties of graphs and vice versa. In order to describe such processes better, we define appropriate relations between graphs and local areas within these graphs. Are particularly important subgraphs relationships. The terms subgraph and subgraph are special cases of the more general terms corresponding partial structure and substructure in the model theory. A substructure is preserved vividly seen an excerpt from a structure in which all the relationships between the elements ( or nodes ). Example is given below: G2, G3 are subgraphs of G, but G1 is not a subgraph, but only a subgraph of G. Part structures so they can additionally be eliminated yet relationships between the elements. Each sub- structure is a part of structure, but not vice versa. In the following two terms for graphs are defined in more detail.

Clearly, it means the following: To create a subgraph T of a graph G to choose any node of G and adds them to T. A subgraph is obtained by adding some edges of T 's nodes also to T. A subgraph is obtained by adding all edges between T's nodes to T.

Subgraph

A graph is called partial graph or subgraph of if subset of, and therefore

• In graphs without multiple edges subset of,
• In undirected graphs with multiple edges for all two-element subsets of, ie, Applies, wherein the amount of the edges between the nodes,
• In directed graphs with multiple edges is valid for all subsets of the Cartesian product.

Conversely, this means Supergraph or supergraph of.

In a node -weighted and edge-weighted graph is a subgraph also requires that the weight function of compatible to the weight function, ie for each node and for each edge of.

Subgraph or induced subgraph

Applies also:

• In graphs without multiple edges, , That is, G1 contains all the edges between the nodes in V1, which are also present in G2.
• In undirected graphs with multiple edges, for all two-element subsets v of V2,
• In directed graphs with multiple edges, for all v in the Cartesian product V2xV2,

This is referred to as G1 induced by V1 subgraph of G2 and a note of this with or just (G = G2, A = V1).

Remarks:

• Induced subgraphs are always determined uniquely by the corresponding set of nodes.
• Particularly important subgraphs resulting from the omission of nodes and edges. Consider the graph G ( V, E), then called the graph formed by omitting the nodes of A and their incident nodes edges. The resulting subgraphs are always induced subgraphs.

Examples of subgraphs and induced subgraphs

In the figure above, a simple graph on the left is given. is neither subgraph still subgraph, since an edge is incident with only one node. Strictly speaking, there is not even a graph as edges can not exist independently of nodes. is a subgraph of, and is there. But it does not is a subgraph of, since, for example the edge is not included in the set of edges. is a subgraph of and also the induced subgraph of the node set, since all edges which are incident with two of these nodes are also included in the graph.

The following figure shows the graphs, subgraphs of, but which are just and induced subgraphs. arises from this by omitting the node and its incident edges.