“图”的版本间的差异

来自姬鸿昌的知识库
跳到导航 跳到搜索
 
（未显示同一用户的21个中间版本）
第68行： 第68行：
  
 
连通图与完全图不同的是：完全图中，任意两个顶点一定有至少一条边直接相连；而连通图中两个顶点之间的路径可以是间接相连的。
 
连通图与完全图不同的是：完全图中，任意两个顶点一定有至少一条边直接相连；而连通图中两个顶点之间的路径可以是间接相连的。
 +
 +
在有向图中，如果可以直接满足任意两个顶点之间都有一个路径相连的条件的叫做强连通图；如果不计较方向可以直接满足任意两个顶点之间都有一个路径相连的条件的叫做弱连通图。
 +
 +
 +
=== 2）图的转换：无向图转邻接矩阵 ===
 +
用一个n阶方阵R来存放图中各结点的关联信息，其矩阵元素R<sub>ij</sub>定义为：
 +
[[文件:无向图转邻接矩阵元素定义.png|无|缩略图]]
 +
[[文件:无向图转邻接矩阵示意图.png|无|缩略图|600x600像素]]
 +
比如
 +
 +
矩阵R<sub>1</sub>中R<sub>12</sub>=1就表示顶点1到顶点2的边；
 +
 +
矩阵R<sub>1</sub>中R<sub>21</sub>=1就表示顶点2到顶点1的边（和R<sub>12</sub>描述的是同一条边）；
 +
 +
矩阵R<sub>1</sub>中R<sub>25</sub>=0就表示顶点2到顶点5的没有路径，没有边；
 +
 +
 +
无向图转换的邻接矩阵为对称矩阵。
 +
 +
满足R<sub>ij</sub>=R<sub>ji</sub>的矩阵叫做对称矩阵。
 +
 +
 +
出度：看行，一个顶点连到其他顶点
 +
 +
入度：看列，其他顶点连到当前顶点
 +
 +
 +
 +
 +
https://www.bilibili.com/video/BV1hg411V7Bm?p=63
 +
 +
=== 2）图的转换：有向图转邻接矩阵 ===
 +
与有向图的转换方式相同。
 +
[[文件:有向图转邻接矩阵.png|无|缩略图|600x600像素]]有向图中，一个顶点指向另一个顶点的边又叫做弧；
 +
 +
R<sub>ij</sub>=0或∞表示顶点i到顶点j没有弧的存在；
 +
 +
R<sub>ij</sub>=1表示顶点i到顶点j有弧的存在；
 +
 +
 +
有向图中度分入度和出度：其他顶点指向自己的弧的和自己指向其他顶点的弧；
 +
 +
比如顶点V<sub>1</sub>，看第1行，有6、1、50，我们就说顶点V<sub>1</sub>的出度为3；看第1列，没有有效值，我们就说顶点V<sub>1</sub>的入度为0。
 +
 +
再比如顶点V<sub>5</sub>，看第5行，有38、24，我们就说顶点V<sub>5</sub>的出度为2；看第5列，有6、12、1，我们就说顶点V<sub>5</sub>的入度为3。
 +
 +
从行看出度，从列看入度。
 +
 +
 +
=== 2）图的转换：有向图转邻接链表 ===
 +
首先把每个顶点的邻接顶点用链表表示出来，然后用一个一维数组来顺序存储上面没个链表的头指针。
 +
[[文件:有向图转邻接链表.png|无|缩略图|900x900像素]]
 +
比如
 +
 +
V<sub>1</sub>就是有到V<sub>2</sub>的弧值为6，到V<sub>4</sub>的弧值为1，到V<sub>6</sub>的弧值为50；
 +
 +
……
 +
 +
V<sub>7</sub>就是有到V<sub>8</sub>的弧值为20；
 +
 +
 +
 +
=== 考点1：无向图的转换 ===
 +
对于连通无向图G，一下叙述中，错误的是（）。
 +
 +
A、G中任意两个顶点之间存在路径
 +
 +
B、G中任意两个顶点之间都有边
 +
 +
C、从G中任意顶点出发可遍历图中所有顶点
 +
 +
D、G的邻接矩阵是对称的
 +
 +
题解：选项B。完全图才是任意两个顶点之间都有边。
 +
 +
 +
=== 考点2：有向图转邻接矩阵 ===
 +
某图G的邻接矩阵如下图所示。
 +
[[文件:考点2 有向图转邻接矩阵.png|无|缩略图|300x300像素]]
 +
以下关于该图的叙述中，错误的是（）。
 +
 +
A、该图存在回路（环）
 +
 +
B、该图为完全有向图  √
 +
 +
C、图中所有顶点的入度都大于0
 +
 +
D、图中所有顶点的出度都大于0
 +
 +
解：
 +
 +
判断选项D：逐行统计顶点的出度分别为：2、1、2、2、1、2，所以D对
 +
 +
判断选项C：逐列统计顶点的入度分别为：2、1、2、2、1、2，所以C对
 +
 +
判断选项B：完全有向图的定义是每对顶点（每两个顶点）之间都有两条有向边相连接，很明显B是错的。
 +
 +
判断选项A：需要画图
 +
[[文件:考点2选项A有向图转邻接矩阵.png|无|缩略图|600x600像素]]
 +
顶点1、2、3之间构成了回路
 +
 +
 +
=== 考点3：有向图转邻接链表 ===
 +
已知某带权图G的邻接表如下所示，
 +
[[文件:考点3 有向图转邻接链表.png|无|缩略图|600x600像素]]
 +
其中表结点的结构为：以下关于该图的叙述中，正确的是（）。
 +
 +
A、图G是强连通图
 +
 +
B、图G具有14条弧
 +
 +
C、顶点B的出度为3
 +
 +
D、顶点B的入度为3  √
 +
 +
解：
 +
 +
A：“强连通图”要求任意两个顶点之间都有一条路径相连，顶点1A到2B有、到4D有，顶点3C到1A有，但1A和4D之间互相就没有，和5E之间互相也没有，所以A是错的
 +
 +
B：计数：1A到2B、1A到4D、2B到5E、3C到1A、3C到2B、4D到2B、5E到4D，一共7条弧，所以B是错的；
 +
 +
C：B的出度只有2B到5E一条，C错
 +
 +
D：统计B的入度有：1A到2B、3C到2B、4D到2B共计3条，D对
 +
 +
 +
=== 总结 ===
 +
图的分类
 +
 +
* 有向图和无向图
 +
* 连通图和完全图
 +
 +
图的转换
 +
 +
* 无向图转邻接矩阵
 +
** 为对称矩阵
 +
** 行列数为定点数
 +
* 有向图转邻接矩阵（了解出度、入度和边的判断）
 +
* 有向图转邻接链表（了解出度、入度和边的判断）

2022年10月4日 (二) 07:40的最新版本

https://www.bilibili.com/video/BV1hg411V7Bm?p=62

1）图的分类

完全图

在无向图中，若每对顶点之间都有一条边相连，则称该图为完全图。

无向图完全图


在有向图中，若每对顶点之间都有两条有向边相连接，则称该图为完全图。

有向图完全图


问题：n个顶点的无向图和有向图的完全图的边的个数为多少？

无向图

n个顶点：

顶点编号 边统计 参与的边
1 顶点1和顶点2

顶点1和顶点3

顶点1和顶点4

……

顶点1和顶点n

n-1
2 顶点2和顶点3

顶点2和顶点4

……

顶点2和顶点3

顶点2和顶点n

n-2
n-1 顶点n-1和顶点n 1
n 0

n-1，n-2，……，1，0

等差数列求和：(n-1+0)×n÷2=(n-1)×n÷2


有向图：

参考无线图，因为有向图两个顶点之间的线是两条，所以就是(n-1)×n


连通图

连通图：指任意两个顶点之间都有一个路径相连。

连通图与完全图不同的是：完全图中，任意两个顶点一定有至少一条边直接相连；而连通图中两个顶点之间的路径可以是间接相连的。

在有向图中，如果可以直接满足任意两个顶点之间都有一个路径相连的条件的叫做强连通图；如果不计较方向可以直接满足任意两个顶点之间都有一个路径相连的条件的叫做弱连通图。


2）图的转换：无向图转邻接矩阵

用一个n阶方阵R来存放图中各结点的关联信息，其矩阵元素Rij定义为：

无向图转邻接矩阵元素定义.png
无向图转邻接矩阵示意图.png

比如

矩阵R1中R12=1就表示顶点1到顶点2的边；

矩阵R1中R21=1就表示顶点2到顶点1的边（和R12描述的是同一条边）；

矩阵R1中R25=0就表示顶点2到顶点5的没有路径，没有边；


无向图转换的邻接矩阵为对称矩阵。

满足Rij=Rji的矩阵叫做对称矩阵。


出度：看行，一个顶点连到其他顶点

入度：看列，其他顶点连到当前顶点



https://www.bilibili.com/video/BV1hg411V7Bm?p=63

2）图的转换：有向图转邻接矩阵

与有向图的转换方式相同。

有向图转邻接矩阵.png

有向图中，一个顶点指向另一个顶点的边又叫做弧；

Rij=0或∞表示顶点i到顶点j没有弧的存在；

Rij=1表示顶点i到顶点j有弧的存在；


有向图中度分入度和出度：其他顶点指向自己的弧的和自己指向其他顶点的弧；

比如顶点V1，看第1行，有6、1、50，我们就说顶点V1的出度为3；看第1列，没有有效值，我们就说顶点V1的入度为0。

再比如顶点V5，看第5行，有38、24，我们就说顶点V5的出度为2；看第5列，有6、12、1，我们就说顶点V5的入度为3。

从行看出度，从列看入度。


2）图的转换：有向图转邻接链表

首先把每个顶点的邻接顶点用链表表示出来，然后用一个一维数组来顺序存储上面没个链表的头指针。

有向图转邻接链表.png

比如

V1就是有到V2的弧值为6，到V4的弧值为1，到V6的弧值为50；

……

V7就是有到V8的弧值为20；


考点1：无向图的转换

对于连通无向图G，一下叙述中，错误的是（）。

A、G中任意两个顶点之间存在路径

B、G中任意两个顶点之间都有边

C、从G中任意顶点出发可遍历图中所有顶点

D、G的邻接矩阵是对称的

题解：选项B。完全图才是任意两个顶点之间都有边。


考点2：有向图转邻接矩阵

某图G的邻接矩阵如下图所示。

考点2 有向图转邻接矩阵.png

以下关于该图的叙述中，错误的是（）。

A、该图存在回路（环）

B、该图为完全有向图 √

C、图中所有顶点的入度都大于0

D、图中所有顶点的出度都大于0

解：

判断选项D：逐行统计顶点的出度分别为：2、1、2、2、1、2，所以D对

判断选项C：逐列统计顶点的入度分别为：2、1、2、2、1、2，所以C对

判断选项B：完全有向图的定义是每对顶点（每两个顶点）之间都有两条有向边相连接，很明显B是错的。

判断选项A：需要画图

考点2选项A有向图转邻接矩阵.png

顶点1、2、3之间构成了回路


考点3：有向图转邻接链表

已知某带权图G的邻接表如下所示，

考点3 有向图转邻接链表.png

其中表结点的结构为：以下关于该图的叙述中，正确的是（）。

A、图G是强连通图

B、图G具有14条弧

C、顶点B的出度为3

D、顶点B的入度为3 √

解：

A：“强连通图”要求任意两个顶点之间都有一条路径相连，顶点1A到2B有、到4D有，顶点3C到1A有，但1A和4D之间互相就没有，和5E之间互相也没有，所以A是错的

B：计数：1A到2B、1A到4D、2B到5E、3C到1A、3C到2B、4D到2B、5E到4D，一共7条弧，所以B是错的；

C：B的出度只有2B到5E一条，C错

D：统计B的入度有：1A到2B、3C到2B、4D到2B共计3条，D对


总结

图的分类

  • 有向图和无向图
  • 连通图和完全图

图的转换

  • 无向图转邻接矩阵
    • 为对称矩阵
    • 行列数为定点数
  • 有向图转邻接矩阵（了解出度、入度和边的判断）
  • 有向图转邻接链表（了解出度、入度和边的判断）
取自“https://www.jihongchang.top/index.php?title=图&oldid=2688”