A Graph-Grabbing Game
A Graph-Grabbing Game
复制标题
一个抓图游戏
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Bartosz Walczak
中科院分区：
文献类型：
--
作者：
Piotr Micek;Bartosz Walczak
两个玩家共享一个顶点权值为非负的连通图。它们轮流获取顶点（每个回合一个）并收集它们的权重。他们必须遵守的规则是，图形的其余部分必须在每次移动后连接起来。我们推测，第一个玩家至少可以得到偶数个顶点的树的一半权重。我们提供了一个策略让第一个玩家获得至少1/4的偶数树。此外，我们证实了细分恒星的猜想。奇偶性条件是必要的：Alice在三个顶点的路径上一无所获，所有的权值都在中间。我们怀疑存在一种普遍的奇偶性现象，即第一个玩家可以收集任何具有偶数个顶点的“足够简单”的图的大部分权重。
Two players share a connected graph with non-negative weights on the vertices. They alternately take the vertices (one in each turn) and collect their weights. The rule they have to obey is that the remaining part of the graph must be connected after each move. We conjecture that the first player can get at least half of the weight of any tree with an even number of vertices. We provide a strategy for the first player to get at least 1/4 of an even tree. Moreover, we confirm the conjecture for subdivided stars. The parity condition is necessary: Alice gets nothing on a three-vertex path with all the weight at the middle. We suspect a kind of general parity phenomenon, namely, that the first player can gather a substantial portion of the weight of any ‘simple enough’ graph with an even number of vertices.