在无向图G的邻链矩阵A中,若A[i][j]等于1 ,则A[i][j]等于（ ）

一道离散数学证明题 证明：没有3阶子图的完全无向图的子图的n阶简单无向图最多有【n²/4】条边

一道离散数学证明题 证明：没有3阶子图的完全无向图的子图的n阶简单无向图最多有【n²/4】条边
证明：没有3阶子图的完全无向图的子图的n阶简单无向图最多有【n²/4】条边

mumuzhan1年前1

liangkun51326 共回答了16个问题 | 采纳率68.8%

因为该完全无向图无3阶子图,所以其子图的n阶简单无向图中n

1年前查看全部

已知带权的无向图的邻接矩阵（如图）,画出该图及其最小生成树.

我本宁静1年前1

angryriver 共回答了18个问题 | 采纳率88.9%

如图所示.点击下图,可查看大图.

1年前查看全部

2．知有8个结点值为A、B、C、D、E、F、G和H的无向图,其邻接矩阵的存储结构见表.（1）画出此无向图.（2

2．知有8个结点值为A、B、C、D、E、F、G和H的无向图,其邻接矩阵的存储结构见表.（1）画出此无向图.（2
就这些分了- -

tmjxf1年前1

402933916 共回答了11个问题 | 采纳率90.9%

直接插入:46,58 剩下的待排
冒泡:14,18,37,42,48,64,96,96
快速:以第70为基准 68,73,69,23,93,18,11,70
直接选择:2,3,4 剩下的待排
堆排序:用大根堆 第一次选出94 第二次为73,23,71,68,72,16,5
归并:用二路归并 5,26,1,77,11,61,15,59,19,48
基数:用最低位 505,008,109,930,63,269,278,83,184,589

1年前查看全部

若一个无向图有n个顶点,e条边（n>e）,且是一个森林.则它有____棵树.

丘丘_vv1年前1

fd_Goblin 共回答了19个问题 | 采纳率100%

假设有x棵树,在树林间加入x-1条边,使其成为一棵树,由树的定义可以知道：e=n-1,代入得：n-1=e+x-1,解得x=n-e,即它有n-e棵树.
图论一章节啊,加油!

1年前查看全部

对某个无向图的邻接矩阵来说,下列叙述正确的是

对某个无向图的邻接矩阵来说,下列叙述正确的是
A、第i行上的非零元素个数和第i列上的非零元素个数一定相等
B、矩阵中的非零元素个数等于图中的边数
C、第i行与第i列上的非零元素的总数等于顶点vi的度数
D、矩阵中非全零行的行数等于图中的顶点数

重型cc兔1年前1

yingzi1972 共回答了22个问题 | 采纳率95.5%

选A.因为无向图没有方向,所以相应的邻接矩阵是对称的

1年前查看全部

一道离散数学图论题,急!题目是：若一无向图有5个顶点,如果它的补图是连通图,那么这个无向图最多有几条边?答案是6.请问详

一道离散数学图论题,急!
题目是：
若一无向图有5个顶点,如果它的补图是连通图,那么这个无向图最多有几条边?
答案是6.
请问详解是什么?说仔细点,谢谢!

一米阳光19841年前2

石青沸冰 共回答了16个问题 | 采纳率87.5%

首先知道什么是无向图的补图吧?就是所有节点保留,两点之间有边的,补图里面没边,两点之间没边的,补图里面有边,原图边数＋补图边数等于C(5,2)=10……所以求无向图最多有多少边,就是求补图最少有多少边,既然它说补图是连通的,所以补图最少有4条边（树图）,10-4=6,所以原图中最多就有6条边了～
另外这道题是有前提的,就是无向简单图,简单图是指无自环、无平行边.
有问题请补充,满意请采纳～

1年前查看全部

问一道数据结构 求无向图和邻接表的习题

问一道数据结构 求无向图和邻接表的习题
麻烦老师讲解一下 ,设无向图有6个节点,依次输入的9条边为（1,2）（1,3）（1,5）（1,6）（2,3）（3,4）（3,5）（4,5）（5,6）.1.画出无向图G.2.画出G的邻接表

面交相映新1年前0

共回答了个问题 | 采纳率

查看全部

证明:对于一个无向图G=(V,E),若G中各顶点的度均大于或等于2,则G中比存在回路

bearqi1年前1

nishizenme 共回答了13个问题 | 采纳率92.3%

简单的说,就是没有回路,必有叶子节点,与度不为1矛盾
复杂的说：
反证：如果G中不存在回路,则必有一个节点的度为1
可以说明：任意找一个节点,开始遍历,那么最终会访问到一个叶子节点.
任何一个访问到的节点u,存在以下几种情况
1. 是叶子节点（证明结束）
2. 存在节点v,v尚未被访问,且边(u,v)存在,则继续访问v
3. 任何与u有边相连的节点都已经被访问,这种情况会构成回路（与假设矛盾,证明结束）
因为节点个数有限,所以只有有限次可能会落入情况2,随着遍历的进行,必然会落入情况1和3

1年前查看全部

已知一个图的邻接矩阵或邻接表,如何判断此图是有向图还是无向图

luohuafeixu1年前1

wu_shi123 共回答了19个问题 | 采纳率94.7%

如果有对称元素 aij 和 aji 分别是1和0,那么一定是有向图(有一条有向边连接两点)
但如果所有的对应元素都相同,就无法判断是有向图还是无向图

1年前查看全部

试编写求无向图G的连通分量的算法.要求输出每一连通分量的顶点值.(设图G已用邻接表存储)

试编写求无向图G的连通分量的算法.要求输出每一连通分量的顶点值.(设图G已用邻接表存储)
我有一个答案了,但是不是很明白希望可以有人给我用通俗点的语言解释清楚,最好你可以再给我一个算法~
void dfs ( int v)
　　{
visited[v]=1; printf ("%3d",v); //输出连通分量的顶点
p=g[v].firstarc;
while （p!=null）
　　{
if(visited[p->adjvex]==0)
dfs(p->adjvex);
p=p->next;
}
　　}
　　void Count(AdjList g) //求图中连通分量的个数
　　{
　　int k=0 ;
　　for (i=1;i

ruanwuyi1年前2

langzi2001958 共回答了22个问题 | 采纳率90.9%

你肯定还没看懂邻接表,adjvex就是顶点的数组地址,每个顶点都有自己的物理地址,通过数组来存储比较方便操作,不然怎么找到它,你想想.至于前面的算法,我想你看懂了邻接表之后看算法很简单了,这算法没什么技术含量.就是直接利用邻接表的特点

1年前查看全部

离散数学A无向完全图都是欧拉图 B有n个结点n-1条边的无向图都是树 C无向完全图都是平面图 D树的每条边都是割边 那个

离散数学
A无向完全图都是欧拉图 B有n个结点n-1条边的无向图都是树 C无向完全图都是平面图 D树的每条边都是割边 那个对

wangman1111年前1

shendan69 共回答了19个问题 | 采纳率94.7%

D
某条边要不是割边就形成圈了

1年前查看全部

用数学归纳法证明：设G施简单、无向的图.如果G是树,则G有n-1条确定的边.

潜水飞猪1年前1

love京剧 共回答了15个问题 | 采纳率93.3%

可以证明 1：连通简单图的边数>=n-1
2：无圈图的边数

1年前查看全部

1已知一个无向图G的顶点集E(G)={A,B,C,D,E},其邻接矩阵如图所示：01001 10010 00011 01

1已知一个无向图G的顶点集E(G)={A,B,C,D,E},其邻接矩阵如图所示：01001 10010 00011 01101 10110 （1）画
已知一个无向图G的顶点集E(G)={A,B,C,D,E},其邻接矩阵如图所示：
01001
10010
00011
01101
10110
（1）画出该图的图形
（2） 写出从顶点A出发进行深度优先遍历和广度优先遍历的遍历序列.

明月心20061年前1

chixg 共回答了19个问题 | 采纳率100%

（1）、如图所示.
（2）、深度优先：ABDCE
广度优先：ABEDC

1年前查看全部

哈斯图是描述以下哪种对象的?A.等价关系B.偏序关系C.有向图D.无向图

田梅1年前1

小贝其 共回答了17个问题 | 采纳率94.1%

偏序关系
这个要学一下离散数学才知道

1年前查看全部

在含有n个顶点和e条边的无向图的邻接矩阵中令元素的个数为（）

在含有n个顶点和e条边的无向图的邻接矩阵中令元素的个数为（）
A n的平方减2e
B n的平方减e
C 2e
D e

iris-1231年前0

共回答了个问题 | 采纳率

查看全部

判断：一个无向图的邻接矩阵中各元素之和与图中边的条数相等

ddxx12191年前1

btcainiao 共回答了15个问题 | 采纳率100%

不对.一个无向图的邻接矩阵中各元素之和是图中边的条数的两倍.

1年前查看全部

求代码,建立无向图,输入一个邻接矩阵,1求边的条数2任意两个顶点是否有边相连3.任意一个顶点的度是多少

wsww36101年前1

danny2isabella 共回答了20个问题 | 采纳率95%

这个其实很好办的,在有向图的基础上,作如下修改.创建有向图的过程中,用一个数来表示是否相连,可以设置weight为1或0.可以在确定一条弧的两个顶点后,locate其位置后将其的权值定为1或0,1表示相连,0表示不相连.这时候赋值的时候写两句,比如说这样：
G->arcs[i][j].adj=weight;
G->arcs[j][i].adj=weight;
其中i,j分别表示所在的行与列.G是一个图,arcs是一个邻接矩阵,adj就是权值,weight是具体的值,为1或0.这里写了两遍的语句就是实现了无向图的创建.其他的程序就可以依此进行修改,这个还是比较简单的,好好写吧.

1年前查看全部

在含n个顶点和e条边的无向图的邻阶矩阵中,零元素的个数?

在含n个顶点和e条边的无向图的邻阶矩阵中,零元素的个数?
什么是零元素啊

观世观点1年前1

MANJJ1030 共回答了27个问题 | 采纳率92.6%

无向的邻接矩阵一定是对称阵.当vi与vj中间有一条边相连接时,则a(ij)=1,否则为0.e条边对应了n个顶点的度的和为2e.所以零元素的个数为n^2-2e

1年前查看全部

邻接矩阵和邻接表删除有向图或无向图的一条边的算法.急用.尽量简单些就好.

jinjoy1年前1

李逢浪 共回答了19个问题 | 采纳率84.2%

删边i-j
邻接矩阵：
有向图：map[i][j] = 0;
无向图：map[i][j] = map[j][i] = 0;
邻接表：
有向图：
p = v[i] -> firstedge；
pre = p;
while (p && p -> data != j)
{pre = p;p = p -> next;}
if (p && pre == p) v[i] -> firstedge = p -> next;
else if (p) pre -> next = p -> next;
无向图：
p = v[i] -> firstedge；
pre = p;
while (p && p -> data != j)
{pre = p;p = p -> next;}
if (p && pre == p) v[i] -> firstedge = p -> next;
else if (p) pre -> next = p -> next;
p = v[j] -> firstedge；
pre = p;
while (p && p -> data != i)
{pre = p;p = p -> next;}
if (p && pre == p) v[j] -> firstedge = p -> next;
else if (p) pre -> next = p -> next;

1年前查看全部

数据结构的一些问题~1、连通图含义?2、n个顶点的无向图、有向图,最少、最多边数?3、n个顶点的非连通图,最多边数?4、

数据结构的一些问题~
1、连通图含义?
2、n个顶点的无向图、有向图,最少、最多边数?
3、n个顶点的非连通图,最多边数?
4、n个顶点有向图,顶点的度最小?最大?
5、有向图顶点入度、出度关系?
6、邻接矩阵、邻接表看边的个数?空间复杂性分别为?
7、与邻接表表示相比,邻接矩阵表示更适合什么图?

乐此Bu疲1年前1

wangjiel 共回答了21个问题 | 采纳率100%

1、连通图
图内任意两个顶点均有可达路径,其中有向图的话,所有边都看作无向.满足这一性质的图为连通图
2、由于没说一定连通,所以有向图与无向图最少边数均为0
最多的话,有向图为n*(n-1),无向图为n*(n-1)/2
3、无向图,理论最多边数为(n^2-n)/4,其中点的数目平均分布在两个连通分量
假定一边为x,则边数为x*(x-1)/2,另一边就是(n-x)(n-x-1)/2,两项和取最大值.
4、由于没说一定连通,所以最小度为0
最大度,为n-1入度与n-1出度
5、所有顶点的入度之和等于所有顶点的出度之和
6、假定点数为n,边数为e.
邻接矩阵存储空间为n^2
邻接表存储空间为n+e（有向图）,n+e*2（无向图,因为无向图一条边是拆成两条有向边来存）
7、矩阵适合稠密图,即边比较多的图~

1年前查看全部

设计一个算法,求无向图G(采用邻接表存储)的连通分量的个数

设计一个算法,求无向图G(采用邻接表存储)的连通分量的个数
设计一个算法,求无向图G（采用邻接表存储）的连通分量的个数
试计算n个结点的m叉树转化为二叉树所需的存储资源比未转化前用定长节点存储节省了多少?

znjkkk1年前1

苕窝窝 共回答了14个问题 | 采纳率100%

int Count(Graph G)
{
int count=0;
for(v=0;v

1年前查看全部

设G=为无环的无向图,|V|=6,|E|=16,则G是（）

设G=为无环的无向图,|V|=6,|E|=16,则G是（）
A.完全图 B.零图 C.D.多重图
设A和B都是有限集合,且|A|=m,|B|=n,m≤n,则从A到B有___种不同的双射函数
A.m+n B.m×n C.n*m D.
无向图G中的边e是G的割边的充要条件是（）.
A.e是重边 B.e不是重边 C.e不包含在G的任一简单回路中 D.e不包含在G的某一回路中
设A={a,b,c},A上二元关系R={,,},则关系R的自反闭包S(R)是____
A.R∪{} B.R C.R∪R*-1 D.R∩I(A)

麦科拉伍1年前1

为情所伤96 共回答了27个问题 | 采纳率88.9%

设G=为无环的无向图,|V|=6,|E|=16,则G是（D）
A.完全图 B.零图 C.简单图 D.多重图
设A和B都是有限集合,且|A|=m,|B|=n,m=n,则从A到有_D__种不同的双射函数
A.m+n B.m×n C.n*m D.m!
无向图G中的边e是G的割边的充要条件是（D）.
A.e是重边 B.e不是重边 C.e不包含在G的任一简单回路中 D.e不包含在G的某一回路中
设A={a,b,c},A上二元关系R={,,},则关系R的自反闭包S(R)是_A___
A.R∪{} B.R C.R∪R*-1 D.R∩I(A)

1年前查看全部

无论有向图还是无向图,顶点数n、边数e和度数之间有什么关系?

鸿爱柳1年前2

躲啊躲啊ww 共回答了21个问题 | 采纳率90.5%

总的度数=2e
e=n(n-1)/2

1年前查看全部

离散数学中树的概念问题离散数学中图论那章里有树的定义,说连通的无回路的无向图就是树,我不解,既然是连通的,怎么可能无回路

离散数学中树的概念问题
离散数学中图论那章里有树的定义,说连通的无回路的无向图就是树,我不解,既然是连通的,怎么可能无回路呢?万分感激!

xiaweicao1年前0

共回答了个问题 | 采纳率

查看全部

设一个无向图G=(V,E)有n个顶点n+1条边,证明G中至少有一个顶点的度数大于或等于3.

设一个无向图G=(V,E)有n个顶点n+1条边,证明G中至少有一个顶点的度数大于或等于3.
要有证明过程喽!

技术分析1年前1

shili369 共回答了21个问题 | 采纳率95.2%

假设G中每个顶点的度数最大等于2
边数=2n/2=n

1年前查看全部

已知一个无向图G=(V,E),其中V={V1,V2,V3,V4},其邻接矩阵如下

已知一个无向图G=(V,E),其中V={V1,V2,V3,V4},其邻接矩阵如下
0 1 1 1
1 0 1 1
1 1 0 0
1 1 0 0
请还原G图,并画出G的邻接表
根据邻接表,求从V1开始的深度遍历序列和广度遍历序列及其对应的生成树

颠翼1年前1

tnq111 共回答了15个问题 | 采纳率93.3%

邻接表：
v1: v2 - v3 - v4
v2: v1 - v3 - v4
v3: v1 - v2
v4: v1 - v2
深度遍历序列：v1 - v2 - v3 - v4
对应的生成树包含的边是：e12, e24, e23
广度遍历序列：v1 - v2 - v4 - v3
对应的生成树包含的边是：e12, e14, e23

1年前查看全部

急,一个无向图,如何从邻接矩阵看出它所代表的图是欧拉图

急,一个无向图,如何从邻接矩阵看出它所代表的图是欧拉图
一个无向图,如何从邻接矩阵看出它所代表的图是欧拉图

qiuligegirl551年前1

婀娜飞雪 共回答了14个问题 | 采纳率92.9%

无向图是欧拉图的充要条件是每个顶点度数为偶数,
你数邻接矩阵每一行1的个数,如果各行均是偶数,就是欧拉图

1年前查看全部

已知无向图g,写一个算法判断是否存在一条从v0出发,包含所有节点的简单路径

mmickeyy1年前1

jiahua520555 共回答了18个问题 | 采纳率94.4%

核心思想就是对图进行遍历,至于选择DFS(深度优先搜索)还是BFS(广度优先搜索)要根据情况考虑,如果不光需要知道能否有路径到达,还要知道有多少条路径,可以考虑采用DFS.如果只是判断是否存在路径,则只需广度优先搜索即可.从一个点,向外扩展到其它的点,再从这些点又开始向开扩展,直到没有节点可以被扩展即可判断是否存在路径.再打个比方,好比在一个点倒水,这些水会通过有向边流到其它的点,再在这些上一步流到的点继续倒水,它又会继续向周边通过有向边流到其他的点,一直重复,直到没有新的点有水流到.
PS:在不统计路径数量的前提下,选择BFS时间复杂度远低于DFS,速度更快.

1年前查看全部