Definition Weg < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:10 Mi 23.03.2011 | | Autor: | Loko |
| Aufgabe | | Darf eine Kante eine andere Kante in einem Weg überkreuzen? |
Hallo!
Ich habe nur eine kurze Frage wie genau die Definition eines Weges ist (offen oder geschlossen ist egal).
In verschiedenen Büchern steht nur die Ecken müssen paarweise verschieden sein, s.d. jede Ecke (mit Ausnahme höchstens der Anfangs- und Endecke) nur maximal einmal vorkommt.
Allerdings habe ich nirgends die Einschränkung gefunden, dass eine Kante eine andere nicht überkreuzen darf, aber trotzdem kommt dieser Fall in keiner der Beispielabbildungen vor. Ist das erlaubt?
|
|
| |
|
> Darf eine Kante eine andere Kante in einem Weg
> überkreuzen?
> Hallo!
>
> Ich habe nur eine kurze Frage wie genau die Definition
> eines Weges ist (offen oder geschlossen ist egal).
>
> In verschiedenen Büchern steht nur die Ecken müssen
> paarweise verschieden sein, s.d. jede Ecke (mit Ausnahme
> höchstens der Anfangs- und Endecke) nur maximal einmal
> vorkommt.
>
> Allerdings habe ich nirgends die Einschränkung gefunden,
> dass eine Kante eine andere nicht überkreuzen darf, aber
> trotzdem kommt dieser Fall in keiner der
> Beispielabbildungen vor. Ist das erlaubt?
Hi Loko
für den allgemeinen Graphenbegriff gibt es keine solche
Einschränkung. Betrachtet man aber speziell ebene bzw.
![[]](/images/popup.gif) planare Graphen , dann dürfen sich Kanten nicht
überkreuzen. Liegt aber eine ebene Zeichnung eines
Graphen vor, in welchem auch Überschneidungen
vorkommen, ist noch nicht von vornherein klar, dass
dieser Graph nicht "planar" ist. Erst wenn klar ist, dass
es keinen isomorphen und überschneidungsfreien
ebenen Graph geben kann, ist es mit Sicherheit ein
nicht-planarer Graph.
Auf welche Arten von Graphen sich bestimmte Aussagen
beziehen, muss deshalb klar gemacht werden.
In Bezug auf die Begriffe Weg, Pfad, Kreis, Zyklus:
http://de.wikipedia.org/wiki/Wege,_Pfade,_Zyklen_und_Kreise_in_Graphen
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:02 Mi 23.03.2011 | | Autor: | Loko |
Okidoki.. dann sollte in meinem Fall (endlich, ungerichtet, ohne Schleifen aber nichts mit planar) auch eine überschneidung erlaubt sein.
Vielen Dank :)
|
|
|
|
