Matroids Matheplanet Forum Index
Moderiert von matroid
Kombinatorik & Graphentheorie » Graphentheorie » Kombinatorik-Problem Programmierung
Autor
Universität/Hochschule Kombinatorik-Problem Programmierung
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 8997
Wohnort: Westerburg
  Themenstart: 2022-04-09

Moin, ich lager dieses Problem mal aus dem Streichholzgraphen-Thread aus (siehe hier). Es geht um Folgendes: Es sollen alle Möglichkeiten gefunden werden, einen geschlossenen Ring aus n gleichseitigen Dreiecken zu bilden (der Rahmen für einen Streichholzgraphen), wobei diese Dreiecke auch innen mit einer gleichlangen Kante verbunden werden dürfen (sogenannte Rahmen-Elemente). Dabei soll es zu keinen Überschneidungen kommen. Für n=9 finden sich z.B. nur drei mögliche Rahmen. https://www.matheplanet.de/matheplanet/nuke/html/uploads/b/8038_9er_rahmen_3.png Für n=9 bleiben die möglichen Kombinationen noch übersichtlich, da nur Verbindungen von 2 Dreiecken möglich sind (2er-Elemente). Die zyklischen Permutationen wie (2,2,2,2,1)=(2,1,2,2,2) und Spiegelungen wie (2,1,2,2,1,1)=(2,1,1,2,2,1) müssen berücksichtigt werden, da es sich ja um Ringe handelt (hier mit * gekennzeichnet). Ich hoffe, mein Algorithmus wird ersichtlich. Programmiert habe ich noch nichts, denn darum geht es hier. \sourceon nameDerSprache n=9 Rahmen(1,1,1,1,1,1,1,1,1); Rahmen(2,1,1,1,1,1,1,1); Rahmen(2,2,1,1,1,1,1); Rahmen(2,2,2,1,1,1); Rahmen(2,2,2,2,1); Rahmen(2,1,2,1,1,1,1); Rahmen(2,1,2,2,1,1); Rahmen(2,1,2,2,2);* Rahmen(2,1,1,2,1,1,1); Rahmen(2,1,1,2,2,1);* Rahmen(2,1,1,1,2,1,1);* Rahmen(2,1,1,1,2,2);* Rahmen(2,1,1,1,1,2,1);* Rahmen(2,1,1,1,1,1,2);* \sourceoff Dieser Algorithmus liefert 8 verschiedene Rahmen, sagt aber noch nichts über die Überschneidungsfreiheit aus. Händisch geprüft verbleiben 3, siehe oben. Ab n=11 sind auch 3er-Elemente möglich. Und hier komme ich algorithmisch schon ins Schleudern. Vielleicht hat jemand eine Idee, wie man das programmiertechnisch angehen könnte? Die identischen Fälle, die zyklischen Permutationen betreffend, könnte man einfach nach Speichern in einer Liste aussortieren. So würde ich es machen. Gruß, Slash


   Profil

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]