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

2023-08-07 13:35| 来源: 网络整理| 查看: 265

正文之前

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

完全图二分图完全二分图 n立方体正文 1. 完全图定义：

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

以Kn表示有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存在子集V1和V2，两个子集互不相交（各子集中的结点不相邻），与E中的每条边相关联的两个顶点分别在V1和V2中，则称G为二分图。

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

2. 判断条件：

无向图

至少有两个结点（一一配对） 3. 完全二分图 1. 定义：完全二分图建立在完全图和二分图的基础之上，如果一个图G是一个二分图，且V1中的所有结点都与V2中的所有结点相连，则G为完全二分图。也就是说，对于集合V1和V2中的任意顶点v1和v2，两点之间的连线都会是G的一条边。 2. 表示用Km,n表示完全二部图，m代表集合V1的结点数量，n代表集合V2的结点数量。 4. n立方体简介：

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

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

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

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

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

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

【本文地址】

公司简介

联系我们