387
个编辑
更改
跳到导航
跳到搜索
第69行：
第69行： − +
→从其他图构建
=== 从其他图构建===
=== 从其他图构建===
任意无向图都可以被转化为有向无环图。构造方法是选定一个顶点的[[全序关系]]，并将无向图中所有边从全序关系中较前的顶点指向较后的顶点。这种方法是<font color="#ff8000"> 定向 </font>方法中的<font color="#ff8000"> '''无环定向 Acyclic orientation''' </font>。不同的全序关系可能推出相同的无环定向，因此一个包含{{mvar|n}}个顶点的图的无环定向数量小于{{math|''n''!}}<!---全序关系数量？--->。如果定义{{mvar|χ}}为给定图的[[色多项式]]，无环定向数量等于{{math|{{!}}''χ''(−1){{!}}}}。<ref>{{citation|first=Richard P.|last=Stanley|authorlink=Richard P. Stanley|title=Acyclic orientations of graphs|journal=Discrete Mathematics|volume=5|issue=2 |pages=171–178|year= 1973|doi=10.1016/0012-365X(73)90108-8|url=http://math.mit.edu/~rstan/pubs/pubfiles/18.pdf}}.</ref>
任意无向图都可以被转化为有向无环图。构造方法是选定一个顶点的<font color="#ff8000"> '''全序关系 Total order''' </font>，并将无向图中所有边从全序关系中较前的顶点指向较后的顶点。这种方法是<font color="#ff8000"> 定向 </font>方法中的<font color="#ff8000"> '''无环定向 Acyclic orientation''' </font>。不同的全序关系可能推出相同的无环定向，因此一个包含{{mvar|n}}个顶点的图的无环定向数量小于{{math|''n''!}}<!---全序关系数量？--->。如果定义{{mvar|χ}}为给定图的[[色多项式]]，无环定向数量等于{{math|{{!}}''χ''(−1){{!}}}}。<ref>{{citation|first=Richard P.|last=Stanley|authorlink=Richard P. Stanley|title=Acyclic orientations of graphs|journal=Discrete Mathematics|volume=5|issue=2 |pages=171–178|year= 1973|doi=10.1016/0012-365X(73)90108-8|url=http://math.mit.edu/~rstan/pubs/pubfiles/18.pdf}}.</ref>
任意有环有向图都可以被转化为有向无环图。只要从图中移除<font color="#ff8000"> '''反馈节点集 Feedback vertex set''' </font>或<font color="#ff8000"> '''反馈边集 Feedback arc set''' </font>，即对于图中每个环，至少包括环中一个顶点或边的集合。不过，找到反馈节点或边的最小集合是[[NP困难]]问题。<ref>{{citation | last1=Garey | first1=Michael R. | authorlink1=Michael Garey | last2=Johnson | first2=David S. | authorlink2=David S. Johnson | year=1979| title=[[Computers and Intractability|Computers and Intractability: A Guide to the Theory of NP-Completeness]]| publisher=[[W. H. Freeman and Company|W. H. Freeman]]| isbn=0-7167-1045-5| chapter = Problems GT7 and GT8| pages = 191–192}}</ref> 另外一种方法将有环有向图去环的方法是将每个强连通分量[[边收缩|收缩]]为一个顶点。<ref>{{citation|title=Structural Models: An Introduction to the Theory of Directed Graphs|last1=Harary|first1=Frank|author1-link=Frank Harary|last2=Norman|first2=Robert Z.|last3=Cartwright|first3=Dorwin|publisher=John Wiley & Sons|year=1965|page=63}}.</ref> 对于无环图，它的最小反馈顶点或边集为[[空集]]，它的强连通分量则为自身。
任意有环有向图都可以被转化为有向无环图。只要从图中移除<font color="#ff8000"> '''反馈节点集 Feedback vertex set''' </font>或<font color="#ff8000"> '''反馈边集 Feedback arc set''' </font>，即对于图中每个环，至少包括环中一个顶点或边的集合。不过，找到反馈节点或边的最小集合是[[NP困难]]问题。<ref>{{citation | last1=Garey | first1=Michael R. | authorlink1=Michael Garey | last2=Johnson | first2=David S. | authorlink2=David S. Johnson | year=1979| title=[[Computers and Intractability|Computers and Intractability: A Guide to the Theory of NP-Completeness]]| publisher=[[W. H. Freeman and Company|W. H. Freeman]]| isbn=0-7167-1045-5| chapter = Problems GT7 and GT8| pages = 191–192}}</ref> 另外一种方法将有环有向图去环的方法是将每个强连通分量[[边收缩|收缩]]为一个顶点。<ref>{{citation|title=Structural Models: An Introduction to the Theory of Directed Graphs|last1=Harary|first1=Frank|author1-link=Frank Harary|last2=Norman|first2=Robert Z.|last3=Cartwright|first3=Dorwin|publisher=John Wiley & Sons|year=1965|page=63}}.</ref> 对于无环图，它的最小反馈顶点或边集为[[空集]]，它的强连通分量则为自身。