4.1节后习题 - 图的基本概念
一、判断题
二、选择题
三、计算题
1. 无向图连通性判断
题目：给定一个无向图，顶点集合为 V={A,B,C,D,E}，边集合为 E={(A,B),(A,C),(B,C),(B,D),(C,D),(D,E)}。判断该图是否为连通图。
答案与解析
答案：该无向图是连通图。
解析：对于给定的无向图，顶点集合V = {A, B, C, D, E}，边集合E = {(A, B), (A, C), (B, C), (B, D), (C, D), (D, E)}。从顶点A出发，通过边(A, B)可到达B，通过边(A, C)可到达C；因为有边(B, C)，所以B和C相互可达；又有边(B, D)和(C, D)，则A、B、C都可到达D；最后由边(D, E)可知，A、B、C、D都能到达E。即对于图中任意两个顶点，都存在路径相连，所以该无向图是连通图。
核心知识点：无向图连通性的判断方法，通过检查图中顶点之间是否存在路径来确定无向图的连通性，若任意两个顶点之间都有路径，则该无向图是连通图。
2. 有向图强连通性判断
题目：给定一个有向图，顶点集合为 V={A,B,C,D}，边集合为 E={(A,B),(B,C),(C,D),(D,A),(A,C)}。判断该图是否为强连通图。
答案与解析
答案：该有向图是强连通图。
解析：对于给定的有向图，顶点集合V = {A, B, C, D}，边集合E = {(A, B), (B, C), (C, D), (D, A), (A, C)}。从顶点A出发，通过边(A, B)到达B，再通过(B, C)到达C，接着通过(C, D)到达D，然后由(D, A)回到A，说明从A出发可以到达图中所有顶点，且所有顶点都能回到A；从顶点B出发，经过(B, C)、(C, D)、(D, A)、(A, B)也能回到B，并且能到达其他所有顶点；同理，从顶点C和D出发，也都能到达图中所有顶点且能回到自身。即对于该有向图中任意两个顶点u和v，既存在从u到v的路径，也存在从v到u的路径，所以该有向图是强连通图。
核心知识点：有向图强连通性的定义及判断方法，有向图中若任意两个顶点相互可达，则该有向图是强连通图，需要对图中每个顶点进行分析判断。
四、应用题
1. 交通网络最短路径
题目：在一个交通网络中，有5个城市，分别用顶点 A,B,C,D,E 表示。城市之间的道路用边表示，道路的长度用边的权重表示。给定边集合和权重如下： E={(A,B,10),(A,C,15),(B,C,20),(B,D,25),(C,D,30),(D,E,35)}。 问题：从城市 A 到城市 E 的最短路径是什么？
答案与解析
答案：从城市A到城市E的最短路径是A - B - D - E，最短路径长度为10 + 25 + 35 = 70。
解析：已知边集合E = {(A, B, 10), (A, C, 15), (B, C, 20), (B, D, 25), (C, D, 30), (D, E, 35)}。可以使用迪杰斯特拉（Dijkstra）算法等最短路径算法来求解。从A出发，首先A - B的距离为10，A - C的距离为15，B距离A更近；以B为中间点，B - D的距离为25，此时A - B - D的总距离为10 + 25 = 35；再以D为中间点，D - E的距离为35，所以A - B - D - E的总距离为10 + 25 + 35 = 70。其他可能的路径如A - C - D - E的距离为15 + 30 + 35 = 80等，比较后可知A - B - D - E是最短路径。
核心知识点：最短路径算法（如迪杰斯特拉算法）的原理和应用，图中边权重的概念，边的权重表示路径的长度，在求解最短路径时，根据边的权重计算不同路径的总长度并进行比较。
2. 社交网络连通性分析
题目：在一个社交网络中，有4个用户，分别用顶点 A,B,C,D 表示。用户之间的关系用边表示，给定边集合如下： E={(A,B),(A,C),(B,C),(B,D),(C,D)}。 问题：该社交网络是否为连通图？为什么？
答案与解析
答案：该社交网络是连通图。
解析：已知社交网络中顶点集合为{A, B, C, D}，边集合E = {(A, B), (A, C), (B, C), (B, D), (C, D)}。从顶点A出发，通过边(A, B)可到达B，通过边(A, C)可到达C；因为有边(B, C)，所以B和C相互可达；又有边(B, D)和(C, D)，则A、B、C都可到达D。即对于社交网络中任意两个用户顶点，都存在路径相连，所以该社交网络是连通图。
核心知识点：无向图连通性的判断，将社交网络抽象为无向图，用户为顶点，用户之间的关系为边，根据无向图连通性的定义判断社交网络中任意两个用户是否可达，若可达则社交网络是连通的。