We study the existence of allocations of indivisible goods that are envy-free up to one good (EF1), under the additional constraint that each bundle needs to be connected in an underlying item graph. If the graph is a path and the utility functions are monotonic over bundles, we show the existence of EF1 allocations for at most four agents, and the existence of EF2 allocations for any number of agents; our proofs involve discrete analogues of the Stromquist's moving-knife protocol and the Su--Simmons argument based on Sperner's lemma. For identical utilities, we provide a polynomial-time algorithm that computes an EF1 allocation for any number of agents. For the case of two agents, we characterize the class of graphs that guarantee the existence of EF1 allocations as those whose biconnected components are arranged in a path; this property can be checked in linear time.

翻译：我们研究了不可分割的物品的分配情况,这些物品无嫉妒可达一种商品(EF1),这是每个捆包需要在一个基本物品图中连接的额外限制。如果图表是一个路径,而实用功能是捆包的单体函数,我们则表明在大多数四个代理商中存在EF1分配情况,在任何几个代理商中都存在EF2分配情况;我们的证据涉及斯特罗姆奎斯特移动式袖珍协议和基于Sperner Lemma的Su-Simmons论点的离散类比。对于相同的公用事业,我们提供了一种计算任何数量代理商EF1分配情况的多时算法。对于两个代理商来说,我们把保证EF1分配情况的图表类别定性为在一条路径上安排了双连接组件的图表;这种属性可以用线性时间进行检查。