Isomorphe Teilgraphen zu einem vollständigen Graphen

02.12.2016, 21:10	MUneu	Auf diesen Beitrag antworten »
Isomorphe Teilgraphen zu einem vollständigen Graphen Moin moin, ich hänge gerade an einer Hausaufgabe fest. Es geht dabei um einen vollständigen Graphen G mit 10 Knoten. Die Aufgaben dazu lauten: 1.) Wie viele Kanten hat der Graph G? 2.) Wie viele verschiedene Kreise der länge 3 hat der Graph G? 3.) Wie viele verschiedene Teilgraphen hat der Graph G, die isomorph zu dem folgenden Graphen sind? Der Graph zu Aufgabe 3: [attach]43166[/attach] Zu 1: Es gilt ja $\begin{eqnarray} \sum\limits_{v \in V}^{} d(v) = 2 \| E \| \end{eqnarray}$ . Also kann man das für die Kanten umstellen und erhält für die Aufgabe 1: $\begin{eqnarray} (910)1/2 = 45 \end{eqnarray}$ Zu 2: Dort bin ich mir nicht sicher. Im Internet habe ich eine Formel dazu gefunden: $\begin{eqnarray} \frac{ n! }{ (n-l)!2l } \end{eqnarray}$ wobei $\begin{eqnarray} l \end{eqnarray}$ die Kreis Länge ist und $\begin{eqnarray} n \end{eqnarray}$ die Knoten des Kreises. Ob man diese Formel nun so anwenden kann und wie man auf sie kommt weiß ich nicht. Intuitiv hätte ich jetzt einfach gesagt $\begin{eqnarray} \begin{pmatrix} 10 \\ 3 \end{pmatrix} = 120 \end{eqnarray}$ . Bei beiden Formel kommt jetzt allerdings dasselbe raus, weshalb ich mir nicht sicher bin welche von beiden die richtige, oder ob überhaupt eine die richtige ist. Zu 3: Ich hätte jetzt gedacht, dass sich diese Aufgabe aus dem Teil 1 und 2 zusammensetzt. Also eine 4-elementige Teilmenge aus der 10-elementigen Menge. Sprich der Binomialkoeffizient wie in Aufgabe 2 nur jetzt mit einer 4-elementigen Teilmenge. Da nun aber noch die Kante von (3,2) bzw. (2,3) berücksichtigt werden muss, wären dass nach meiner Überlegung $\begin{eqnarray} \begin{pmatrix} 10 \\ 4 \end{pmatrix} 2 = 420 \end{eqnarray}$ . Wie bereits erwähnt bin ich mir bei meinen Lösungen nicht sicher und wäre dankbar für Verbesserungen und auch Erklärungen, am besten Erklärungen die Jeder verstehen kann
03.12.2016, 09:08	Huggy	Auf diesen Beitrag antworten »
RE: Isomorphe Teilgraphen zu einem vollständigen Graphen 1) und 2) sind richtig. Da der Graph vollständig ist, sind je 2 beliebige Ecken durch eine Kante verbunden und je 3 beliebige Ecken bilden einen Kreis. Die Zahl der Möglichkeiten ergibt sich daher aus der Zahl Möglichkeiten, 2 bzw. 3 Ecken aus den 10 Ecken auszuwählen, was auf die entsprechenden Binomialkoeffzienten führt. 3) Schau dir den Teilgraphen noch mal an. Kann ein solcher Teilgraph in einem vollständigen Graphen enthalten sein?
03.12.2016, 14:15	MUneu	Auf diesen Beitrag antworten »
3.) Naja, es wäre "nur" ein Teilgraph, aber kein induzierter Teilgraph. Oder?
03.12.2016, 14:45	Huggy	Auf diesen Beitrag antworten »
Mit der Terminologie kenne ich mich nicht aus. Ich habe angenommen, ein Teilgraph ist eine Teilmenge der Ecken des Graphen einschließlich aller diese Teilmenge verbindenden Kanten. Ist das anders gemeint?
03.12.2016, 22:43	MUneu	Auf diesen Beitrag antworten »
Folgende Definition hatten wir für Teilgraphen in der Vorlesung: Sei $\begin{eqnarray} G = (V, E) \end{eqnarray}$ ein Graph. Ein Graph H ist ein Teilgraph, falls $\begin{eqnarray} V(H) \subseteq V \end{eqnarray}$ und $\begin{eqnarray} E(H) \subseteq E \end{eqnarray}$ und wir schreiben dann $\begin{eqnarray} H \subseteq G \end{eqnarray}$ . Ein Teilgraph $\begin{eqnarray} H = (U, E_{H} ) \end{eqnarray}$ von G heißt induziert, falls zusätzlich gilt $\begin{eqnarray} E_{H} = \left\{ e \in E: e \subseteq U \right\} \end{eqnarray}$ , d.h. H enthält alle Kanten von G die durch die in $\begin{eqnarray} U \subseteq V \end{eqnarray}$ enthalten sind. Wir schreiben dann auch $\begin{eqnarray} H = G\left[U\right] \end{eqnarray}$ . Also im Tutorium wurde so etwas erwähnt wie, dass man zu nächst die Kante von (3,2) bzw. (2,3) vernachlässigen soll und erste einmal gucken soll wie viele isomorphe Graphen es für diesen Teilgraphen gibt und dann die Kante in der Mitte extra behandelt, weshalb ich so bei Aufgabe 3 vorgegangen bin. Ich bin mir nun aber nicht sicher, ob ich es nach diesem Tipp richtig behandelt habe.
04.12.2016, 08:46	Huggy	Auf diesen Beitrag antworten »
Mit dieser Definition ist dein Ansatz richtig, seine Ausführung im zweiten Teil aber nicht. Beachte, wenn man aus einem vollständigen Graphen mit 4 Ecken eine beliebige Kante entfernt, so sind die entstehenden Graphen alle isomorph zueinander. Wenn du bei dem von dir gezeichneten Graphen die Kante (1, 2) statt der Kante (1, 3) entfernst, sieht der Graph zwar optisch anders aus, aber man kann ihn so umzeichnen, dass man die Isomorphie auch optisch sieht.
Anzeige

04.12.2016, 16:50	MUneu	Auf diesen Beitrag antworten »
Das alle Graphen mit 4 Knoten (Ecken) isomorph zu diesem wären ist mir klar. Man könnte ja auch sagen, wenn man die Kante (3,2) bzw. (2,3) rauslässt, dass der Teilgraph einen Kreis der Länge 4 im Graphen G abbildet. Nur was mir das Hilft weiß ich nicht so richtig. Man kann ja sehen, dass es für den Teilgraphen nur 2 Möglichkeiten gibt, die Kante (3,2) bzw. (2,3) anders zusetzen. Und das wäre eben die besagte (3,2) Kante oder die gespiegelte Kante (1,4). Nur wie kann ich das jetzt verrechnen und komme auf die verschiedene Teilgraphen die der Graph G hat die isomorph zu dem gezeichneten Graphen sind. Wichtig ist ja auch das sie verschieden sind. Ich habe da einfach gerade ein Brett vorm Kopf. Es ist bestimmt super einfach und logisch, wenn man einmal die Lösung hat. Ich wäre für jeden Tipp bzw. Denkanstoß dankbar.
05.12.2016, 08:40	Huggy	Auf diesen Beitrag antworten »
Die Sache ist doch einfach. Zunächst werden aus dem Ausgangsgraphen 4 beliebige Ecken einschließlich aller sie vebindender Kanten entnommen. Das ergibt den schon von dir genannten Faktor $\begin{eqnarray} \binom {10} 4 \end{eqnarray}$ Dieser Teilgraph hat 6 Kanten. Von diesen kann eine beliebige entfernt werden und man enthält einen zu dem gezeichneten isomorphen Graphen. Der Binomialkoeffizient ist also noch mit 6 zu multiplizieren.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »