Gráfico elaborado a partir de un subconjunto de los nodos de otro gráfico y sus aristas
In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and all of the edges (from the original graph) connecting pairs of vertices in that subset.
Definition
Formally, let be any graph, and let be any subset of vertices of G. Then the induced subgraph is the graph whose vertex set is and whose edge set consists of all of the edges in that have both endpoints in .[1] That is, for any two vertices , and are adjacent in if and only if they are adjacent in . The same definition works for undirected graphs, directed graphs, and even multigraphs.
The induced subgraph may also be called the subgraph induced in by , or (if context makes the choice of unambiguous) the induced subgraph of .
Examples
Important types of induced subgraphs include the following.
Induced paths are induced subgraphs that are paths. The shortest path between any two vertices in an unweighted graph is always an induced path, because any additional edges between pairs of vertices that could cause it to be not induced would also cause it to be not shortest. Conversely, in distance-hereditary graphs, every induced path is a shortest path.[2]
^ Diestel, Reinhard (2006), Teoría de grafos, Textos de posgrado en matemáticas, vol. 173, Springer-Verlag, págs. 3–4, ISBN 9783540261834.
^ Howorka, Edward (1977), "Una caracterización de gráficos hereditarios de distancia", The Quarterly Journal of Mathematics , segunda serie, 28 (112): 417–420, doi :10.1093/qmath/28.4.417, MR 0485544.
^ Johnson, David S. (1985), "La columna de integridad NP: una guía continua", Journal of Algorithms , 6 (3): 434–451, doi :10.1016/0196-6774(85)90012-4, MR 0800733.