结构相关的概念

bipartite 二部

将图的顶点分成两个非空集合\(V_1\)和\(V_2\)，如果这个图的每一条边的两个端点都分别属于\(V_1\)和\(V_2\)，那么称这个图是二部图（bipartite）。

在这个概念的基础上，还有完全二部图（complete bipartite graph）的概念，指的是在bipartite的基础上，\(V_1\)中的每个点，都与\(V_2\)中的每个点相连。

graphlets 图元

图元，指的是一系列异构的（isomorphism）导出（induced）子图。

下面列举所有的3节点、4节点、5节点的图元：

3节点、4节点、5节点的所有图元

induced 导出

给定一个图\(G\)，以及这个图的子图（subgraph）\(G'=(V', E')\)，其中\(V'\subseteq V\)并且\(E' \subseteq E\)。如果\(E' = \{(v_i,v_j)|(v_i,v_j) \in E \text{ and }v_i, v_j \in V'\}\)，也就是对于所有属于\(V'\)的节点，他们在原图\(G\)的中出现的所有边，也都出现在\(G'\)的\(E'\)中，那么，这个子图\(G'\)称为\(G\)的导出（induced）子图。

下面是导出子图的一个示例：

导出子图

isomorphism 同构

如果两个图\(G = (V,E)\) 和 \(G' = (V', E')\) 之间存在一个双射（bijection）函数 \(f: V \rightarrow V'\)，使得$ (v_i, v_j) E (f(v_i),f(v_j)) E' v_i,v_j V$，那么这两个图互为同构图（isomorphism）

subgraph 子图

给定一个图\(G\)，那么定义这个图的子图\(G'=(V', E')\)，其中\(V'\subseteq V\)并且\(E' \subseteq E\)。