| 词条 | Path cover |
| 释义 |
Given a directed graph G = (V, E), a path cover is a set of directed paths such that every vertex v ∈ V belongs to at least one path. Note that a path cover may include paths of length 0 (a single vertex).[1] A path cover may also refer to a vertex-disjoint path cover, i.e., a set of paths such that every vertex v ∈ V belongs to exactly one path.[2] PropertiesA theorem by Gallai and Milgram shows that the number of paths in a smallest path cover cannot be larger than the number of vertices in the largest independent set.[3] In particular, for any graph G, there is a path cover P and an independent set I such that I contains exactly one vertex from each path in P. Dilworth's theorem follows as a corollary of this result. Computational complexityGiven a directed graph G, the minimum path cover problem consists of finding a path cover for G having the least number of paths. A minimum path cover consists of one path if and only if there is a Hamiltonian path in G. The Hamiltonian path problem is NP-complete, and hence the minimum path cover problem is NP-hard. However, if the graph is acyclic, the problem is in complexity class P and can therefore be solved in polynomial time by transforming it in a matching problem. ApplicationsThe applications of minimum path covers include software testing.[4] For example, if the graph G represents all possible execution sequences of a computer program, then a path cover is a set of test runs that covers each program statement at least once. See also
Notes1. ^{{harvtxt|Diestel|2005}}, Section 2.5. 2. ^{{harvtxt|Franzblau|Raychaudhuri|2002}}. 3. ^{{harvtxt|Diestel|2005}}, Theorem 2.5.1. 4. ^{{harvtxt|Ntafos|Hakimi|1979}} References
| last1=Bang-Jensen | first1= Jørgen | last2=Gutin |first2=Gregory | title=Digraphs: Theory, Algorithms and Applications | publisher=Springer | edition=1st | year=2006 | url=http://www.cs.rhul.ac.uk/books/dbook/ }}.
| last=Diestel | first=Reinhard | title=Graph Theory | publisher=Springer | year=2005 | edition=3rd | url=http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/ }}.
| doi=10.1017/S1446181100013894 | last1=Franzblau | first1=D. S. | last2=Raychaudhuri | first2=A. | title=Optimal Hamiltonian completions and path covers for trees, and a reduction to maximum flow | journal=ANZIAM Journal | year=2002 | volume=44 | issue=2 | pages=193–204 | url=http://www.austms.org.au/Publ/Jamsb/V44P2/1761.html }}.
| doi=10.1109/TSE.1979.234213 | last1=Ntafos | first1=S. C. | last2=Hakimi | first2=S. Louis. | title=On path cover problems in digraphs and applications to program testing | journal=IEEE Transactions on Software Engineering | year=1979 | volume=5 | issue=5 | pages=520–529{{DEFAULTSORT:Path Cover}}{{Compsci-stub}} 1 : Graph theory objects |
| 随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。