1. Disconnected Graph (图形不连通 / 断开图)

English: A graph in which there are at least two vertices such that there is no path connecting them.
中文: 一个图中至少有两个顶点之间没有路径相连。

1
2
3

A---B         E---F
    |
    C---D

2. Bipartite Graph (二部图 / 二分图)

bipartite ［bipartit］; adj. 二深裂的［指叶子］；由双方组成的，两党的，由两党组成的.

English: A graph whose vertices can be divided into two disjoint and independent sets such that every edge connects a vertex in one set to a vertex in the other set.
中文: 将顶点分成两类，边只存在不同类的顶点之间，同类顶点之间没有边。

应用：

二部图在许多领域的应用中非常常见，包括：

• 最大匹配问题：寻找图中不存在共用顶点的最大边集。

• 婚姻问题：将 n 位女士与 n 位男士配对，使得每位女士都嫁给一位男士，每位男士都娶一位女士。

• 流量网络：表示商品在网络中从源点到汇点的流动。

1
2
3
4
5
6
7
8
9
10
11

Set 1: A, C, E
Set 2: B, D, F

  A--B
   \/
   /\
  C--D
   \/
   /\
  E--F

3. Planar Graph (平面图)

English: A graph that can be drawn on a plane without any edges crossing each other.
中文: 一种图，可以在平面上绘制而不出现任何边交叉。

1
2
3
4
5
6
7

   A
  / \
 /   \
B-----C
|     |
D-----E

4. Subgraph (子图)

English: A graph formed from a subset of the vertices and edges of another graph.
中文: 从另一个图的顶点和边的子集中形成的图。（可以没有一些边和点）

1
2
3
4
5
6
7
8
9
10

Original Graph:
A---B---C
|       |
D---E---F

Subgraph:
A---B
|  
D---E

5. Spanning Subgraph (生成子图)

中古高地德語 spān ← 古高地德語 spān (“木屑，削片”) ← 原始日耳曼語 *spēnuz (“碎屑，削片”)。 与古英語 spōn (“木片，碎屑”)同源
English: A subgraph that includes all the vertices of the original graph.
中文: 包含原图所有顶点的子图。（可以没有一些边，但不能少点）

1
2
3
4
5
6
7
8
9
10

Original Graph:
A---B
|   |
C---D---E

Spanning Subgraph:
A---B
|  
C---D---E

6. Separation edges and separation vertices