Graphen < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 03:20 Sa 08.01.2005 | | Autor: | newbie |
Hm, ich hoffe das es hier auch hinpasst, jedenfalls habe ich mehrer Aufgaben, wo ich etwas sehr am Grübeln bin (k.a. ob es noch die Spätfolgen von Silvester sind).
Ersteinmal, bei uns wird der Graph jetzt als endlich, ungerichtet, schlingenfrei und ohne Mehrfachkanten betrachtet.
1.
Zeigen sie, dass die in der Vorlesung definierte Erreichbarkeitsrealtion (3 Mitstudenten konnten diese angebliche Definition nicht in ihren Aufzeichnungen finden -_-) zwischen den Knoten eines Graphen G=(E,K) eine Äquivalenzrelation auf der Menge E ist.
Hm, ok, irgendwie verwirrt mich das. Erreichtbar ist eine Ecke u bezüglich v, wenn ein Weg von v nach u existiert. Und unter Erreichbarkeitsrealtion würde ich jetzt verstehen, dass wenn ein u von v aus erreichbar ist, ich in einer z.B. einer Matrix eine eins setze, anderenfalls eine null und das eben für alle Ecken. Scheint nicht wirklich zu stimmen, aber nun soll dies eine Äuquivalenzrelation auf der Menge E (also die Menge aller Ecken des Graphen) sein... Wenn eine Ecke von einer anderen erreichbar ist, dann muss die Ecke ja mindestens den Grad eins haben, aber weiter komme ich auch nicht. Insgesamt müsste es ganz einfach sein, aber irgendwie sehe ich den Wald vor lauter Bäumen nicht...
2.
Beweisen oder widerlegen sie folgende Aussage:
In jedem Graphen mit genau zwei Ecken ungeraden Grades existiert ein Weg, der diese beiden Ecken miteinadner verbindet.
Wenn ich zwei Ecken ungeraden Grades habe, bedeutet dass sie entweder direkt miteinadner verbunden sind oder sie noch mit andern Ecken verbunden sind. Wenn sie jeweils eine Kante mit einer anderen Ecke haben, so muss diese Ecke ja laut Vorraussetzung geraden Grades sein und somit noch mindestens eine weiter Kante haben. Die nächste Ecke muss ebenfalls geraden Grades sein, weswegen sie wieder eine weitere Kante haben muss, was immer so weiter geht, bis eine Ecke geraden Grades eine Kante mit der zweiten Ecke ungeraden Grades einschließt, wodurch dann ein Weg vorhanden ist.... geht das so?
3.
Zeigen sie, dass in einem Graphen G=(E,K) die Kante k Element K genau dann eine Brücke ist, wenn k in keinem Kreis im Graphen G enthalten ist.
Eine Kante ist ja eine Brücke, dass wenn ich sie entferne, ich aus einen zusammenhängenden Komponenten zwei Komponenten erhalte. In einem Kreis hat ja jede Ecke mindestens den Grad zwei und es gibt immer zwei Wege in dem Kreis von einen zu einer anderen Ecke. Wie aber nun zeigen?
Wenn ich nun zwei nicht miteinander verbundene Komponenten habe und diese durch eine Kante verbinde, so habe ich eine Brücke, die aber nicht in einem Kreis enthalten ist. Und laut Definition gibt es ja keine andere Möglichkeit eine Brücke zu machen.
Und wenn k in keinem Kreis liegt, dann bedeutet es, dass es zumindest in einem Weg liegt, der kein Kreis ist und wenn ich bei einem Weg eine Kante wegnehme, dann entstehen auch zwei Komponenten.
Soweit so gut, aber wir formal ausdrücken?
4.
Zeigen sie, dass das Komplement jedes Graphen mit mindestens zwei Zusammenhangskomponenten zusammenhängend ist. Gilt auch die Umkehrung der Aussage? Begründen sie die Antwort.
Naja, wenn ich ein Graphen habe, der aus zwei Komponenten (die ja nicht miteinadner verbunden sind) besteht, dann ist jede Ecke mit mindestens einer anderen Ecke nicht verbunden und jede Ecke eines Komponenten ist mit jeder Ecke des anderen Komponenten nicht verbunden, wobei ja beim Komplement überalle da Kanten gesetzt werden, wo keine waren und Kanten weggenommen werden, wo welche vorher waren. Nun wird aber jede Ecke des einen Komponenten mit ebenfalls jeder Ecke des anderen Komponenten verbunden, wodurch der Graph nun zusammenhängend ist.
Die Umkehrung gilt nicht, was leicht mit einem Gegenbeispiel bewiesen ist, wenn ich z.B. ein Graph in der Form von N nehme, dann ist das Komplement Z Aber direkt begründen...
5.
Zeigen sie, dass es keinen zusammenhängenden Graphen mit n Knoten und weniger als n-1 Kanten gibt.
Naja, ein Kreis hat immer genausoviel Kanten wie Ecken (also nur der Kreis) und ein Weg hat immer eine Ecke mehr als Kanten. Ein Graph ist nur zusammenhängen, wenn mindestens ein Weg von einer beliebigen Ecke zu einer anderen beliebigen Ecke existiert. Die Summe aller Grade ist die doppelte Anzahl aller Kanten. Soweit ersteinmal meine Überlegungn, aber ich glaube da mache ich lieber später weiter...
Naja, was die anderen Aufgaben betrifft, die ich noch nicht aufliste (da ich mir noch keine allzu großen Gedanken darüber gemacht habe), da würde mich ersteinmal interessieren, was genau isomorph heißt. Hier unsere Definition:
Zwei Graphen heißen isomorph, wenn es eine Bijektion F: E [mm] \mapsto [/mm] E' gibt mit der Eigenschaft, dass für alle u,v Element E gilt: uv [mm] \in [/mm] k [mm] \Rightarrow [/mm] F(u)F(v) [mm] \in [/mm] K'
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:02 Mo 10.01.2005 | | Autor: | reneP |
Hallo,
ich habe gerade leider nur 5 minuten zeit, deswegen gebe ich dir mal die antwort auf aufgabe 1 und 2....
also wenn du prüfen sollst, ob die relation eine äquivalenzrelation ist, dann musst du gucken, ob die relation
reflexiv, symetrisch und transitiv ist.
diese begriffe solltest du in der vorlesung finden...
transitiv bedeutet z.b:
wenn a [mm] \approx [/mm] b und b [mm] \approx [/mm] c [mm] \Rightarrow [/mm] a [mm] \approx [/mm] c
das gilt offensichtlich auch für die Knoten in deinem Graphen.
Reflexiv und symmetrisch sollten ähnlich gehen. Zur not kannst du ja nochmal nachfragen.
Zu Aufgabe 2.
Guck dir doch mal an, was ein Eulergraph ist ( ein graph heißt eulersch, wenn es einen Kantenzug von v nach v gibt, der jede Kante genau einmal enhält )
Ein graph ist genau dann eulersch, wenn alle Ecken geraden grad haben. Hiermit solltest du bei aufgabe 2 weiterkommen....
viele Grüße René
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 01:02 Mi 12.01.2005 | | Autor: | newbie |
Danke für deine Antwort, aber kann es sein, dass es gestern Probleme mit dem Forum gab, bin nämlich absolut nicht reingekommen... naja, die Aufgaben habe ich bereits abgegeben, trotzdem interressiert es mich natürlich weiterhin. Das mit dem Nachweis der Äquivalenzrelation ist mir dann doch noch eingefallen, ich hab da wirklich den Wald vor lauter Bäumen nicht gesehen, was die zweite Aufgabe betrifft, so weiß ich da leider immernoch nicht so recht weiter... Ok, da zwei Ecken ungeraden Grades vorkommen, kann es kein eulerscher Graph sein und somit auch kein Kreis (also der Graph kann einen Kreis enthalten, ist aber selbst kein Kreis)... aber damit habe ich ja nicht gezeigt, dass es zwischen diesen Beiden Ecken ungeraden Grades einen Weg gibt... oder wie meinst du das?
Was mir noch eingefallen ist, wir haben in einer Definition, dass die Summe aller Grade gleich der doppelten Anzahl aller Kanten ist, wodurch folglich auch die Summe alle Grade gerade sein muss. Wären nun die beiden Ecken ungeraden Grades nicht miteinander verbunden, dann kann ich sie ja komponentenweiße betrachten. In jedem Komponenten würde immer die Summe aller Grade ungerade sein, was ja nicht möglich ist, wodurch diese beiden Komponenten miteinander verbunden sein müssen und somit ein Weg existiert... Würde das ausreichen?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:11 Mi 12.01.2005 | | Autor: | reneP |
Ok, wenn du nur 2 Knoten ungeraden Grades hast und alle anderen sind gerade, was passiert, wenn du nun eine Kante zwischen genau diese beiden Knoten einfügst? Genau, du erhälst einen Graphen, in dem alle Knoten geraden grad haben ==> Der Graph enthält einen Eulerkreis. somit können von einem Knoten aus alle anderen erreicht werden und zwar auf 2 methoden....
nimmst du jetzt die Kante wieder raus kannst du von einem der beiden Knoten immer noch auf die andere Methode den anderen Knoten erreichen.
Somit hast du gezeigt, dass es einen Weg zwischen den beiden Knoten geben muss
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:50 Mo 10.01.2005 | | Autor: | Hanno |
Hallo newbie!
> 3. Zeigen sie, dass in einem Graphen G=(E,K) die Kante k Element K genau dann eine Brücke ist, wenn k in keinem Kreis im Graphen G enthalten ist.
Deine Ideen schauen doch ganz gut aus, ich helfe dir einfach mal, das Ganze mal in ein paar Formeln zu stecken:
Zuerst zeigen wir die Hinrichtung: sei also [mm] $k\in [/mm] K$ eine Brücke, [mm] $k_1,k_2\in [/mm] E$ die zu $k$ inzidenten, adjazenten Knoten und seien [mm] $V_1,V_2\subset [/mm] V$ die Komponenten, die durch die Brücke verbunden werden. Folglich führt jeder [mm] $v_1-v_2-Pfad$ [/mm] über $k$. Folglich kann $k$ in keinem Kreis liegen, da es dann nach Definition des Kreises zwei Wege von [mm] $v_1$ [/mm] nach [mm] $v_2$ [/mm] gäbe und somit jeder [mm] $v_1-v_2-Pfad$ [/mm] durch $k$ durch Substitution von $k$ durch den zweiten Weg von [mm] $v_1$ [/mm] nach [mm] $v_2$ [/mm] (im Kreis) in einen solchen überführt werden könnte. Folglich kann $k$ in keinem Kreis liegen.
Nehmen wir nun an, dass $k$ in keinem Kreis liegt. Sei [mm] $V_1$ [/mm] die Menge der Knoten [mm] $v\in [/mm] E$, für die ein [mm] $v-k_1$ [/mm] Pfad existiert, der nicht durch [mm] $k_2$ [/mm] geht, und analog dazu [mm] $V_2$ [/mm] die Menge derjenigen Punkte [mm] $v\in [/mm] E$, für die ein [mm] $v-k_2$ [/mm] Pfad existiert, der nicht durch [mm] $k_1$ [/mm] geht. Nehmen wir an es gäbe zwei Knoten [mm] $v_1\in V_1, v_2\in V_2$, [/mm] für die ein [mm] $v_1-v_2$ [/mm] Pfad existierte, der nicht durch k ginge. Dann allerdings wäre der vereinigte Pfad [mm] $k_1-v_1-v_2-k_2$ [/mm] ein weiterer [mm] $k_1-k_2$ [/mm] Pfad, was der Definition von $k$ widerspricht. Daher werden Knoten aus [mm] $V_1$ [/mm] und [mm] $V_2$ [/mm] nur über $k$ verbunden und folglich ist $k$ eine Brücke zwischen den Komponenten [mm] $V_1$ [/mm] und [mm] $V_2$.
[/mm]
Das war hoffentlich ein weiterer Schritt zur Klärung deiner Fragen :)
Liebe Grüße,
Hanno
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 01:10 Mi 12.01.2005 | | Autor: | newbie |
Auch dir wieder ein großes Dankeschön. Ich habe es mir jetzt durchgelesen und muss sagen, dass es mir wirklich weiter geholfen hat. Es ist für mich immernoch etwas ungewohnt mathematisch zu argumentieren, anstatt es in Worte zu fassen... auf jedenfall danke für die Antwort.
|
|
|
|
