bipartite Graphen |
| 27.01.2007, 17:24 | Dani123 | Auf diesen Beitrag antworten » | ||
| bipartite Graphen ich soll angeben für welche n,m Element N der vollständige bipartite Graph K(n,m) ein Baum oder ein Hamiltonscher Kreis ist. Ich weiss nicht ob das alles ist, aber für m=n-1 ist das doch ein baum mit m+n Knoten und n*m Kanten? |
||||
| 27.01.2007, 17:36 | Dual Space | Auf diesen Beitrag antworten » | ||
| RE: bipartite Graphen Hast du es schon im Informatikerboard versucht? |
||||
| 27.01.2007, 17:53 | Abakus | Auf diesen Beitrag antworten » | ||
RE: bipartite Graphen
ZB m := 3, also n = 2. Dann besitzt K(2, 3) mindestens einen Kreis mit 4 Ecken (der Graph ist demnach kein Baum). Grüße Abakus 
|
||||
| 27.01.2007, 18:03 | Dani123 | Auf diesen Beitrag antworten » | ||
Hab im Info. Board nix gefunden.. Naja das mit dem m=n-1 stand im wikipedia so...war mir irgendwie klar das das nich aussreicht.. |
||||
| 27.01.2007, 18:12 | Abakus | Auf diesen Beitrag antworten » | ||
Wo denn ? Wenn du in jeder der beiden Eckenmengen zumindest 2 Ecken hast, kriegst du auf die Art immer einen Kreis. Damit müsstest du die Bäume unter den vollständig bipartiten Graphen charakterisieren können. Grüße Abakus
EDIT: Text |
||||
| 27.01.2007, 18:16 | Dani123 | Auf diesen Beitrag antworten » | ||
Also wie jetzt... ich dachte wenn ein graph ein kreis besitzt kann es kein baum sein?? hier steht was ein baum ist: http://de.wikipedia.org/wiki/Baum_%28Graphentheorie%29 |
||||
| Anzeige | ||||
|
|
||||
| 27.01.2007, 18:27 | Abakus | Auf diesen Beitrag antworten » | ||
OK, da verwechselst du was: - ein Baum mit n Ecken hat n-1 Kanten (n und m bezeichnen hier die Ecken- bzw. Kantenanzahl) - ein vollständig bipartiter Graph K(n, m) besteht aus 2 Eckenmengen mit jeweils n bzw. m Ecken und hat max. viele Kanten (d.h. K(n, m) hat n+m Ecken und n*m Kanten) Und ja, Bäume besitzen keine Kreise. Wenn du alle vollständig bipartiten Graphen kennst, die Kreise besitzen, kennst du auch die, die keine Kreise besitzen. Grüße Abakus
|
||||
| 27.01.2007, 18:56 | Dani123 | Auf diesen Beitrag antworten » | ||
hmm ok, ich versuchs mal mit einem Beispiel: Knotenmenge A,B mit A={a,b}; |A|=2=m B={c,d,e}; |B|=3=n ein vollständiger bipartiter Graph hat dann die Kantenmeng K(m,n)={(a,c),(a,d),(a,e),(b,c),(b,d),(b,e)}=m*n=6 das is doch richtig oder? Da aber doch gilt, das jedes Paar (a,b) für alle a element A und b element B, zur Kantenmenge gehört, gibt es doch garkeine kreise, nur wenns auch die Paare(b,a) gibt oder?? |
||||
| 27.01.2007, 19:20 | Abakus | Auf diesen Beitrag antworten » | ||
Kanten gehören zu nicht-orientierten Graphen. (In orientierten Graphen sind das Pfeile.) Die Kanten (a, b) und (b, a) sind demnach dieselben. Grüße Abakus
|
||||
| 27.01.2007, 19:30 | Dani123 | Auf diesen Beitrag antworten » | ||
bei wiki. is aber immer die rede von Kanten, ich bin verwirrt, aber total |
||||
| 27.01.2007, 19:50 | Abakus | Auf diesen Beitrag antworten » | ||
OK, die Sprechweise gibt es dann auch: genauer wäre hier von gerichteten Kanten zu reden. Bei dieser Aufgabe solltest du aber wissen, ob die vorkommenden Graphen gerichtet oder ungerichtet sein sollen (ich gehe von ungerichtet aus). Grüße Abakus
|
||||
| 27.01.2007, 20:05 | Dani123 | Auf diesen Beitrag antworten » | ||
naja steht nich explizit da... okay, also ich glaub ein kreis muss min. aus 3 kanten (also geht ja von a nach c, von c nach a nicht) bestehen. in meinem Beispiel gibts somit die kreise. (a,c,b,d,a)....von a nach c, von c nach b, von b nach d, von d nach a (a,d,b,c,a) (a,e,b,c,a)... oder?? |
||||
| 27.01.2007, 20:20 | Abakus | Auf diesen Beitrag antworten » | ||
Ja, richtig. Solche Kreise findest du dann in jedem bipartiten Graphen, vorausgesetzt du hast mindestens 2 Knoten auf jeder Seite. Grüße Abakus
|
||||
| 27.01.2007, 20:41 | Dani123 | Auf diesen Beitrag antworten » | ||
so jetzt hast du gesagt, wenn wir alle graphen kennen die kreise sind, dann kennen wir auch alle die keine sind und das sind dann die bäume.. ja hmm und schon ist wieder vorbei, denn nur wenn eine knotenmenge 0 oder nur 1 knoten beinhaltet, dann gibt es keine kreise? |
||||
| 27.01.2007, 20:51 | Abakus | Auf diesen Beitrag antworten » | ||
Ja (wobei vollständig bipartit immer vorausgesetzt ist). D.h. die Bäume sind in dem Fall Graphen des Typs K(1, m), K(n, 1). Wenn n oder m gleich 0 ist, fehlt für einen Baum der Zusammenhang. Grüße Abakus
|
||||
| 27.01.2007, 21:24 | Dani123 | Auf diesen Beitrag antworten » | ||
ok gut
Jetzt zu dem Hamiltonschen Kreis (also wo der Kreis jeden Knoten einmal besucht): Dazu muss n und m min. 2 sein, sonst wärs ja wieder ein baum. Naja und weiss nicht komm irgendwie darauf das gelten muss, das die Anzahl der Knoten die der kreis durchläuft bei (n-1)+m oder umgekehrt sein muss?? |
||||
| 27.01.2007, 21:36 | Abakus | Auf diesen Beitrag antworten » | ||
Vergleiche einmal n und m. Wenn du dich im Graph bewegst, springst du ja von einem Knoten der einen Knotenmenge zu einem Knoten der anderen Knotenmenge. Wenn du jetzt auf einem Weg jeden Knoten genau einmal besuchst, lässt das Schlüsse auf n und m zu. Grüße Abakus
|
||||
| 27.01.2007, 21:49 | Dani123 | Auf diesen Beitrag antworten » | ||
Ja hab ich eigentlich gemacht, aber mit nem fehler.. also m und n muss gleich sein, damit jeder knoten einmal erreicht wird |
||||
| 27.01.2007, 21:55 | Abakus | Auf diesen Beitrag antworten » | ||
Genau, jetzt hast du es 
Grüße Abakus
|
||||
| 27.01.2007, 22:22 | Dani123 | Auf diesen Beitrag antworten » | ||
Juuchuu 
jetzt muss ich noch ne Formel angeben für die Anzahl aller Hamiltonschen Kreise in einem Hamiltonschen K(n,m). Hab mir das so überlegt. Da ja n=m ist es egal auf welcher seite man anfängt. Ich fange bei n an und wähle 1 knoten aus n Knoten also (n über 1) Möglichkeiten, dann wähle ich 1 Knoten aus m Knoten von der anderen seite, also (m über 1). Beim nächsten mal wird 1 Knoten aus n-1 Knoten gewält (n-1 über 1) usw.. Da ja n=m, wähle ich t=n=m somit ist die Formel ?? |
||||
| 28.01.2007, 00:19 | Dani123 | Auf diesen Beitrag antworten » | ||
hmm ne stimmt nich 
|
||||
| 28.01.2007, 00:44 | Abakus | Auf diesen Beitrag antworten » | ||
Deine Idee geht schon in die richtige Richtung. Betrachte einmal Wege des Typs: Die a's sind Knoten aus der einen Knotenmenge, die b's stammen aus der anderen. Untereinander kannst du die a's permutieren, ebenso kannst du das mit den b's. Um nicht alle Wege mehrfach zu zählen, könntest du zB den Startknoten fest wählen (oder du überlegst, wie oft du einen Weg jeweils gezählt hast). Grüße Abakus
|
||||
| 28.01.2007, 13:03 | Dani123 | Auf diesen Beitrag antworten » | ||
hmm versteh ich zwar grad nicht, aber is ja noch früh am morgen.. also ich hab n^2 wege die ich immer wählen kann. leg ich ein startpunkt fest (z.b. a1) dann hab ich nur noch n wege zum wählen. Hab ich ein weg gewählt, dann hab ich beim nächsten mal nur noch n-1 wege zur auswahl. ich glaub das wird zu kompliziert..mist |
||||
| 28.01.2007, 19:15 | Abakus | Auf diesen Beitrag antworten » | ||
Das Stichwort lautet Permutationen. Diese bilden die Symmetrische Gruppe auf n Elementen (da steht auch die Anzahl der Elemente davon). Nun musst du das in den Kontext einordnen (lies noch mal oben). Du kannst sowohl die a's als auch die b's untereinander permutieren, wobei du aber zB fest wählen solltest (das vermeidet die Mehrfachzählung von Wegen). Also bleiben (n-1) Knoten der einen Menge und n Knoten der anderen Menge, die du jeweils untereinander permutieren kannst. Grüße Abakus
|
||||
| 29.01.2007, 09:17 | Dani123 | Auf diesen Beitrag antworten » | ||
naja genau auf der einen seite hab ich doch dann (n-1)! Permutationen und auf der anderen Seite n! aber zusammengerechnet haut das wieder nicht hin |
||||
| 29.01.2007, 09:49 | Dani123 | Auf diesen Beitrag antworten » | ||
wobei ich denke das n!*n! = (n!)^2 stimmen müsste oder? |
||||
| 29.01.2007, 11:18 | Abakus | Auf diesen Beitrag antworten » | ||
Wenn du nur die Knotenreihenfolge beachtest, kommst du auf . (Hier spielen die Anfangspunkte der Kreise keine Rolle, nur die Reihenfolge der Knoten.) Du musst also schauen, wie ihr solche Wege definiert habt und ob der Anfangspunkt eine Rolle spielen soll. Wenn du die Reihenfolge beachten willst, kann jeder Knoten eines Weges als erster Knoten gewählt werden, d.h. die Anzahl der Möglichkeiten multipliziert sich noch mit 2n. Grüße Abakus
EDIT: bei 2*2 Knoten gibt es 2 Kreise (nur Knotenreihenfolgen hier), bei 3*3 Knoten gibt es 12 Kreise; am Besten testet man die Formel mal aus... |
||||
| 29.01.2007, 11:31 | Dani123 | Auf diesen Beitrag antworten » | ||
ja hmm, keine ahnung wie es definiert is, geht aus den unterlagen nicht hervor und aus der aufgabe auch nicht. aber wir können ja das Beispiel nehmen: Knoten Menge A={a,b} und Knotenmenge B={c,d} in einem bipartiten Graph. Es gibt folgende Hamiltonsche Kreise: 1: a-c-b-d 2: a-d-b-c 3: b-c-a-d 4: b-d-a-c dreht man den 3. kreis, kommt man auf a-d-b-c = 2 Kreis dreht man den 4. kreis, kommt man auf a-c-b-d = 1 Kreis somit entstehen 2 verschieden Hamiltonsche Kreise, für m=n=2 nach deiner Formel wären das doch nur ein Kreis, da du noch durch 2 rechnest, aber das macht doch schon (n-1)! oder? Also stimmt doch (n-1)!*n!. |
||||
| 29.01.2007, 11:40 | Abakus | Auf diesen Beitrag antworten » | ||
Korrekt, ich habs oben bereits editiert gehabt. Für n = 2, 3 muss man sich die Kreise wirklich mal hinzeichnen. Und du rechnest die "Drehungen" ja raus, demnach kommt es dir nicht auf den Anfangspunkt an. Grüße Abakus
|
||||
| 29.01.2007, 12:01 | Dani123 | Auf diesen Beitrag antworten » | ||
okay danke
wobei ich aber nicht weiss ob man die drehung rausrechnen soll oder nicht... |
||||
| 29.01.2007, 12:13 | Abakus | Auf diesen Beitrag antworten » | ||
Also das mit dem Faktor 2 ist auch noch kritisch, sehe ich gerade: die 2 Wege, die du beim (2+2)-Graphen hast sind genau invers zueinander, d.h. du hast "nur" 2 verschiedene Durchlaufrichtungen. Das sollten wir auch noch berücksichtigen. Grüße Abakus
EDIT: dann müsste noch alles durch 2 geteilt werden |
||||
| 29.01.2007, 12:16 | Dani123 | Auf diesen Beitrag antworten » | ||
ja aber beim 3x3 graph funktionierts anscheinend ja auch. |
||||
| 29.01.2007, 13:16 | Abakus | Auf diesen Beitrag antworten » | ||
Also wir haben 3 Ergebnisse, ich fasse zusammen: - betrachten wir Wege mit verschiedenen Anfangsknoten als verschieden, so haben wir viele Hamilton-Kreise. - ist uns nur die Reihenfolge der Knoten wichtig, so kommen wir auf viele Hamilton-Kreise. - ist uns auch noch die Orientierung (bzw. Durchlaufrichtung) egal, erhalten wir viele Hamilton-Kreise. Es hängt also von der genauen Definition ab, wie man so einen Kreis definiert. Ggf. hängt das wiederum von dem Problem ab, an dem man arbeitet und welche Kreise einem interessieren. Wichtig ist jedenfalls bei den Formeln, zu wissen, was genau gezählt wird und welche Kreise identifiziert werden. In Wiki siehe hier: Hamilton-Kreis, Wege/Pfade/Zyklen Grüße Abakus
|
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
