[Graphentheorie] pebbling Graph - was bedeutet x-pebbled

Neue Frage »

MatheN00bine Auf diesen Beitrag antworten »
[Graphentheorie] pebbling Graph - was bedeutet x-pebbled
Hallo, ich beschäftige mich gerade mit pebbling Graphs, eine Art mathematischem Spiel bei dem man in einem Graphen mit n Knoten eine beliebige Anzahl pebbles (Kieselsteine) verteilt und dann jeweils zwei pebbles wegnehmen darf und einen auf einen benachbarten Knoten. Interessant ist dann ob Anzahlen an pebbles existieren, so dass ich immer einen pebble auf einen bestimmten Knoten v legen kann mit dieser Methode...

Dazu lese ich gerade einen Artikel von David Moews, der hier einzusehen ist: https://www.sciencedirect.com/science/ar...09589569290043W

Ich habe auf der dritten Seite des pdfs folgende Definition nicht ganz verstanden:

If G is a digraph and v is a vertex of G, we say (G,v) can be -pebbled if
1. g 1, if p g, then g pebbles can be moved to v
2. g 2, if p + q g, then g pebbles can be moved to v

p is the total number of pebbles on G and q the number of vertices of G with an odd number of pebbles.


Ich verstehe folgendes: Wir haben einen gerichteten Graphen G, p ist die Gesamtzahl an Steinen auf G und q die Anzahl der Knoten, die eine ungerade Anzahl Steine hat. Das g beschreibt dann wieviele Steine auf den speziellen Knoten v gelegt werden können. Bedeutet das alpha nun irgendwas? Ist das alpha überhaupt eine ganze Zahl? Ich weiss noch, dass wenn es alpha-pebble-bar ist, dass dann das alpha größergleich der kleinste Anzahl Steine ist, die auf G liegen können, so dass immer ein Stein auf den Knoten v gelegt werden kann...
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »