Die Mathe-Redaktion - 12.11.2019 03:57 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte / Top 15
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
Listenpunkt? im neuen Schwätz
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 902 Gäste und 8 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 » bipartite Graphen
Druckversion
Druckversion
Autor
Universität/Hochschule J bipartite Graphen
erik92
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 09.05.2019
Mitteilungen: 167
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2019-10-19 17:13


Hallo,

ich höre dieses Semester die Vorlesung algebraische Kombinatorik und zu Beginn der Vorlesung beschäftigen wir uns gerade mit Graphen.
Im Allgemeinen finde ich hier auch vieles einleuchtend nur irritiert mich eine Aufgabe auf dem ersten Übungszettel doch sehr.
Die Aufgabe lautet  

fed-Code einblenden

Was mich hier nun zunächst irritiert ist die Eigenschaft des Graphen vollständig und bipartit zu sein.
Vollständig bedeutet, dass jeder Konten mit jedem Knoten der nicht er selbst ist durch eine Kante verbunden ist. Bipartit bedeutet nun, dass eine Kante immer nur je einen Punkt aus fed-Code einblenden
fed-Code einblenden
und einen Punkt aus fed-Code einblenden
fed-Code einblenden
verbindet. Dies müsste doch aber bedeuten, dass wenn beide Eigenschaften gegeben sind mein Graph nur maximal aus zwei Punkten bestehen kann oder? Da wenn ein dritter Punkt gegeben wäre dieser aufgrund der Vollständigkeit  durch eine Kante mit meinem ersten Punkt und durch eine weitere Kante mit meinem zweiten Punkt verbunden sein müsste, wobei Punkt 1 aus
fed-Code einblenden
und Punkt 2 aus
fed-Code einblenden
ist.
Da der Graph bipartit ist müsste mein Punkt 3 nun aus beiden Mengen sein, da er sowohl mit Punkt 1 also auch mit Punkt 2 durch je eine Kanten verbunden ist. Dies wäre aber eine Widerspruch dazu, dass die Zerlegung disjunkt ist.

Angenommen dieser Gedanke von mir ist nun richtig, dann kann es doch keine geschlossenen Wege innerhalb des Graphen geben, da nach Voraussetzung die Menge aller Kanten keine Mehrfachkanten besitzt  und man ohne Mehrfachkanten keinen geschlossenen Weg zwischen zwei Punkten erzeugen kann.

Diese Lösung sollte aber falsch sein, da mein Prof bereits angedeutet hat, dass man hier eine Formel erhalten sollte.
Kann mir jemand sagen wo mein Denkfehler liegt???



  Profil  Quote  Link auf diesen Beitrag Link
zippy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2018
Mitteilungen: 716
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2019-10-19 17:20


2019-10-19 17:13 - erik92 im Themenstart schreibt:
Kann mir jemand sagen wo mein Denkfehler liegt???

Du machst keinen Denkfehler, sondern hast ein Problem mit der deutschen Sprache: Ein "vollständig bipartiter" Graph ist nicht dasselbe wie ein Graph, der gleichzeitig vollständig und bipartit ist.



  Profil  Quote  Link auf diesen Beitrag Link
ochen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 09.03.2015
Mitteilungen: 2437
Aus: der Nähe von Schwerin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2019-10-20 16:19


Hallo,

an einer Lösung bin ich auch interessiert. Die Eigenwerte und die dazu gehörigen Eigenvektoren kann ich berechnen, aber ich kenne noch nicht den Zusammenhang mit der Anzahl aller Wege. Wahrscheinlich sollte ich nochmal darüber nachdenken.


[Verschoben aus Forum 'Strukturen und Algebra' in Forum 'Graphentheorie' von ochen]



  Profil  Quote  Link auf diesen Beitrag Link
erik92
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 09.05.2019
Mitteilungen: 167
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, vom Themenstarter, eingetragen 2019-10-21 13:17


Hallo viel weiter bin ich noch nicht gekommen. Dank des Hinweises von zippy hat sich mein Anfangsproblem gelöst. Allerdings hat sich inzwischen ein neues aufgetan:
Eine andere Aufgabe auf dem Übungsblatt war zu zeigen, dass die Eigenwerte eines bipartiten Graphen immer in Paaren auftreten, d.h. wenn a ein Eigenwert ist, dann auch -a, wobei a=0 erlaubt ist.
In der Vorlesung hatten wir gesagt, dass die Anzahl der geschlossenen Wege der Länge l in einem Graphen dadurch berechnet werden kann, dass alle Eigenwerte mit l potenziert werden und anschließend aufsummiert werden.

Wenn die Eigenwerte nun aber in Paaren auftreten, würde hier ja immer 0 rauskommenen. Dies kann aber natürlich nicht sein, was bedeutet, dass in meiner Mitschrift wohl Fehler sind. Daher versuche ich gerade durch das Betrachten verschiedener Beispiele eine Idee zu bekommen aber ich weiß nicht ob da noch viel bei rauskommt.
Falls jemand eine Idee hat, wäre ich sehr dankbar.



  Profil  Quote  Link auf diesen Beitrag Link
Fabi
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.03.2002
Mitteilungen: 4503
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2019-10-21 13:28


2019-10-21 13:17 - erik92 in Beitrag No. 3 schreibt:
Wenn die Eigenwerte nun aber in Paaren auftreten, würde hier ja immer 0 rauskommenen.

Warum?


-----------------
"There would be the mathematical equivalent of worldwide rioting." (P.C.)

Willst du Hamburg oben sehen, musst du die Tabelle drehen.



  Profil  Quote  Link auf diesen Beitrag Link
erik92
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 09.05.2019
Mitteilungen: 167
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2019-10-21 13:54


Ah stimmt dummer Denkfehler bei l ungerade ist dies natürlich nicht der Fall. Ich hatte allerdings gerade beim Mittagessen einen neuen Gedanken.

Wenn ich meine Ecken wie folgt anordne:
Die ersten s sind in E1 und die nächsten t sind in E2 dann müsste meine Adjazenmatrix doch eine mehr oder minder schöne Blockmatrix ergeben, bei der oben links eine sxs Matrix ist mit nur 0 Einträgen. Unten links eine txt Matrix mit nur 0 Einträgen und alle anderen Einträge müsste 1 sein wenn ich es mir jetzt nicht falsch überlegt hab.


Kann man damit vielleicht etwas anfangen?



  Profil  Quote  Link auf diesen Beitrag Link
erik92
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 09.05.2019
Mitteilungen: 167
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2019-10-21 15:48


fed-Code einblenden



  Profil  Quote  Link auf diesen Beitrag Link
ochen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 09.03.2015
Mitteilungen: 2437
Aus: der Nähe von Schwerin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2019-10-21 16:19


2019-10-21 13:54 - erik92 in Beitrag No. 5 schreibt:
Ah stimmt dummer Denkfehler bei l ungerade ist dies natürlich nicht der Fall. Ich hatte allerdings gerade beim Mittagessen einen neuen Gedanken.

Wenn ich meine Ecken wie folgt anordne:
Die ersten s sind in E1 und die nächsten t sind in E2 dann müsste meine Adjazenmatrix doch eine mehr oder minder schöne Blockmatrix ergeben, bei der oben links eine sxs Matrix ist mit nur 0 Einträgen. Unten links eine txt Matrix mit nur 0 Einträgen und alle anderen Einträge müsste 1 sein wenn ich es mir jetzt nicht falsch überlegt hab.


Kann man damit vielleicht etwas anfangen?

Hallo,

damit lässt sich etwas anfangen. Sei $A$ die Adjazenzmatrix von $K_{s,t}$, so gilt
\[A=\begin{bmatrix}\mathbf{0}_{s\times s} & \mathbf{1}_{s\times t}\\
\mathbf{1}_{t\times s} & \mathbf{0}_{t\times t}
\end{bmatrix}\] Wir können jetzt sehr einfach den Kern dieser Matrix ausrechnen, da es nur zwei verschiedene Zeilen gibt. Es gilt
\[ \text{ker}(A)=\text{ker}\begin{bmatrix}
\mathbf{1}_{1\times s} & \mathbf{0}_{1\times t}\\
\mathbf{0}_{1\times s} & \mathbf{1}_{1\times t}
\end{bmatrix}=\text{span}\{\mathbf{e}_1-\mathbf{e}_2,\mathbf{e}_1-\mathbf{e}_3,\ldots, \mathbf{e}_1-\mathbf{e}_s\}\oplus\text{span}\{ \mathbf{e}_{s+1}-\mathbf{e}_{s+2},\mathbf{e}_{s+1}-\mathbf{e}_{s+3}\ldots,\mathbf{e}_{s+1}-\mathbf{e}_{s+t}\}.\] Der Eigenraum zum Eigenwert $0$ ist also $(s+t-2)$-dimensional.

Kannst du mal versuchen die anderen beiden Eigenräume anzugeben? Das ist in diesem Fall nicht so schwer, da beide eindimensional sind. Du kannst sie raten. Multipliziere $A$ mit einem Vektor, dessen erste $s$ Einträge alle gleich sind und dessen letzte $t$ Einträge alle gleich sind.  

Kannst du bitte auch noch den Satz aus der Vorlesung zitieren?



  Profil  Quote  Link auf diesen Beitrag Link
erik92
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 09.05.2019
Mitteilungen: 167
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, vom Themenstarter, eingetragen 2019-10-21 16:46


Wofür genau brauchst du hier die Eigenräume?

Der Satz in der Vorlesung lautete:

fed-Code einblenden



  Profil  Quote  Link auf diesen Beitrag Link
ochen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 09.03.2015
Mitteilungen: 2437
Aus: der Nähe von Schwerin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2019-10-21 17:11


Die brauchst du gar nicht. Wie hast du aber die Eigenwerte berechnet oder weist nach, dass sie welche sind?

Die Anzahl der geschlossenen Wege der Länge $2$ ist $2st$, da die Anzahl aller Kanten genau $st$ ist und ein geschlossener Weg der Länge 2 eine auf- und abgelaufene Kante ist. Du darfst dir bei jeder Kante den Startknoten aussuchen.



  Profil  Quote  Link auf diesen Beitrag Link
erik92
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 09.05.2019
Mitteilungen: 167
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, vom Themenstarter, eingetragen 2019-10-21 17:14


Ah okay danke.

Die Eigenwerte hab ich durch wiederholtes ausprobieren gefunden. Ich hab mir von vielen verschiedenen Matrizen mit der beschriebenen Form die Eigenwerte ausrechnen lassen und habe dann versucht ein Muster zu erkennen.

Ein Beweis ist dies natürlich noch nicht allerdings ging es mir auch erstmal nur darum eine Idee zu bekommen.



  Profil  Quote  Link auf diesen Beitrag Link
ochen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 09.03.2015
Mitteilungen: 2437
Aus: der Nähe von Schwerin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, eingetragen 2019-10-21 17:43


Ok gut. Mit der Folgerung 1.8 kannst du die Eigenwerte direkt berechnen. Da die Adjazenzmatrix $A$ nur zwei verschiedene Zeilen hat, ist ihr Rang höchstens 2. Somit hat sie nur maximal zwei von Null verschiedene Eigenwerte $\lambda_1$ und $\lambda_2$. Da die es keine Schleifen gibt, gilt $\lambda_1+\lambda_2=0$. Weiter ist die Anzahl von Wegen der Länge 2 gleich $2st$. Somit erhalten wir $\lambda_1^2+\lambda_2^2=2st$. Dieses Gleichungssystem hat genau 2 Lösungen.



  Profil  Quote  Link auf diesen Beitrag Link
erik92
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 09.05.2019
Mitteilungen: 167
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, vom Themenstarter, eingetragen 2019-10-21 18:03


Ah okay das sieht ja schon ziemlich gut aus. Das Einzige, was ich nicht ganz noch vollziehen kann ist, wie du mit den c's aus der Folgerung umgegangen bist bzw. woher nimmst du das Wissen, das die Anzahl der geschlossenen Wege der Länge 2 2st ist?
Bei mir hat es darauf aufgebaut, dass ich die Eigenwerte bereits erraten habe aber bei dir sehe ich das gerade noch nicht  frown



  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 5234
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, eingetragen 2019-10-21 18:52


Hallo erik92,

2019-10-21 13:54 - erik92 in Beitrag No. 5 schreibt:
Wenn ich meine Ecken wie folgt anordne:
Die ersten s sind in E1 und die nächsten t sind in E2 dann müsste meine Adjazenmatrix doch eine mehr oder minder schöne Blockmatrix ergeben, bei der oben links eine sxs Matrix ist mit nur 0 Einträgen. Unten links eine txt Matrix mit nur 0 Einträgen und alle anderen Einträge müsste 1 sein wenn ich es mir jetzt nicht falsch überlegt hab.

Das ist nicht unbedingt so, wenn G kein vollständiger bipartiter Graph ist. Bei einem bipartiten Graphen steht oben rechts eine \(s\times t\)-Matrix A und unten links dann \(A^T\), da die Adjazenzmatrix symmetrisch ist.

Nimm nun einen Eigenwert a und einen zugehörigen Eigenvektor x. Zerlege jetzt x = (y,z), wobei y die ersten s Komponenten und z die letzten t Komponenten von x hat. Zeige dann, dass (-y,z) ein EV zum EW -a ist.



  Profil  Quote  Link auf diesen Beitrag Link
ochen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 09.03.2015
Mitteilungen: 2437
Aus: der Nähe von Schwerin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.14, eingetragen 2019-10-21 19:12


2019-10-21 18:03 - erik92 in Beitrag No. 12 schreibt:
woher nimmst du das Wissen, das die Anzahl der geschlossenen Wege der Länge 2 2st ist?
Bei mir hat es darauf aufgebaut, dass ich die Eigenwerte bereits erraten habe aber bei dir sehe ich das gerade noch nicht  :-(

Die Anzahl der geschlossenen Wege der Länge 2 bei einem einfachen Graphen ist das Doppelte der Anzahl an Kanten, da ein geschlossener Weg der Länge 2 eine doppelt abgelaufene Kante ist.



  Profil  Quote  Link auf diesen Beitrag Link
erik92
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 09.05.2019
Mitteilungen: 167
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.15, vom Themenstarter, eingetragen 2019-10-21 19:22


Ah cool. Das ist gut zu wissen. Schreib ich mir direkt mal auf vielen Dank!



  Profil  Quote  Link auf diesen Beitrag Link
erik92
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 09.05.2019
Mitteilungen: 167
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.16, vom Themenstarter, eingetragen 2019-10-22 00:19


Hallo ich habe meine Lösung nochmal aufgeschrieben. Es ist eigentlich so wie bereits oben geschrieben, ich habe lediglich noch eine kleine Fallunterscheidung am Anfang hinzugefügt. Vielen Dank für die Hilfe!
(Bitte entschuldigt meine Handschrift und die Fotoqualität)  smile








  Profil  Quote  Link auf diesen Beitrag Link
ochen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 09.03.2015
Mitteilungen: 2437
Aus: der Nähe von Schwerin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.17, eingetragen 2019-10-22 09:20


Du kannst die Anzahl der geschlossenen Wege der Länge $2m$ auch direkt berechnen. Wir kodieren jeden geschlossenen Wege indem wir die Knoten aufschreiben, die wir nacheinander ablaufen. So hat jeder geschlossene Weg der Länge $2m$, der mit einem Knoten in $E_1$ startet, die Form
\[u_1v_1u_2v_2\ldots u_mv_mu_1,\] wobei $u_i\in E_1$ und $v_i\in E_2$ sind. Für die Auswahl der $u_i$ gibt es exakt $s^m$ Möglichkeiten und für die Auswahl der $v_i$ gibt es genau $t^m$ Möglichkeiten. Insgesamt haben wir also $s^mt^m$ solche Wörter.

Für die Wege, die in $E_2$ beginnen, kannst du es analog machen.



  Profil  Quote  Link auf diesen Beitrag Link
erik92 hat die Antworten auf ihre/seine Frage gesehen.
erik92 hat selbst das Ok-Häkchen gesetzt.
Neues Thema [Neues Thema]  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-2019 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]