用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否有关？

设为简单有向图G的邻接矩阵,证明A³的对角线元素表示经过结点v1的“三角形”的个数,即以v为一个结点的G的子图k₃的个数.

已知8个顶点所构成无向图的顶点横坐标xo、纵坐标ro及邻接矩阵A对应的上三角矩阵A分别为

画出该无向图。

对图9.17给出的有向图G:

(1)写出它的邻接矩阵A,用邻接矩阵计算各个结点的出度与人度.

(2)计算说出从出到后的长度为1,2,3,4的拟路径各有多少条.

(3)计算,说出它们中第2,3分量及第4,4分量的意义.

(4)计算它的路径矩阵B及可达性矩阵P,并从P说出G的各强分图.

用E_ij表示i行j列的元素为1，而其余元素全为零的nxn矩阵，A=(a_ij)_nxn。证明：

1)如果AE₁₂=E₁₂A，那么当k≠1时a_k1=0，当k≠2时a_2k=0;

2)如果AE_ij=E_ijA，那么当k≠i时a_ki=0，当k≠j时a_jk=0，且a_ii=a_jj;

3)如果A与所有的n级矩阵可交换，那么A一定是数量矩阵，即A=aE。

动到t.树状路径T.上有若干可移动的障碍物.由于路径狭窄,任何时刻在路径的任何位置不能同时容纳2个物体.每步可以将障碍物或机器人移到相邻的空顶点上.设计一个有效算法用最少移动次数使机器人从s运动到t.

算法设计:对于给定的树T,以及障碍物在树T中的分布情况,计算机器人从起点s到终点t的最少移动次数.

数据输入:由文件input.txt提供输入数据.文件的第1行有3个正整数n,s和t,分别表示树T的顶点数,起点s的编号和终点t的编号.

接下来的n行分别对应于树T中编号为0,1,...,n-1的项点.每行的第1个整数h表示顶点的初始状态,当h+1时表示该顶点为空顶点,当h=0时表示该顶点为满顶点,其中已有一个障碍物.第2个数k表示有k个顶点与该项点相连.接下来的k个数是与该顶点相连的顶点编号.

结果输出:将计算出的机器人最少移动次数输出到文件output.txt.如果无法将机器人从起点s移动到终点t,则输出“NoSolution!"

对于邻接矩阵A的简单有向图G,它的距离矩阵定义如下:

确定由图7-14所示的有向图的距离矩阵,并指出dij=1是什么意义？

集合是支配集.如果一个支配集的任何真子集都不是支配集,则称该支配集为最小支配集。

(a)在图8.10中找出两个不同大小的最小支配集。

(b)设棋盘的64个方块用64个顶点表示,如果两顶点对应的两个方块是在同一行，同一列或同一对角线上,则这两顶点之间有一条边。已知5个皇后能被放在棋盘上,使它们支配所有64个方块，而且5是必须的最小皇后数，再用图论名词叙述这一结论.

一种简单的绘图表，表示时间进展的数据称为

A.原因与效果图表

B.奔跑图表

C.相关图

D.决策矩阵

E.直方图

表示两个变量之间变化关系和相互作用的图称为

A.原因与效果图表

B.奔跑图表

C.相关图

D.决策矩阵

E.直方图