诱导子图 | Baeldung中文网

1. Introduction

In this tutorial, we’ll explain what an induced subgraph is. We’ll also show how to construct it, how to check if a (sub)graph is induced, and how to find the induced graph isomorphism.

2. Subgraphs

Let’s say we have a graph G=(V, E) , where is the set of nodes, and denotes the edges between them. A subgraph of is any graph G'=(V', E') such that $V' \subseteq V$ and $E' \subseteq E$ . In other words, each node in a subgraph is also a node in the supergraph. Further, every edge in the subgraph is an edge in the supergraph.

For example, all these graphs:

Examples of subgraphs

can be listed as subgraphs of:

graph

3. Induced Subgraphs

An induced subgraph is a special case of a subgraph. If is a subset of ‘s nodes, then the subgraph of induced by is the graph that has as its set of vertices and contains all the edges of $\boldsymbol{G}$ that have both endpoints in $\boldsymbol{S}$ . This definition covers both directed and undirected graphs. Also, it covers the weighted just as the unweighted ones.

Given and , the induced subgraph is unique. There’s only one subgraph induced by $\{D, E, G, J, K\}$ in the above graph:

Example of an induced subgraph

3.1. What’s the Difference?

The concepts of an induced subgraph and an ordinary subgraph are very similar. The difference is that an induced subgraph includes all the edges that have both endpoints in the inducing set $\boldsymbol{S}$ , whereas an ordinary subgraph may miss some.

So, an induced subgraph keeps both adjacency and non-adjacency of the inducing vertices, in contrast to an ordinary subgraph that preserves only non-adjacency.

4. Induced Subgraph Problems and Algorithms

Let’s introduce a few problems related to induced subgraphs.

4.1. Induced Subgraph Construction

Here, the input consists of the graph $\boldsymbol{G=(V, E)}$ and the inducing set $\boldsymbol{S \subseteq V}$ . Our goal is to construct the induced subgraph $\boldsymbol{G_S = (S, E_S)}$ . We’ll do so by iterating over the edges in and keeping only those whose both endpoints are in :

algorithm ConstructInducedSubgraph(G, S):
    // INPUT
    //    G = (V, E) = the input graph with nodes V and edges E
    //    S = the inducing set of nodes, a subset of V
    // OUTPUT
    //    G_S = (S, E_S) = the subgraph of G induced by S

    E_S <- an empty set
    
    for u in S:
        for v in ADJACENT-NODES(u):
            E_S <- E_S ∪ {(u, v)}

    G_S <- (S, E_S)

    return G_S

The time complexity depends on how we represent the graphs. Using linked lists, we traverse each edge incident to a node in twice, so the time complexity is $\Theta(|E_S|)$ . On the other hand, if we use matrices, we traverse the whole row of |V| entries for each of the |S| inducing nodes. Therefore, the complexity will be $\Theta(|S|\cdot |V|)$ .

4.2. How to Check if a Subgraph Is Induced

In this problem, we have a graph $\boldsymbol{G_1=(V_1, E_1)}$ and its subgraph $\boldsymbol{G_2=(V_2, E_2)}$ (so $V_2 \subseteq V_1$ and $E_2 \subseteq E_1$ ). Our goal is to check if $\boldsymbol{G_2}$ is an induced subgraph of $\boldsymbol{G_1}$ . To do so, we iterate over the edges incident to V_2 in G_1 . If we find an edge that isn’t in E_2 , we can conclude that G_2 isn’t an induced subgraph because it doesn’t preserve adjacency. Otherwise, we conclude that G_2 is induced:

algorithm CheckingIfSubgraphIsInduced(G1, G2):
    // INPUT
    //    G1 = the input graph with nodes V1 and edges E1
    //    G2 = a subgraph of G1, with nodes V2 and edges E2 (V2 ⊆ V1 and E2 ⊆ E1)
    // OUTPUT
    //    Returns true if G2 is an induced subgraph, false otherwise

    for u in V2:
        // check all the nodes adjacent to u in G1
        for v in ADJACENT-NODES(u):
            if (u, v) not in E2:
                return false

    return true

As before, the complexity depends on the way we represent the graphs.

We don’t need to check if G_2 contains an edge not in G_1 . That’s because of the way we defined the input. Since we know that G_2 is a subgraph of G_1 , E_2 can’t contain an edge that’s not in E_1 .

4.3. How to Check if a Graph Is an Induced Subgraph

However, if we get G_2 as a graph of some nodes in V_1 , we’ll have to check both that G_2 is a subgraph and that it is induced:

algorithm CheckInducedSubgraph(G1, G2):
    // INPUT
    //    G1 = (V1, E1) - the input graph with nodes V1 and edges E1
    //    G2 = (V2, E2) - a graph of nodes in V1 
    //      (so V2 ⊆ V1, but not necessarily E2 ⊆ E1)
    // OUTPUT
    //    true, if G2 is an induced subgraph of G1
    //    false, otherwise

    // First, check if G2 is a subgraph of G1
    for (u, v) in E2:
        if (u, v) is not in E1:
            return false

    // If yes, check if it is induced by V2
    for u in V2:
        // check all the nodes adjacent to u in G1
        for v in ADJACENT-NODES(u):
            if (u, v) is not in E2:
                return false

    return true

4.4. Induced Subgraph Isomorphism

The Induced Subgraph Isomorphism (ISI) is an injective mapping from one graph $\boldsymbol{G_2 = (V_2, E_2)}$ to an induced subgraph of another, $\boldsymbol{G_1=(V_1, E_1)}$ . So, we get G_1 and G_2 at the input and find an ISI mapping from the former to the latter.

Unlike in the previous two problems, G_2 and G_1 don’t use the same labels for their nodes. So, we have to find a mapping that translates $\boldsymbol{G_2}$ to an induced subgraph of $\boldsymbol{G_1}$ :

isi

Formally, we say that $f: V_2 \mapsto V_1$ is an ISI if and only if it satisfies:

(1) $\begin{equation*} \begin{aligned} (\forall v',v'' \in V_2) \begin{cases} v' \neq v'' \implies f(v') \neq f(v'') \\ (v', v'') \in E_2 \implies (f(v'), f(v'')) \in E_1 \\ (v', v'') \not \in E_2 \implies (f(v'), f(v'')) \not \in E_1 \end{cases} \end{aligned} \end{equation*}$

The first condition states that is an injective function. The second is that an ISI preserves adjacency, and the third is that it also keeps non-adjacency.

This problem is NP-hard, which means that no polynomial-time algorithm for solving it is known to date. We can treat it as a constraint-satisfaction problem (CSP) and solve it like we solve other CSPs. The Equation (1) lists all the constraints we need to define the CSP and feed it to the universal solver. Each f(v) for $v \in V_2$ will correspond to a CSP variable, and each variable will have the whole set V_1 as its domain.

5. Conclusion

In this article, we talked about induced and ordinary subgraphs. We also presented a few common problems related to the former subgraphs. Those are the induced subgraph construction, verification, and isomorphism.

Persistence

REST

Security