Schweres Rätsel:

Das Problem ist auf dem üblichen Stück Papier (z.B. DIN A4) unlösbar. Es 
ginge vielleicht auf einem Möbiusband.

Bernhard

Der Graph K3,3 ist nicht planar, daher ist die Aufgabe im 
zweidimensionalen Raum nicht lösbar.

Ist nicht so schwer falls die folgenden Annahmen wahr sind:

a) Ein Haus gilt als angeschlossen falls mindestens eine Wand von der 
Leitung berührt wird
b) Leitungsführung ist auch durch die Häuser erlaubt

a) ja
b) nee

Wir in der realen Welt haben eine dritte Dimension, wo sich Leitungen 
ohne Probleme kreuzen können :)

Wieso dürfen die Häuser eigentlich kein Telefon haben?

Lösung im Anhang :D

Maik Fox schrieb:
> Der Graph K3,3 ist nicht planar, daher ist die Aufgabe im
> zweidimensionalen Raum nicht lösbar.

Wie Maik schon schreibt: K3,3 ist nicht plättbar.
Um das ganze zu untermauern:
http://de.wikipedia.org/wiki/Satz_von_Kuratowski

Die einfachste 3D- Lösung:

Blatt Papier als Rolle formen und beide Seiten nutzen.
( Dann klappt's auch mit dem Nachbarn  :)

Noch eine Lösung mit Portal

Blatt papier und Bleistift.

Versorger und Häuser aufmalen. Und erstmal soweit verbinden wie geht. 
Dann einen Via ins Papier drücken und auf der Rückseite die Verbindung 
weiterführen. Dann wieder zurück zur Vorderseite und tataa.
Staunen und Begeisterung.

K. Laus schrieb:
> Noch eine Lösung mit Portal

:) schön.

Ich hätte auch noch eine zeitgemässe Variante: Heutzutage kommt alles 
aus der Cloud. Siehe Anhang.

A. K. schrieb im Beitrag #2883373:
> Gabelungen sind in der
> Aufgabe m.E. nicht ausgeschlossen.

Ich würde schon sagen, dass sie ausgeschlossen sind.

Frank N. Stein schrieb:
> Jedes Haus muss mit jedem der Werke mit einer
> Leitung verbunden werden.

K. Laus schrieb:
> Frank N. Stein schrieb:
>> Jedes Haus muss mit jedem der Werke mit einer
>> Leitung verbunden werden.

Nja, was ist eine Leitung, inhaltlich gesehen... Bringt aber eh nix.

Man könnte das natürlich so machen, wie ein Bekannter, der keinen Platz 
für eine Stromleitung hatte, oder kein Lust zum Bohren, was auch immer. 
Eine Wasserrohr lag da aber schon. Also oben mit dem Kabel rein ins Rohr 
und unter wieder raus. ;-)

Also die handelsübliche Lösung des beschriebenen Problems

"Jedes Haus muss mit jedem der Werke mit einer Leitung verbunden werden. 
Die Leitungsführung kann direkt oder auch über jeden verschlungenen 
Umweg geführt werden. Aber: Es darf keine Leitung eine andere Leitung 
kreuzen. "

ist wie im Bild gezeigt,

und wenn der Auftraggeber nachträglich den Auftrag ändert

> b) nee

wird eben eine Leitung ein mal ganz aussen um die Erde rum gelegt, 
40000km, und dem strunzdummen Aufraggeber in Rechnung gestellt.

Denn nichtbeachtung von Grundlagen der Mathematikm und Physik werden 
eben bestraft.

Michael Bertrandt schrieb:
> wird eben eine Leitung ein mal ganz aussen um die Erde rum gelegt,
> 40000km, und dem strunzdummen Aufraggeber in Rechnung gestellt.

Dafür braucht's also die Erhöhung der EEG-Umlage... :'(

Immer noch einfach, falls folgendes gilt:

c) Die Definition von Kreuzung wird sehr eng gefasst. Falls zwei 
(gerade) Leitungen aus entgegengesetzen Richtungen kommen und sich dann 
treffen und übereinanderlaufen und innehalb der Überlagerung aufhören 
wird dass als 'nicht-kreuzend' bezeichnet.

oder

d) Die Leitungen dürfen zwar nicht durch die Häuser laufen (wer weiss 
was die Bewohner damit machen), aber durch die anderen Kraftwerke (man 
kennt sich ja).

Bernd Funk schrieb:
> Die einfachste 3D- Lösung:
>
> Blatt Papier als Rolle formen und beide Seiten nutzen.
> ( Dann klappt's auch mit dem Nachbarn  :)

Ich kann mein zweidimensionales Koordinatensystem auch als Röhre 
definieren. Auch wenn es wie drei Dimensionen aussieht, brauche ich nur 
zwei Koordinaten um alle Punkte auf der Röhre zu definieren. Die Erde 
ist auch eine Kugel, und ein schlauer Fuchs hat sie flach auf ein Papier 
gezeichnet...

[EDIT]: Man kann auf der Oberfläche jedes beliebigen dreidimensionalen 
Körpers ein zweidimensionales Koordinatensystem definieren.

be stucki schrieb:
> [EDIT]: Man kann auf der Oberfläche jedes beliebigen dreidimensionalen
> Körpers ein zweidimensionales Koordinatensystem definieren.

Nicht, wenn es sich um einen fraktalen Körper handelt. (Oder täusch ich 
mich?)

Das ist eine prima Aufgabe für ein Auto-Router-Programm!

Ich komme jetzt nicht dazu, werde es aber heute Abend mal mit
4-poligen Pinhead-Steckern und Eagle verdrahten.

MfG Paul

Paul Baumann schrieb:
> Das ist eine prima Aufgabe für ein Auto-Router-Programm!

Autorouter reagieren nicht auf Sadismus.


Bernhard

BTW Dieses Rätsel war damals (6. Klasse) für mindestens eine Woche das 
"Thema des Tages" für Pausengespräche in der Schule.

Barnyh schrob:
>Autorouter reagieren nicht auf Sadismus.

Ich habe ihn dennoch mal damit beschäftigt. Das Problem ist nur:
Ich muß mit Leitungen durch Nachbar's Keller, die der gar nicht braucht.

;-)

MfG Paul

P. M. schrieb:
> Nicht, wenn es sich um einen fraktalen Körper handelt. (Oder täusch ich
> mich?)

Ich kenn mich nicht wirklich mit fraktalen Körper aus. Die haben doch im 
Allgemeinen eine nicht ganzzahlige Dimension? (Stimmt das?) Dann wären 
sie ja nicht dreidimensional...
Obwohl die Oberfläche eines fraktalen Körpers gegen Unendlich und dessen 
Volumen gegen Null strebt, kann ich auf einen dreidimensionalen 
fraktalen Körper ein beliebiges Gitter legen. Oder irre ich mich da 
jetzt total?

Besser als auf einem fraktalen Körper liegt man gelegentlich auf
einem fragilen Körper....

;-)
MfG Paul

Auf einem Möbiusband klappts.

Hallo,
ich könnte mir vorstellen, dass man mit unendlich langen Leitungen 
zumindest beliebig nah an jedes Haus heran kommt. Vielleicht gilt ja als 
angeschlossen, wenn man für jedes beliebig kleine epsilon größer 0 im 
Umkreis des Hauses die Leitung findet.

Grüße
Flo

Ich denke, daß mein Versuch mit dem Autorouter weiter oben die 
Bedingungen
erfüllt, die gestellt waren -oder täusche ich mich?

Habe ich zu einfach gedacht, oder muß es möglichst kompliziert werden?
;-)

MfG Paul

Paul Baumann schrieb:
> Ich denke, daß mein Versuch mit dem Autorouter weiter oben die
> Bedingungen erfüllt, die gestellt waren -oder täusche ich mich?

Du täuschst dich nicht, deine Lösung erfüllt die ursprüngliche Aufgabe.

Allerdings hat Frank N. Stein die Aufgabe anfangs unvollständig gestellt
und deswegen eine weitere wichtige Bedingung nachgereicht, nachdem ihn
dumdi dum draufgestoßen hat:

dumdi dum schrieb:
> b) Leitungsführung ist auch durch die Häuser erlaubt

Frank N. Stein schrieb:
> b) nee

Mit dieser zusätzlichen Bedingung ist die Aufgabe in einer Ebene ohne
Löcher, doppeltem Boden u.ä. nicht lösbar, auch nicht mit Eagle.

Yalu schrob:
>Mit dieser zusätzlichen Bedingung ist die Aufgabe in einer Ebene ohne
>Löcher, doppeltem Boden u.ä. nicht lösbar, auch nicht mit Eagle.

Du wirst Recht haben....

Ich habe jetzt über eine Stunde herumfuhrwerken (lassen), die 
Leiterbreite
auf 50mil, damit er nicht durch die "Häuser" durchrouten kann.

mfG Paul

Durch die Häuser darfs nicht, aber durch die Werke.

Fred schrob:
>Durch die Häuser darfs nicht, aber durch die Werke.

Ich grabe jetzt keine Gräben mehr -mir tut das Kreuz weh.
Vielleicht morgen früh mit einem Minibagger...
;-)
MfG Paul

Michael Bertrandt schrieb:
> wird eben eine Leitung ein mal ganz aussen um die Erde rum gelegt,
> 40000km, und dem strunzdummen Aufraggeber in Rechnung gestellt.

Merksatz eines Unternehmers, welcher seine Brötchen mit der Erdverlegung 
von Kabeln verdient:

   "Die Meter bringen das Geld!"

Michael Bertrandt schrieb:
> Denn nichtbeachtung von Grundlagen der Mathematikm und Physik werden
> eben bestraft.

Der Rohrleger beachtet wohl eher irgendwelche Installationsnormen. 
Außerdem verlegt er clevererweise die Rohre unter der Erde und dort in 
mehreren Schichten, mit Satz von Kuratowski, Graphen und Möbiusbändern 
braucht ihr dem nicht zu kommen, der zeigt euch höchstens noch einen 
Vogel. Während die Mathematiker und Physiker noch über die Lösung 
streiten, hat der die Installation längst erledigt.

Schön, dass ich zu Eurem Zeitvertreib beitragen konnte.


Aber: Diese Aufgabenstellung ist in der Praxis (zweidimesional) nicht 
lösbar.

Frank N. Stein schrieb:
> Schön, dass ich zu Eurem Zeitvertreib beitragen konnte.
>
>
> Aber: Diese Aufgabenstellung ist in der Praxis (zweidimesional) nicht
> lösbar.

Die Praxis ist nicht 2-dimensional, du müsstest dich deshalb auf die 
Theorie beschränken. Außerdem könnte man ein Rohr durch das andere 
führen, womit wir sowieso im 3-dimensionalen sind, denn ein Rohr gibt es 
in der Ebene nicht.

Problemstellungen aus der Graphentheorie auf die Laienpraxis zu 
übertragen ist halt doch nicht so trivial, wie das der Laie denkt.

Befass dich lieber mit den Königsberger Brücken.

FrankeNstein schrob:
>Aber: Diese Aufgabenstellung ist in der Praxis (zweidimesional) nicht
>lösbar.

Nur, um auf "Nummer Sicher" zu gehen:

Es ist verboten, die Leitungen sowohl durch Häuser als auch durch Werke
zu legen? Wenn es nur die Häuser wären, dann gäbe es eine Möglichkeit.

Ein richtiger Kabelgraben-Kämpfer hat auch statt Möbiusbändern gelbe 
Bänder
mit der Aufschrift "Vorsicht Kabel!"

;-)
MfG Paul

D. I. schrieb:
> Andi $nachname schrieb:
>> Befass dich lieber mit den Königsberger Brücken.
>
> Und wenn das zu schwer wird, dann doch lieber ein paar Königsberger
> Klopse :)

Aber die sind ja noch viel schwerer, zumindest liegen sie so auf dem
Magen :)