【离散数学】图论（二）几种特殊图

正文之前

上一篇文章中介绍了欧拉回路，这次我们来说一说几种特殊的图

• 完全图
• 二分图
• 完全二分图
• n立方体

正文

1. 完全图

定义：

• 每对结点之间都恰好有一条边（作为判断条件）的简单图

• 以K_n表示有n个结点的完全图

性质：

• 结点数：n

• 边数：n (n - 1) / 2
  (将所有结点标上顺序，第n个结点共有 n - 1 条边，依次类推，
  

  (n - 1) + (n - 2) + ... + 2 + 1 = n (n - 1) / 2)

2. 二分图

1. 定义：

• 图G = (V, E)中，集合V存在子集V₁和V₂，两个子集互不相交（各子集中的结点不相邻），与E中的每条边相关联的两个顶点分别在V₁和V₂中，则称G为二分图。

通俗地说，也就是一个能一分为二的图称为二分图（二部图）。

2. 判断条件：

• 无向图

• 至少有两个结点（一一配对）

3. 完全二分图

1. 定义：

• 完全二分图建立在完全图和二分图的基础之上，如果一个图G是一个二分图，且V₁中的所有结点都与V₂中的所有结点相连，则G为完全二分图。
  也就是说，对于集合V₁和V₂中的任意顶点v₁和v₂，两点之间的连线都会是G的一条边。

2. 表示

• 用K_m,n表示完全二部图，m代表集合V₁的结点数量，n代表集合V₂的结点数量。

4. n立方体

简介：

• n立方体也称超立方体，是用来描述并行计算机的图模型

• 在n立方体中，立方体的棱长为1

• 描述并行计算机时，每个顶点表示1个处理器，共有2ⁿ个处理器，顶点标号用二进制表示

• 既然时并行计算，在同一时刻，每一个处理器可以处理不同的指令，然后与相邻的处理器进行通信

• 每个处理器可以直接与相邻的处理器进行通信，和非相邻处理器之间通信则需要发送额外的消息给接收的处理器，需要花费一段时间

关于几个特殊图的介绍就到此了，这几种图在下文中还会提及，谢谢大家！