Was ist das Pebbling Spiel auf Graphen?
Pebbling ist ein kombinatorisches Spiel welches auf einem gerichteten, azyklischen Graphen gespielt wird. Das Ziel ist es, einen Stein (Englisch Pebble) auf der Senke zu platzieren.
Was das Spiel interessant macht, ist die Einschränkung, dass ein Knoten nur dann gepebbelt (mit einem Stein belegt) werden darf, falls alle seine Elternknoten gepebblet sind. Wir betrachten das klassische Pebbling Spiel bei dem man Pebbles jederzeit entfernen darf. Das Ziel besteht darin, einen Pebble auf die Senke des Graphen (in unserem Spiel der Knoten ganz rechts) zu platzieren, und dabei so wenige Pebbles wie möglich zu verwenden.
Der Graph mit dem das Spiel beginnt ist ein einfacher Pfad und benötigt bloß 2 Pebbles, drücke den Pebble! Knopf um zu sehen wie das geht.
Wettbewerb: konstruiere einen Graphen der möglichst viele Pebbles benötigt.
Am Open Campus Tag gibt es einen Wettbewerb bei dem das Ziel darin besteht einen Graphen zu konstruieren der möglichst viele Pebbles benötigt. Wenn zwei Graphen die gleiche Anzahl Pebbles benötigen, gewinnt derjenige, welcher dafür mehr Schritte benötigt.
Du kannst deinen Graphen konstruieren indem du Kanten zum Pfad hinzufügst. Klicke auf einen Knoten um zu sehen welche Kanten hinzugefügt oder entfernt werden können. Die einzige Einschränkung besteht darin, dass jeder Knoten höchstens zwei eingehende Kanten haben darf. Klicke den Pebble! Knopf um zu sehen wie viele Pebbles und wie viele Schritte dein Graph benötigt. Klicke den Einreichen Knopf um deinen Graphen einzureichen.
Die Gewinner werden um 16:30 im Mondi 2 (wo die Ausstellung ist) bekanntgegeben und der Highscore ist ab dann auch auf https://www.pebbling-game.at/highscore/ ersichtlich. Die besten fünf Einreichungen bekommen einen Preis, der bis 17:30 abgeholt werden kann.
Glossar
Ein gerichteter azyklischer Graph wird durch eine Menge an Knoten und Kanten definiert, wobei eine Kante immer von einem Knoten u zu einem anderen Knoten v führt. Dargestellt wird das so:
Man sagt dann, dass v ein Kind von u ist, und u ist ein Elternknoten von v. Der Eingangsgrad eines Knoten ist die Anzahl an Elternknoten (entspricht also der Anzahl an Kanten die zu dem Knoten führen). Der Ausgangsgrad ist die Anzahl an Kinder des Knoten (entspricht also der Anzahl an Kanten die von dem Knoten wegführen). Ein Knoten mit Eingangsgrad 0 wird Quelle genannt, ein Knoten mit Ausgangsgrad 0 Senke.
What is Graph pebbling?
Graph pebbling is a combinatorial game played on a directed acyclic graph, where the goal is to put a pebble on the sink of the graph.
What makes this task non-trivial is that you are only allowed to put a pebble on a node if all its parent nodes are pebbled. We consider the classical “black pebbling” game where you can remove pebbles at any time, and the goal is to pebble the sink using as few pebbles as possible.
The initial graph you see in the game is a path and can be pebbled with only 2 pebbles, press the Pebble! button to see how this is done.
Competition: construct a graph with high pebbling complexity?
At the Open Campus day we have a competition where the goal is to construct a graph that requires the highest number of pebbles in the black pebbling game. For two graphs that need the same number of pebbles, the graph which needs more pebbling steps is considered the winner.
You can construct your graph by adding edges to the initial graph, which is a path of length 16. Click on a node to see which edges containing this node can be added or removed. The only constraint is that the indegree of any node in the graph can be at most two. Click the Pebble! button to see how many pebbles and steps your graphs needs, and click Einreichen to submit your answer.
We will announce the winners 4.30pm in Mondi 2 (the room where the exhibition is) and the highscore can be seen from then on at https://www.pebbling-game.at/highscore/. The five best submissions win a prize and you can pick it up until 5.30pm.
Glossary
A directed acyclic graph is defined by a set of nodes and directed edges, where an edge always points from some node u to a node v and is drawn like this:
We then say that v is a child of u, and u is a parent of v. The indegree of a node is the number of its parents, the outdegree the number of its children. A node with indegree 0 is called a source, a node with outdegree 0 is called a sink.