题目内容
（请给出正确答案）
关联矩阵(incidence matrix)是描述和实现图算法的另一重要方式，对于含有n个顶点、e条边的图，对应的关联矩阵I[][]共有n行e列。在无向图中，对于任意的0≤i＜n和0≤j＜e，若第i个顶点与第j条边彼此关联，则定义I[[i][j]=1;否则，定义I[[i][j]=0。
a)关联矩阵与邻接矩阵有何联系？
b)有向图的关联矩阵应如何定义？
c)有向图的关联矩阵，与邻接矩阵又有何联系？
d)基于关联矩阵，可以解决哪些问题？试举一例。
安装简答题APP，拍照搜题省时又省心！
更多“关联矩阵（incidence matrix)是描述和实现图算…”相关的问题
(1)如果ADJ是图G=(V，E)的邻接矩阵，INC是关联矩阵，试说明在什么条件下将有ADJ=lNC×INCT-I，其中，INC是矩阵INC的转置矩阵，I是单位矩阵。两个nxn的矩阵的乘积C=A×B定义为
公式中的“∪”定义为按位加，“∩”定义为按位乘。
(2)设用邻接矩阵表示的图的定义如下。
试仿照上述定义，建立用关联矩阵表示的图的结构。
(3)以关联矩阵为存储结构，实现图的DFS的递归算法。
A、O(n）
B、O(
)
C、O(n*e）
D、O(n+e）
A、O(
)
B、O(n*e）
C、O(n+e）
D、O(n）
N个顶点的连通图的生成树含有__________条边。【中山大学1998一、9(1分)】
令G=(X，△，Y)为一个二分图。设有正整数p，使X的每一个顶点至少与p条边关联，并且Y的每一个顶点最多与p条边关联。试证明Y至少与X有同样多的顶点。
关于图(Graph)的一些问题： (1)有n个顶点的有向强连通图最多有多少条边？最少有多少条边？ (2)表示有1 000个顶点、1 000条边的有向图的邻接矩阵有多少个矩阵元素？是否为稀疏矩阵？ (3)对于一个有向图，不用拓扑排序，如何判断图中是否存在环？
A.如果一个连通图有r个顶点，则其完全关联矩阵的秩为r-1。
B.完全关联矩阵每一行元素的和对应于顶点的度数。
C.完全关联矩阵一行中的元素全为0，其对应的顶点为孤立点。
D.完全关联矩阵中两个平行边对应的两列相同。
在含有n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（）。
A．e
B．2e
C．n2-e
D．n2-2e
为了保护您的账号安全，请在“简答题”公众号进行验证，点击“官网服务”-“账号验证”后输入验证码“”完成验证，验证成功后方可继续查看答案！
微信搜一搜
简答题
微信搜一搜
简答题
如搜索结果不匹配，请 
去掉任何一个顶点及其与之关联的边之后是哈密顿图。
