subgrafen

In graph theory, a subgraph of a graph G=(V,E) is a graph H=(V_H,E_H) where V_H ⊆ V and E_H ⊆ E, and each edge in E_H has both endpoints in V_H. In Dutch, the term is subgraf and the plural subgrafen; the English term is subgraph.

Common types include induced subgraphs (E_H consists of all edges of E with both endpoints in V_H), spanning subgraphs (V_H = V but E_H ⊆ E), and edge-induced subgraphs (choose a subset of edges and take their endpoints as the vertex set).

Example: Let G have vertices {a,b,c,d} and edges {ab, bc, cd, da}. A subgraph H with V_H={a,b,c} and E_H={ab, bc} is an induced subgraph on {a,b,c}.

Subgraph relations enable local analysis of a graph. Subgraph isomorphism asks whether a smaller graph H can be mapped into G preserving adjacency; this problem is NP-complete in general. Special cases include when H is a tree or when a fixed-size pattern is considered, which can admit more efficient algorithms.

Applications of subgraphs span several disciplines. They appear in network analysis to study local connectivity, in chemistry to represent molecular fragments, in pattern matching and graph mining, in circuit design, and in the study of social network motifs. Subgraphs provide a fundamental way to examine the structure of larger graphs through smaller, well-defined components.