首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
证明:对有向图的顶点适当地编号,可使其邻接矩阵为下三角形且主对角线为全O的充要条件是该图为无环图。
证明:对有向图的顶点适当地编号,可使其邻接矩阵为下三角形且主对角线为全O的充要条件是该图为无环图。
admin
2018-08-12
28
问题
证明:对有向图的顶点适当地编号,可使其邻接矩阵为下三角形且主对角线为全O的充要条件是该图为无环图。
选项
答案
此题考查的知识点是无环图的定义。根据题意,该有向图顶点编号的规律是让弧尾顶点的编号大于弧头顶点的编号。由于不允许从某顶点发出并回到自身顶点的弧,所以邻接矩阵主对角线元素均为0。先证明该命题的充分条件。由于弧尾顶点的编号均大于弧头顶点的编号,在邻接矩阵中,非零元素(A[i][j]=1)自然是落到下三角矩阵中;命题的必要条件是要使上三角为0,则不允许出现弧头顶点编号大于弧尾顶点编号的弧,否则,就必然存在环路。(对该类有向无环图顶点编号,应按顶点出度顺序编号。)
解析
转载请注明原文地址:https://kaotiyun.com/show/KwRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
春秋时期的鲁国初税亩和战国时期以商鞅变法为代表的各国变法,在历史上产生了深刻的影响。这些变法的最大作用和产生的最主要的社会后果是()。
近代中国各派军阀的共同点有()①始终打着维护共和制度的旗号②利用中央政权排斥异己③都试图夺取中央政权④以帝国主义列强为靠山
1920年,苏俄农民中流传着这样的说法:“土地属于我们,面包却属于你们;水属于我们,鱼却属于你们;森林属于我们,木材却属于你们”,它反映的是战时共产主义政策()。
以下不是巴黎和会的主要议题的是()
首次提出“长期共存,互相监督”观念的是在文件()中。
简述中、苏分歧和中、苏同盟关系破裂的原因及其影响。
下列不是唐玄宗组织编撰的是()。
到1869年为止,人类已发现了多少种化学元素()。
下列哪两个国家是第二次工业革命的发源地和“中心”?
1854年,英国外交大臣致函英国驻华公使说:“为了适应外商对农业产品已增加了的需要,新的贸易市场尚待开辟。”1856年,法国外长则指令法国驻华代办强调“商业关系的推广”,并强调“这是一个关系到至高无上权益的问题”。这说明()。
随机试题
老年人自我保健的措施包括___________、自我治疗、自我护理、自我预防和自我急救。
在现实中我们通常能够看到这样一种现象:高校的校长多是某学科的学术专家,医院的院长多是某领域的医学专家。但是,有些技术能手却未能成为称职的管理者。对此,你的看法是()
(Many)awoman(feel)(entitled)to(more)inlifethanjusthousework.
职工在()情况下,可申请住房公积金贷款。
大中型建设工程项目立项批准后,建设单位应按( )顺序办理相应手续。
一个人的吸烟行为是()。
影响问题解决的定势包括()
下列叙述不正确的一项是:
ACanadianresearcherhasdiscoveredthatsoundtravels【21】______airmorethanone-halfkilometeranhourslowerthanhadb
HintsandTipstoSaveMoneySpendlessThisisnotoversimplifyingthebestwaytosavemoney!Itisessentialifyouares
最新回复
(
0
)