更改

=== Construction from cyclic graphs ===

=== Construction from cyclic graphs ===

 

 

Any undirected graph may be made into a DAG by choosing a total order for its vertices and directing every edge from the earlier endpoint in the order to the later endpoint. The resulting orientation of the edges is called an acyclic orientation. Different total orders may lead to the same acyclic orientation, so an -vertex graph can have fewer than  acyclic orientations. The number of acyclic orientations is equal to χ(−1)}}, where  is the chromatic polynomial of the given graph.

Any undirected graph may be made into a DAG by choosing a total order for its vertices and directing every edge from the earlier endpoint in the order to the later endpoint. The resulting orientation of the edges is called an acyclic orientation. Different total orders may lead to the same acyclic orientation, so an -vertex graph can have fewer than  acyclic orientations. The number of acyclic orientations is equal to χ(−1)}}, where  is the chromatic polynomial of the given graph.

任何无向图都可以通过为其顶点选择一个总的顺序，并按顺序将前一个端点的每条边定向到后一个端点，从而构成一个 DAG。所得到的边的方向称为无圈方向。不同的总序可能导致相同的无圈取向，因此一个顶点图可以有少于个无圈取向。非循环取向的个数等于 χ (- 1)} ，其中是给定图的色多项式。

任意无向图都可以被转化为有向无环图。构造方法是选定一个顶点的全序关系Total order，并将无向图中所有边从全序关系中较前的顶点指向较后的顶点。这种方法是定向Orientation (graph theory)方法中的无环定向acyclic orientation。不同的全序关系可能推出相同的无环定向，因此一个包含n个顶点的图的无环定向数量小于n!。如果定义χ为给定图的色多项式Chromatic polynomial，无环定向数量等于|χ(−1)|。[19]

 

[[File:Graph Condensation.svg|thumb|upright=1.5|The yellow directed acyclic graph is the [[Condensation (graph theory)|condensation]] of the blue directed graph. It is formed by [[Edge contraction|contracting]] each [[strongly connected component]] of the blue graph into a single yellow vertex.]]

[[File:Graph Condensation.svg|thumb|upright=1.5|The yellow directed acyclic graph is the [[Condensation (graph theory)|condensation]] of the blue directed graph. It is formed by [[Edge contraction|contracting]] each [[strongly connected component]] of the blue graph into a single yellow vertex.]]

Any directed graph may be made into a DAG by removing a feedback vertex set or a feedback arc set, a set of vertices or edges (respectively) that touches all cycles. However, the smallest such set is NP-hard to find. An arbitrary directed graph may also be transformed into a DAG, called its condensation, by contracting each of its strongly connected components into a single supervertex. When the graph is already acyclic, its smallest feedback vertex sets and feedback arc sets are empty, and its condensation is the graph itself.

Any directed graph may be made into a DAG by removing a feedback vertex set or a feedback arc set, a set of vertices or edges (respectively) that touches all cycles. However, the smallest such set is NP-hard to find. An arbitrary directed graph may also be transformed into a DAG, called its condensation, by contracting each of its strongly connected components into a single supervertex. When the graph is already acyclic, its smallest feedback vertex sets and feedback arc sets are empty, and its condensation is the graph itself.

 

=== Transitive closure and transitive reduction ===

=== Transitive closure and transitive reduction ===