beweisaufgabe

27.04.2010, 15:02

gzm

beweisaufgabe

hallo..

ich muss folgendes beweisen, weiß aber leider nicht wie unglücklich

kann mir bitte jmd. behilflich sein?

Aufgabe:

Zeige: In jeder Gruppe aus 6 Menschen gibt es eine Dreiergruppe, in der die Personen einander
kennen, oder eine Dreiergruppe, in der die Personen einander nicht kennen.

27.04.2010, 15:21

WebFritzi

Auf diesen Beitrag antworten »

Wenn Person A die Person B kennt, kennt dann auch Person B Person A?

27.04.2010, 15:37

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von WebFritzi
Wenn Person A die Person B kennt, kennt dann auch Person B Person A?

Für das "einander kennen" im Sinne der Aufgabenstellung ist die Antwort ja...

27.04.2010, 15:45

WebFritzi

Auf diesen Beitrag antworten »

Nein, so kann man das nicht behaupten. Die Aufgabe ist nicht korrekt gestellt. In der Aufgabe werden nur Pärchen behandelt, die einander kennen. Das schließt aber nicht aus, dass es Pärchen gibt, bei denen der eine den anderen, nicht aber der andere den einen kennt.

Ich denke, dass dies ausgeschlossen sein soll. Aber das wird es eben nicht.

27.04.2010, 15:54

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von WebFritzi
Ich denke, dass dies ausgeschlossen sein soll. Aber das wird es eben nicht.

Das wird nicht ausgeschlossen, das ist richtig, ist aber andererseits in Hinblick auf die Behauptung auch unerheblich...

Man betrachtet hier einfach den (ungerichteten) Graphen G, dessen Knoten die 6 Leute sind, wobei genau dann eine Kante von Knoten A zu Knoten B führt, wenn A und B einander gegenseitig kennen...Knoten, bei denen sich die zugehörigen Personen nur einseitig oder gar nicht kennen bleiben unverbunden... Die Behauptung ist dann, dass entweder $\begin{eqnarray*} G \end{eqnarray*}$ selbst oder sein Komplementgraph $\begin{eqnarray*} \bar{G} \end{eqnarray*}$ den vollständigen Graphen $\begin{eqnarray*} K_3 \end{eqnarray*}$ als Teilgraphen enthält...

27.04.2010, 17:19

WebFritzi

Auf diesen Beitrag antworten »

Zitat:

Original von Mystic

Zitat:

Original von WebFritzi
Ich denke, dass dies ausgeschlossen sein soll. Aber das wird es eben nicht.

Das wird nicht ausgeschlossen, das ist richtig, ist aber andererseits in Hinblick auf die Behauptung auch unerheblich...

Erm..... Jop. smile

<- ich über mich Augenzwinkern

27.04.2010, 18:29

gzm

Auf diesen Beitrag antworten »

danke an euch alle dass ihr mir geantwortet habt smile

aber leider verstehe ich immer noch nicht wie ich die aufgabe lösen soll unglücklich

könnte es mir jmd. nochmal erklären?

27.04.2010, 18:58

Mystic

Auf diesen Beitrag antworten »

Mit den oben von mir eingeführten Bezeichnungen solltest du versuchen, das Folgende zu zeigen bzw. dir zu überlegen:

1. Entweder $\begin{eqnarray*} G \end{eqnarray*}$ oder $\begin{eqnarray*} \bar G \end{eqnarray*}$ enthält einen Knoten mit Grad mindestens 3.

Im Folgenden wird o.B.d.A. angenommen, dass dies für $\begin{eqnarray*} G \end{eqnarray*}$ selbst zutrifft. (Beachte, dass die Behauptung vollkommen symmetrisch in Bezug auf $\begin{eqnarray*} G \end{eqnarray*}$ und $\begin{eqnarray*} \bar G \end{eqnarray*}$ ist, sodass wir uns einen dieser beiden Graphen für den Beweis aussuchen dürfen!) Es gibt also dann einen Knoten $\begin{eqnarray*} A \end{eqnarray*}$ in $\begin{eqnarray*} G \end{eqnarray*}$ , der mit drei anderen Knoten $\begin{eqnarray*} X,Y,Z \end{eqnarray*}$ verbunden ist.

2. Wenn dann beispielsweise $\begin{eqnarray*} X \end{eqnarray*}$ mit $\begin{eqnarray*} Y \end{eqnarray*}$ verbunden ist, was könnten wir daraus schließen in Hinblick auf die Behauptung?

3. Wenn keine zwei der drei Knoten $\begin{eqnarray*} X,Y,Z \end{eqnarray*}$ miteinander verbunden sind, was könnten wir dann daraus schließen in Hinblick auf die Behauptung?

27.04.2010, 19:11

gzm

Auf diesen Beitrag antworten »

danke für deine antwort ..

ich hab mir erstmal das was du erklärt hast gezeichnet und bin dann bei 2. darauf gekommen dass x und z sich NICHT kennen, und y und z sich NICHT kennen??

und bei 3. kennen sich x und y, x und z, y und z nicht ??? verwirrt

27.04.2010, 19:19

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von gzm
ich hab mir erstmal das was du erklärt hast gezeichnet und bin dann bei 2. darauf gekommen dass x und z sich NICHT kennen, und y und z sich NICHT kennen??

Hm, woher willst du das wissen bzw. wo habe ich solches behauptet? verwirrt

Zitat:

Original von gzmund bei 3. kennen sich x und y, x und z, y und z nicht ??? verwirrt

Ja, aber inwiefern ist das nützlich in Hinblick auf die Behauptung?

27.04.2010, 19:24

gzm

Auf diesen Beitrag antworten »

weil du ja gesagt hast dass A ein knoten ist das mit 3 anderen knoten x,y,z verbunden ist.

wenn dann bei 2. x mit y verbunden ist, dann ist x nicht mit z, und y nicht mit z verbunden. ??

und bei der 3 wie gesagt.

oder ich glaub ich hab immer noch nicht verstanden was du meinst unglücklich

27.04.2010, 19:36

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von gzm
wenn dann bei 2. x mit y verbunden ist, dann ist x nicht mit z, und y nicht mit z verbunden. ??

Um Gotteswillen, was ist denn das für eine obskure Logik? unglücklich

Wenn ich z.B. in einer Tischrunde erwähne, dass der anwesende Fritz sehr intelligent ist, heißt das dann, dass Gerlinde, Hubert und alle anderen, die dabeisitzen, strohdumm sind, nur weil ich sie nicht im gleichen Atemzug erwähnt habe? verwirrt

Die Wahrheit ist: Über deren IQ habe ich absolut keine Aussage gemacht, weder im Positiven, noch im Negativen... So ist es auch hier über die Beziehung von Z mit X bzw. Y, ich habe nichts darüber gesagt, ja es interessiert mich auch gar nicht, denn es ist hier vollkommen belanglos...

Zitat:

Original von gzmoder ich glaub ich hab immer noch nicht verstanden was du meinst unglücklich

Ja, das Gefühl habe ich allerdings auch... Es geht um den Beweis des Satzes der Graphentheorie, den ich oben angegeben habe oder verstehst du etwas in seiner Formulierung nicht? verwirrt

27.04.2010, 20:43

gzm

Auf diesen Beitrag antworten »

könntest du es mir vielleicht nochmal so erklären,sodass ich es verstehe traurig

etwas einfacher vllt. ??

27.04.2010, 21:19

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von gzm
könntest du es mir vielleicht nochmal so erklären,sodass ich es verstehe traurig

etwas einfacher vllt. ??

Ich kann versuchen, dass verwendete Vokabular noch einmal zu verdeutlichen...

- In jeder Gruppe mit 6 Menschen gibt es eine Dreiergruppe, die sich kennen... = In $\begin{eqnarray*} G \end{eqnarray*}$ (wie oben definiert) gibt es den vollständigen Graphen $\begin{eqnarray*} K_3 \end{eqnarray*}$ als Teilgraphen (in einer Zeichnung würde man da die den $\begin{eqnarray*} K_3 \end{eqnarray*}$ als Dreieck sehen können, desen Eckpunkte die Knoten und dessen Seiten die Kanten sind...)

- ...oder die sich nicht kennen = dasselbe wie oben, aber jetzt für den Komplementgraphen $\begin{eqnarray*} \bar G \end{eqnarray*}$ , für den zwei Knoten genau dann durch eine Kante verbunden sind, wenn das in $\begin{eqnarray*} G \end{eqnarray*}$ nicht der Fall war....

Um zu zeigen, dass es entweder in $\begin{eqnarray*} G \end{eqnarray*}$ oder in $\begin{eqnarray*} \bar G \end{eqnarray*}$ so eine Dreiergruppe (bzw. den $\begin{eqnarray*} K_3 \end{eqnarray*}$ oder graphisch eben ein Dreieck gibt), musst du die einzelnen Punkte 1.,2.,3. von oben durchgehen, da führt leider kein Weg daran vorbei, die kann man nicht mehr einfacher formulieren ohne eine Totallösung hier hereinzustellen, sorry...

Neue Frage »

Antworten »

beweisaufgabe

Verwandte Themen