更改

有向无环图 (查看源代码)

2021年6月6日 (日) 23:03的版本

删除209字节、 2021年6月6日 (日) 23:03

→‎定义

第8行：第8行：

==定义==

图是由顶点和连接顶点对的边组成的，顶点可以是任何一种由边成对连接的对象。在有向图中，每条边都有一个方向，从一个顶点到另一个顶点。

−

有向图中的 '''路径 Path''' 是不重复的顶点<math>i_1,…,i_m</math>（至少2个）的序列，满足对于所有的<math>k=1,…,{~~m-1~~}</math>存在边在顶点<math>i_k</math>和顶点<math>i_{k+1}</math>~~之间。~~

+

有向图中的 '''路径 Path''' 是不重复的顶点<math>i_1,…,i_m</math>（至少2个）的序列，满足对于所有的<math>k=1,…,{m−1}</math>存在边在顶点<math>i_k</math>和顶点<math>i_{k+1}</math>之间; 如果一条路的第一条边的起始顶点与它的最后一条边的结束顶点相同，那么它就形成了一个环。有向无环图即为没有环出现的有向图。<ref name="thul">{{citation|title=Graphs: Theory and Algorithms|first1=K.|last1=Thulasiraman|first2=M. N. S.|last2=Swamy|publisher=John Wiley and Son|year=1992|isbn=978-0-471-51356-8|contribution=5.7 Acyclic Directed Graphs|page=118}}.</ref><ref name="bang">{{citation|title=Digraphs: Theory, Algorithms and Applications|first1=Jørgen|last1=Bang-Jensen|series=Springer Monographs in Mathematics|edition=2nd|publisher=Springer-Verlag|year=2008|isbn=978-1-84800-997-4|contribution=2.1 Acyclic Digraphs|pages=32–34}}.</ref><ref>{{citation|title=Graph theory: an algorithmic approach|first=Nicos|last=Christofides|author-link=Nicos Christofides||publisher=Academic Press|year=1975|pages=170–174}}.</ref>

−

~~<math>Y_x(u)=Y_{M_x}(u)</math>~~

−

~~有向图中的 '''路径 Path''' 是不重复的顶点（至少2个）的序列，满足序列中的顶点与序列中相邻的顶点有边连接~~; 如果一条路的第一条边的起始顶点与它的最后一条边的结束顶点相同，那么它就形成了一个环。有向无环图即为没有环出现的有向图。<ref name="thul">{{citation|title=Graphs: Theory and Algorithms|first1=K.|last1=Thulasiraman|first2=M. N. S.|last2=Swamy|publisher=John Wiley and Son|year=1992|isbn=978-0-471-51356-8|contribution=5.7 Acyclic Directed Graphs|page=118}}.</ref><ref name="bang">{{citation|title=Digraphs: Theory, Algorithms and Applications|first1=Jørgen|last1=Bang-Jensen|series=Springer Monographs in Mathematics|edition=2nd|publisher=Springer-Verlag|year=2008|isbn=978-1-84800-997-4|contribution=2.1 Acyclic Digraphs|pages=32–34}}.</ref><ref>{{citation|title=Graph theory: an algorithmic approach|first=Nicos|last=Christofides|author-link=Nicos Christofides||publisher=Academic Press|year=1975|pages=170–174}}.</ref>

孙钦贵

387

个编辑