Die Mathe-Redaktion - 14.11.2018 17:22 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
ListenpunktSchwätz / Top 15
ListenpunktWerde Mathe-Millionär!
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 881 Gäste und 30 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von matroid
Kombinatorik & Graphentheorie » Graphentheorie » Kanten mit verschiedenen Prioritäten
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Kanten mit verschiedenen Prioritäten
flaterik
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 20.05.2018
Mitteilungen: 9
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2018-05-21


<a href='' target=_blank>hierHallo Leute!

Ich hoffe ich bin hier richtig!?

Ich habe folgendes Problem:

Seht dazu bitte die Skizze! -->  [img]http://up.picr.de/32747953cn.jpg[/img]

Ich habe einen Areal, welches ich in mehrere Bereiche mit unterschiedlichen Prioritäten geteilt habe. Jeder Knoten ist eine Kreuzung (wie Straßenkreuzung) und jede Kante eine Straße. Prio 1 (Grün) bedeutet ich möchte diese Kante mindestens einmal, Prio 2 (Gelb) mindestens zweimal und Prio 3 (Orange) mindestens dreimal abfahren.. Die Kanten können aber auch mehr als gefordert befahren werden. Die Zahlen an den Kanten sind die Entfernungen. Einige Kanten können (maximal zwei) unterschiedliche Prioritäten besitzen.


Die zurückgelegte Strecke (Gesamtentfernung) soll minimiert werden.

Habt ihr eine Ahnung nach welchen Verfahren ich dieses Problem lösen könnte?
Gibt es vielleicht ein Graphenprogramm (online) wo ich ähnlich meiner Skizze Kanten und Knoten eintragen kann und mir die effizienteste Lösung ausgespuckt wird?

Tausend Dank schonmal!!

LG Erik wink



  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 4398
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2018-05-21


Hallo flaterik,

willkommen auf dem Matheplaneten!

Leider sehe ich keine Skizze.

Gruß
StrgAltEntf



  Profil  Quote  Link auf diesen Beitrag Link
dromedar
Senior Letzter Besuch: im letzten Quartal
Dabei seit: 26.10.2013
Mitteilungen: 5123
Aus: München
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2018-05-21


2018-05-21 00:32 - StrgAltEntf in Beitrag No. 1 schreibt:
Leider sehe ich keine Skizze.




  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 4398
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2018-05-21


Danke @dromedar, eben war der Link noch nicht da.

@flaterik: Wie oft muss eine Kante durchlaufen werden, wenn sie unterschiedliche Prioritäten besitzt?



  Profil  Quote  Link auf diesen Beitrag Link
flaterik
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 20.05.2018
Mitteilungen: 9
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2018-05-21


2018-05-21 00:44 - StrgAltEntf in Beitrag No. 3 schreibt:
Danke @dromedar, eben war der Link noch nicht da.

@flaterik: Wie oft muss eine Kante durchlaufen werden, wenn sie unterschiedliche Prioritäten besitzt?

Ja hatte die Skizze erst im nachhinein eingefügt.

Also eine Kante mit unterschiedlichen Prios sollte mindestens so oft, wie die höchste Priorität der Kante es fordert durchlaufen werden.



  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 4398
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2018-05-21


Ist ein geschlossener Kantenzug gesucht oder einer mit Anfangs- und Endknoten? Falls letzteres: Sind Anfangs- und Endknoten vorgegeben, oder darf man sich die aussuchen?



  Profil  Quote  Link auf diesen Beitrag Link
flaterik
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 20.05.2018
Mitteilungen: 9
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2018-05-21


2018-05-21 00:58 - StrgAltEntf in Beitrag No. 5 schreibt:
Ist ein geschlossener Kantenzug gesucht oder einer mit Anfangs- und Endknoten? Falls letzteres: Sind Anfangs- und Endknoten vorgegeben, oder darf man sich die aussuchen?

Es ist kein geschlossener Kantenzug gesucht. Einzig der Anfangspunkt sollte bestimmbar sein.. also es wäre schon von Vorteil, je nach Situation, vorher sagen zu können, wo man in das Areal "reinfährt". Wo man dann rauskommt  also der Endpunkt ist egal..



  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 4398
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2018-05-21


Dann noch eine Rückfrage mit der Bitte um eine ehrliche Antwort, und bitte nicht falsch verstehen:

Handelt es sich hier um ein "Real-World-Problem" oder ist dies eine Art Forschungsaufgabe für dich? Im letzeren Fall wäre es natürlich nicht okay, dir eine Lösung auf dem Silbertablett zu präsentieren.



  Profil  Quote  Link auf diesen Beitrag Link
flaterik
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 20.05.2018
Mitteilungen: 9
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, vom Themenstarter, eingetragen 2018-05-21


2018-05-21 01:29 - StrgAltEntf in Beitrag No. 7 schreibt:
Dann noch eine Rückfrage mit der Bitte um eine ehrliche Antwort, und bitte nicht falsch verstehen:

Handelt es sich hier um ein "Real-World-Problem" oder ist dies eine Art Forschungsaufgabe für dich? Im letzeren Fall wäre es natürlich nicht okay, dir eine Lösung auf dem Silbertablett zu präsentieren.

Im Rahmen eines Hochschulpraktikums soll ich diese Aufgabe lösen.. also ja ich würde sagen es ist ein reales Problem.. ;)



  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 4398
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2018-05-21


Okay, also kein Silbertablett ...  wink

Schritt 1: Produziere aus dem Graphen einen Multigraphen, indem du eine Kante, die n mal durchlaufen werden soll, durch n Kanten ersetzt. Dann reduziert sich das Problem darauf, einen Kantenzug zu finden, der jede Kante mindestens ein Mal durchläuft.

Kennst du das Konzept eulerscher Kantenzüge?




  Profil  Quote  Link auf diesen Beitrag Link
flaterik
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 20.05.2018
Mitteilungen: 9
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, vom Themenstarter, eingetragen 2018-05-21


2018-05-21 01:55 - StrgAltEntf in Beitrag No. 9 schreibt:
Okay, also kein Silbertablett ...  wink

Schritt 1: Produziere aus dem Graphen einen Multigraphen, indem du eine Kante, die n mal durchlaufen werden soll, durch n Kanten ersetzt. Dann reduziert sich das Problem darauf, einen Kantenzug zu finden, der jede Kante mindestens ein Mal durchläuft.

Kennst du das Konzept eulerscher Kantenzüge?

Super! ich denke, der Tipp mit dem Multigraphen reicht schon.. ich mach mir mal Gedanken und melde mich zurück biggrin

Vielen Dank!




  Profil  Quote  Link auf diesen Beitrag Link
flaterik
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 20.05.2018
Mitteilungen: 9
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, vom Themenstarter, eingetragen 2018-05-23


2018-05-21 02:11 - flaterik in Beitrag No. 10 schreibt:
2018-05-21 01:55 - StrgAltEntf in Beitrag No. 9 schreibt:
Okay, also kein Silbertablett ...  wink

Schritt 1: Produziere aus dem Graphen einen Multigraphen, indem du eine Kante, die n mal durchlaufen werden soll, durch n Kanten ersetzt. Dann reduziert sich das Problem darauf, einen Kantenzug zu finden, der jede Kante mindestens ein Mal durchläuft.

Kennst du das Konzept eulerscher Kantenzüge?

Super! ich denke, der Tipp mit dem Multigraphen reicht schon.. ich mach mir mal Gedanken und melde mich zurück biggrin

Vielen Dank!



Hey StrgAltEntf!

Ich hab mir über das Problem einige Gedanken gemacht und komme auch auf eine Lösung. Ich habe es nach dem Chinese Postman Problem gelöst.. und den Kostenminimalsten Eulerkreis gefunden.

Problem ist, ich weiss nicht wie ich folgende Einschränkung implementieren kann:

Solange ein Knoten kein Endknoten (äußere Knoten mit Grad 1) ist, darf der vorhergehnde Knoten nicht direkt danach nochmal abgefahren werden. Damit möchte ich ein "umdrehen" bzw. " "zurückfahren"  in der Mitte des Graphen vermeiden.
 
Hättest du eine Idee?

VG!



  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 4398
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, eingetragen 2018-05-23


Hallo flaterik,

2018-05-23 22:14 - flaterik in Beitrag No. 11 schreibt:
Solange ein Knoten kein Endknoten (äußere Knoten mit Grad 1) ist, darf der vorhergehnde Knoten nicht direkt danach nochmal abgefahren werden. Damit möchte ich ein "umdrehen" bzw. " "zurückfahren"  in der Mitte des Graphen vermeiden.

Edit: Ohne das jetzt komplett zu Ende gedacht zu haben, denke ich, dass diese Forderung eng mit der Cycle double cover conjecture zusammenhängt. Da letztere ungelöst ist, wirst du also diese Forderung vermutlich nicht realisieren können. (Ohne Gewähr.) Das war wirklich nicht zu Ende gedacht.



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 5513
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, eingetragen 2018-05-24


2018-05-23 22:14 - flaterik in Beitrag No. 11 schreibt:
Solange ein Knoten kein Endknoten (äußere Knoten mit Grad 1) ist, darf der vorhergehnde Knoten nicht direkt danach nochmal abgefahren werden. Damit möchte ich ein "umdrehen" bzw. " "zurückfahren"  in der Mitte des Graphen vermeiden.

Der kostenoptimale Eulerweg ist in Beispielen wie diesem ja bei weitem nicht eindeutig. Man kann variieren, welche Zyklen man durchläuft und in welcher Reihenfolge. Die Chancen sind hoch, dass man dabei eine Route findet, die die Anforderung erfüllt.

Ich habe das mal für den Fall "links unten rein und links in der Mitte raus" probiert und fand mit etwas Probieren eine entsprechende Lösung.

Hast Du eine (überschaubare) Anzahl an Instanzen, für die Du das Problem lösen sollst, oder willst Du einen Algorithmus entwickeln, der das für beliebige Instanzen kann?



  Profil  Quote  Link auf diesen Beitrag Link
flaterik
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 20.05.2018
Mitteilungen: 9
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.14, vom Themenstarter, eingetragen 2018-05-24


2018-05-24 12:19 - Kitaktus in Beitrag No. 13 schreibt:
2018-05-23 22:14 - flaterik in Beitrag No. 11 schreibt:
Solange ein Knoten kein Endknoten (äußere Knoten mit Grad 1) ist, darf der vorhergehnde Knoten nicht direkt danach nochmal abgefahren werden. Damit möchte ich ein "umdrehen" bzw. " "zurückfahren"  in der Mitte des Graphen vermeiden.

Der kostenoptimale Eulerweg ist in Beispielen wie diesem ja bei weitem nicht eindeutig. Man kann variieren, welche Zyklen man durchläuft und in welcher Reihenfolge. Die Chancen sind hoch, dass man dabei eine Route findet, die die Anforderung erfüllt.

Ich habe das mal für den Fall "links unten rein und links in der Mitte raus" probiert und fand mit etwas Probieren eine entsprechende Lösung.

Hast Du eine (überschaubare) Anzahl an Instanzen, für die Du das Problem lösen sollst, oder willst Du einen Algorithmus entwickeln, der das für beliebige Instanzen kann?

Anderen Graphen anderer Bereiche sind maximal um 3-4 Knoten und 7-8 Kanten größer. Ein Algorithmus wäre schon super aber wie soll ich sowas erstellen?

Bis jezt versuche ich Eulerwege durch "probieren" zu erhalten. Füge an estimmten Orten möglichst kostenminimal einfach ne neue Kante ein.. Aber ist das Mathmatisch "okay"?



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 5513
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.15, eingetragen 2018-05-24


Kostenminimale Eulerwege
------------------------
Ich gehe davon aus, dass alle Kantenlängen nichtnegativ sind.

1. Fall: Beginn und Ende eines Eulerweges sind gegeben oder ein Eulerkreis ist gesucht
a) Die Knoten am Beginn und am Ende des Eulerweges müssen einen ungeraden Kantengrad haben, alle anderen einen geraden. Bei einem Eulerkreis müssen alle Knoten einen geraden Grad haben.
b) Man zählt alle Knotengrade aus und schaut, bei welchen Knoten die Paritäten nicht passen.
c) Es bleibt eine gerade Anzahl 2k an Knoten übrig, die die "falsche" Parität haben. Das lässt sich beheben, in dem man aus diesen Knoten k Paare bildet und diese Paare jeweils durch einen kürzesten Weg verbindet. Die Kanten auf diesen Wegen kommen zu den bereits vorhandenen Multikanten noch dazu.
d) Das Du den jeweils kürzesten Weg zwischen zwei Knoten findest, setze ich mal voraus. Welchen Knoten man mit welchem verbindet, das ist ein Zuordnungsproblem. Bei Instanzen dieser Größe kann man das noch relativ gut von Hand lösen.

Ich demonstriere das mal für den Fall eines Eulerkreises.
Ich benenne die Knoten von oben nach unten und von links nach rechts mit den Nummern 1 bis 16. Die Knoten 1, 3, 7, 8 und 13 sind Blätter (haben also nur einen Nachbarn).
Einen ungeraden Kantengrad haben die Knoten 2, 3, 4, 5, 6, 7, 8, 9, 10, 13, 14 und 15.
Jetzt suchen wir sechs möglichst billige Wege, die je zwei dieser Knoten verbinden.
Bei einem Blatt hat der dort ausgehende Weg nur eine einzige Möglichkeit und ähnlich ist es beim Knoten 2, dessen Weg nur nach unten gehen kann.
Ich ergänze also die Kanten 3-4, 7-4, 8-9, 13-14 und 2-6. Bei einigen Knoten ist damit ein gerader Grad erreicht, bei anderen noch nicht.

Einen ungeraden Kantengrad haben jetzt noch die Knoten 4, 5, 10, und 15.
Die Kante von 4 aus, muss nach 5 verlaufen und damit ist klar, dass noch die Kanten 15-14 und 14-10 benötigt werden.
In dem entstandenen Multigraphen hat jetzt jeder Knoten einen geraden Grad und es gibt daher einen Eulerkreis.

Deine Zusatzbedingung lässt sich hier nicht einhalten. Der Knoten 2 hat zwei Kanten zum Knoten 1, aber vier Kanten zum Knoten 6. Daher gibt es zwangsläufig irgendwann auf der Rundreise die Knotenabfolge 6-2-6.

Ansonsten wäre eine mögliche Lösung:
1-2-6-5-4-3-4-7-4-5-9-8-9-10-6-2-6-5-9-10-14-13-14-15-16-12-11-15-14-10-9-8-9-5-6-10-14-13-14-15-16-12-11-15-14-10-6-2-1


2. Fall: Beginn und Ende eines Eulerweges sind _nicht_ gegeben (a) oder es ist zwar der Beginn gegeben, aber nicht das Ende (b).
Dieser Fall ist etwas schwieriger. Bei b) darf man sich einen der Knoten mit ungeradem Grad aussuchen, dessen Parität nicht ausgeglichen wird, bei a) sind es sogar zwei.
Im Beispiel würden sich die Knoten 13 und 10 anbieten (es entfallen die zusätzlichen Kanten 13-14 und 14-10) mit 13 und 8 ginge es aber auch.
Hier fällt die Lösung von Hand etwas schwerer, weil es weniger Kanten gibt, die man "offensichtlich" dazu nehmen muss, weil sie z.B. ein Blatt mit dem Rest verbinden. Es könnte ja sein, dass man in diesem Blatt gerade mit dem Weg beginnt oder endet.



  Profil  Quote  Link auf diesen Beitrag Link
flaterik hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


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-2018 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. 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]