We introduce a homotopy theory of digraphs (directed graphs) and prove its
basic properties, including the relations to the homology theory of digraphs
constructed by the authors in previous papers. In particular, we prove the
homotopy invariance of homologies of digraphs and the relation between the
fundamental group of the digraph and its first homology group.
The category of (undirected) graphs can be identified by a natural way with a
full subcategory of digraphs. Thus we obtain also consistent homology and
homotopy theories for graphs. Note that the homotopy theory for graphs
coincides with the one constructed in the paper of Babson et.

该论文介绍了有向图的同伦理论并证明了其基本性质，包括与作者在之前的论文中构建的有向图同调理论的关系，特别是证明了有向图的同调不变性以及其基本群和第一同调群之间的关系。同时，研究者还确定了无向图的同调理论，并发现了它与 Babson 等人在一篇论文中构建的同伦理论的一致性。

有向图的同伦论

Homotopy theory for digraphs

For several computational problems in homotopy theory, we obtain algorithms
with running time polynomial in the input size. In particular, for every fixed
k>1, there is a polynomial-time algorithm that, for a 1-connected topological
space X given as a finite simplicial complex, or more generally, as a
simplicial set with polynomial-time homology, computes the k-th homotopy group
\pi_k(X), as well as the first k stages of a Postnikov system of X. Combined
with results of an earlier paper, this yields a polynomial-time computation of
[X,Y], i.e., all homotopy classes of continuous mappings X -> Y, under the
assumption that Y is (k-1)-connected and dim X < 2k-1. We also obtain a
polynomial-time solution of the extension problem, where the input consists of
finite simplicial complexes X,Y, where Y is (k-1)-connected and dim X < 2k,
plus a subspace A\subseteq X and a (simplicial) map f:A -> Y, and the question
is the extendability of f to all of X.
The algorithms are based on the notion of a simplicial set with
polynomial-time homology, which is an enhancement of the notion of a simplicial
set with effective homology developed earlier by Sergeraert and his co-workers.
Our polynomial-time algorithms are obtained by showing that simplicial sets
with polynomial-time homology are closed under various operations, most
notably, Cartesian products, twisted Cartesian products, and classifying space.
One of the key components is also polynomial-time homology for the
Eilenberg--MacLane space K(Z,1), provided in another recent paper by Krcal,
Matousek, and Sergeraert.

本文介绍了一些与同伦理论有关的计算问题，包括计算拓扑空间 X 的 k 阶同伦群 π_k (X)，并根据前一篇文章结果，实现了用 k-1 连通的 Y 和 dim X<2k-1 的连续映射 X -> Y 计算 [X,Y] 所有同伦类的多项式时间算法。同时，本文也介绍了计算拓扑空间 X,k 阶同伦群 π_k (X) 和 X 的 Postnikov 系统的前 k 个阶段的算法，并提出了一个简单的扩展问题的解决方案。