题目内容
（请给出正确答案）
[主观题]
在图G=（V，E)中，从给定的结点v出发，若中每一结点都是从v可达、而V-S中的每个结点都从v不可达，则
在图G=(V，E)中，从给定的结点v出发，若
中每一结点都是从v可达、而V-S中的每个结点都从v不可达，则称S为v的可达集合，记为d(v)=S。集合
称为V’的可达集合，记为d(V')=T，这里
.试在图8.13中，求出
.
答案
查看答案
重要提示：请勿将账号共享给其他人使用，违者账号将被封禁！
查看《购买须知》>>>
请输入或粘贴题目内容
搜题
拍照、语音搜题，请扫码下载APP
题目内容
（请给出正确答案）
在图G=(V，E)中，从给定的结点v出发，若中每一结点都是从v可达、而V-S中的每个结点都从v不可达，则称S为v的可达集合，记为d(v)=S。集合称为V’的可达集合，记为d(V')=T，这里.试在图8.13中，求出.
答案
更多“在图G=（V，E)中，从给定的结点v出发，若中每一结点都是从v可达、而V-S中的每个结点都从v不可达，则”相关的问题
第1题
证明对哈密顿图G=＜V,E＞删除S(
V)中的所有结点后,所得图G'的连通分支变数不大于|S|.
第2题
图的m着色问题描述如下:给定无向连通图G和m种不同的颜色.用这些颜色为图G的各顶点着色,每个顶点着一种颜色.如果有一种着色法,使G中每条边的2个顶点着不同颜色,则称这个图是m可着色的.图的m着色问题是对于给定图G和m种颜色,找出所有不同的着色法.
算法设计:对于给定的无向连通图G和m种不同的颜色,计算图的所有不同的着色法.
数据输入:由文件input.txt给出输入数据.第1行有3个正整数n,k和m,表示给定的图G有n个项点和k条边,m种颜色.顶点编号为1,2,...,n接下来的k行中,每行有2个正整数u、v,表示图G的一条边(u,v).
结果输出:将计算的不同的着色方案数输出到文件output.txt.
第3题
称d(u,v)为图G＜A,E＞=中结点u,v间的距离:
又称max{d(u,v)|u,v
V}为图G的直径,试求如图9.15所示的图的直径.
第5题
A.W≦|S|
B.W≠|S|
C.W≧|S|
D.W=|S|
第7题
问题描述:给定一个无向图G=(V.E),设
是G的顶点集.对任意
,若u∈U且v∈V-U,就称(u,1)为关于顶点集U的条割边.顶点集U的所有割边构成图G的一个割.G的最大割是指G中所含边数最多的割.
算法设计:对于给定的无向图G,设计一个优先队列式分支限界法,计算G的最大割.
数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和m,表示给定的图G有n个顶点和m条边,顶点编号为1,2,...,n.接下来的m行中,每行有2个正整数u和y,表示图G的一条边(u,v).
结果输出:将计算的最大割的边数和顶点集U输出到文件output.txt.文件的第1行是最大割的边数;第2行是表示顶点集U的向量x(1≤i≤n),x=0表示顶点i不在项点集U中,x=1表示顶点i在顶点集U中.
第8题
在以下假设下，重写Djkstra算法：
(1)用邻接表表示有向带权图G，其中每个边结点有3个域：邻接顶点vertex，边上的权值length和边链表的链接指针link
(2)用集合T=V(G)-S代替S(已找到最短路径的顶点集合)，利用链表来表示集合T。
试比较新算法与原来的算法，计算时间是快了还是慢了，给出定量的比较。
