387
个编辑
更改
跳到导航
跳到搜索
第79行：
第79行： +
→从其他图构建
任意无向图都可以被转化为有向无环图。构造方法是选定一个顶点的<font color="#ff8000"> '''全序关系 Total order''' </font>，并将无向图中所有边从全序关系中较前的顶点指向较后的顶点。这种方法是定向方法中的<font color="#ff8000"> '''无环定向 Acyclic orientation''' </font>。不同的全序关系可能推出相同的无环定向，因此一个包含{{mvar|n}}个顶点的图的无环定向数量小于{{math|''n''!}}<!---全序关系数量？--->。如果定义{{mvar|χ}}为给定图的<font color="#ff8000"> '''色多项式 Chromatic polynomial''' </font>，无环定向数量等于{{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"> '''无环定向 Acyclic orientation''' </font>。不同的全序关系可能推出相同的无环定向，因此一个包含{{mvar|n}}个顶点的图的无环定向数量小于{{math|''n''!}}<!---全序关系数量？--->。如果定义{{mvar|χ}}为给定图的<font color="#ff8000"> '''色多项式 Chromatic polynomial''' </font>，无环定向数量等于{{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>
[[file:Example_of_a_directed_acyclic_graph.png|thumb|right|175px|图9：黄色有向无环图是蓝色有向图的缩合。它是通过将蓝色图的每个强连通部分收缩为一个黄色顶点而形成的]]
任意有环有向图都可以被转化为有向无环图。只要从图中移除<font color="#ff8000"> '''反馈节点集 Feedback vertex set''' </font>或<font color="#ff8000"> '''反馈边集 Feedback arc set''' </font>，即对于图中每个环，至少包括环中一个顶点或边的集合。不过，找到反馈节点或边的最小集合是<font color="#ff8000"> '''NP困难 NP-hard''' </font>问题。<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"> '''空集''' </font>，它的强连通分量则为自身。
任意有环有向图都可以被转化为有向无环图。只要从图中移除<font color="#ff8000"> '''反馈节点集 Feedback vertex set''' </font>或<font color="#ff8000"> '''反馈边集 Feedback arc set''' </font>，即对于图中每个环，至少包括环中一个顶点或边的集合。不过，找到反馈节点或边的最小集合是<font color="#ff8000"> '''NP困难 NP-hard''' </font>问题。<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"> '''空集''' </font>，它的强连通分量则为自身。