Subgraph

Материал из WEGA
Перейти к навигации Перейти к поиску

Subgraph --- подграф, часть графа, частичный граф.

1.(Subgraph in a weak sense) For a graph [math]\displaystyle{ G = (V,E) }[/math] this is a graph [math]\displaystyle{ H = (V_{H},E_{H}) }[/math] with [math]\displaystyle{ V_{H} \subseteq V }[/math] and [math]\displaystyle{ E_{H} \subseteq E }[/math]. Another name is Part of a graph.

2. (Subgraph in a strong sense) If [math]\displaystyle{ W \subseteq V }[/math] then [math]\displaystyle{ G[W] }[/math] denotes the subgraph induced by [math]\displaystyle{ W }[/math], i.e. [math]\displaystyle{ G[W] }[/math] is the subgraph with the vertex set [math]\displaystyle{ W }[/math] in which two vertices are adjacent whenever they are adjacent in [math]\displaystyle{ G }[/math]. Another name is Induced [with vertices] subgraph.