一个图有7个顶点,编号为0~6,其邻接矩阵如下: 回答以下问题: (1)画出该有向图。 (2)求顶点0的入度和出度。 (3)求顶点2的度。
时间: 2024-02-18 11:06:00 浏览: 60
好的,我会根据你的要求回答问题。以下是我的回答:
(1)该有向图的图示如下:
```
0 -> 1
^ |
| v
2 <- 3 -> 4
^ | |
| v v
6 <- 5 -> /
```
(2)顶点0的入度为1,出度为1。
(3)顶点2的度为3,即入度为2,出度为1。
相关问题
[6-1] 无向网的5个顶点依序为a, b, c, d, e,其邻接矩阵如下,画出该图及其最小生成树。
首先画出该图:
```
a b c d e
a 0 6 1 5 -
b 6 0 5 - 3
c 1 5 0 5 6
d 5 - 5 0 2
e - 3 6 2 0
```
最小生成树的求解过程可以使用 Prim 或 Kruskal 算法,这里使用 Prim 算法。
选取一个起始点,比如选取顶点 a。然后依次将与该点直接相连的边加入集合 S,记录下该边所连接的点,将这些点标记为已访问。接着从集合 S 中选择一条最小权值的边,该边所连接的点如果已经访问过,则舍弃该边,否则将该边加入集合 S,记录下该边所连接的点,将这些点标记为已访问。重复以上步骤,直到所有的点都被访问过。
最小生成树的边集为 {a-c, c-b, b-e, e-d},其权值和为 12。以下是该图及其最小生成树的示意图:
```
1
a------c
| \ |
6 | 5 | 5
| \ |
b------e
3
|
2
|
d
```
其中,用粗实线表示最小生成树的边。
请根据下图给出:@ (1)每个顶点的度 (2)邻接矩阵 (3)邻接表 图片1.png
(1) 每个顶点的度如下:
顶点1的度为3,顶点2的度为4,顶点3的度为2,顶点4的度为3,顶点5的度为2。
(2) 邻接矩阵如下:
```
1 2 3 4 5
1 0 1 1 1 0
2 1 0 1 1 1
3 1 1 0 0 0
4 1 1 0 0 1
5 0 1 0 1 0
```
(3) 邻接表如下:
```
1: 2 3 4
2: 1 3 4 5
3: 1 2
4: 1 2 5
5: 2 4
```
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)