Harmonious Trees

Aus Rechenkraft
Zur Navigation springen Zur Suche springen
Qsicon Ueberarbeiten.png Dieser Artikel bedarf einer Überarbeitung. Näheres dazu sollte auf der Diskussionsseite stehen. Hilf mit, ihn zu verbessern und entferne anschließend diese Markierung.
Languages Languages

Deutsch ja.gif   Deutsch •  Deutsch nein.gif   English

Beispiel eines harmonischen Baumes für n=6

Harmonious Trees ist das neueste Unterprojekt von yoyo@home.

Im Jahr 1980 haben Graham und Sloane die These einer harmonischen Beschriftung von Graphen vorgestellt. Es handelt sich hierbei um eine Form der Beschriftung, die an die der additiven Basen angelehnt ist. Im Grunde genommen gilt für einen Graphen mit e Kanten, dass die harmonische Beschriftung jedem Knoten von 0 bis e-1 eine Kennung zuweist, die sich aus der Formel der Summe modulo e aller benachbarten Knoten ergibt [1].

Diese Beschriftung ist nicht trivial, in dem Sinne, dass nicht jeder Graph auch harmonisch beschriftet werden kann. Wenn ein Graph jedoch eine harmonische Beschriftung hat, wird dieser als harmonisch bezeichnet. [2]

Graham und Sloane stellten die Vermutung an, dass jeder Baum harmonisch sein kann. Laut dieser Hypothese gilt also: für jeden Baum mit n Knoten kann jeder Knoten mit den Kennungen von 0 bis n-1 versehen werden, ohne dass eine Wiederholung vorkommt, so dass die Summe modulo (n-1) von je 2 benachbarten Knoten von 0 bis (n-2) reicht.

Gemäß Gallians dynamischer Studie zum Thema Beschriftung von Graphen [3], gibt es nur wenige Resultate für harmonische Bäume. Graham und Sloane konnten bereits beweisen, dass Raupenbäume harmonisch sind. Aldret und McKay konnten mittels eines Programmes verifizieren, dass alle Bäume mit höchstens 26 Knoten harmonisch dargestellt werden können. Vor kurzem hat Fang einen neunen Algorithmus vorgeschlagen und die Harmonizität für Bäume mit höchtens 31 Knoten nachweisen können. Eine Version dieses Algorithmuses wird in diesem Projekt verteilt.

Wir versuchen mit dem Subprojekt zu bestätigen, dass Bäume begrenzter Größe harmonisch sind. Sollten sie tatsächlich harmonisch sein, bestätigt sich unser Vertrauen in die Hypothese. Andernfalls, sollte also ein Gegenbeispiel gefunden werden, wird die Hypothese augenblicklich widerlegt und damit ein ungelöstes Problem der Graphentheorie widerlegt.