打开主菜单
首页
随机
登录
设置
关于集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织
免责声明
集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织
搜索
更改
←上一编辑
下一编辑→
有向无环图 Directed acyclic graph
(查看源代码)
2021年6月21日 (一) 20:27的版本
删除8字节
、
2021年6月21日 (一) 20:27
→基于邻接矩阵判断有向图有没有环
第92行:
第92行:
===基于邻接矩阵判断有向图有没有环===
===基于邻接矩阵判断有向图有没有环===
−
对于有向图<math>G=(V,E)</math>,构造<math>d=\mid V \mid</math>阶方阵<math>B=
(b_
{ij}
)_
{d*d}</math>,其中
+
对于有向图<math>G=(V,E)</math>,构造<math>d=\mid V \mid</math>阶方阵<math>B=
(b_
{ij}
)_
{d*d}</math>,其中
:<math>b_{ij}=\mid e_k \mid,e_k=(v_i,v_j)\in E</math>
:<math>b_{ij}=\mid e_k \mid,e_k=(v_i,v_j)\in E</math>
称矩阵<math>B</math>为有向图<math>G</math>的节点邻接矩阵。
称矩阵<math>B</math>为有向图<math>G</math>的节点邻接矩阵。
第102行:
第102行:
'''定理''':
'''定理''':
−
对于邻接矩阵 <math> B=
(b_
{ij}
)_
{d*d} </math>, <math> B </math>是有向无环图当且仅当
+
对于邻接矩阵 <math> B=
(b_
{ij}
)_
{d*d} </math>, <math> B </math>是有向无环图当且仅当
:<math> tr(e^B)=d</math>
:<math> tr(e^B)=d</math>
孙钦贵
387
个编辑