Dies ist eine statische Kopie unseres alten Forums. Es sind keine Interaktionen möglich.
This is a static copy of our old forum. Interactions are not possible.

BLUESCREEN

Junior Schreiberling

  • "BLUESCREEN" is male
  • "BLUESCREEN" started this thread

Posts: 244

Date of registration: Oct 11th 2005

1

Sunday, July 2nd 2006, 4:46pm

Diskrete Strukturen - Übungsblatt 6

Weiß jemand, wie die Gradfolgen bei Aufgabe 2a und 2c zu verstehen sind?

Bei 2a steht z.B. in der Aufgabenstellung: (1,1,1,3,...)

ist das nun (1,1,1,3,4,5,6,7,8,9,...) oder (1,1,1,3,5,7,9,...)?



Zu Aufgabe 5:

Bedeutet "Knotenmenge m", dass die Anzahl der Knoten m beträgt (m ist eine Abkürzung für {1,...,m})?



edit: Es geht um folgenden Aufgabenzettel: http://www-ifm.math.uni-hannover.de/~pig…en/huebg_06.pdf

This post has been edited 1 times, last edit by "BLUESCREEN" (Jul 2nd 2006, 5:41pm)

  • Send private message

Joachim

Guru

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

2

Sunday, July 2nd 2006, 5:19pm

RE: Diskrete Strukturen - Übungsblatt 6

Quoted

Original von BLUESCREEN
Weiß jemand, wie die Gradfolgen bei Aufgabe 2a und 2c zu verstehen sind?

Bei 2a steht z.B. in der Aufgabenstellung: (1,1,1,3,...)

ist das nun (1,1,1,3,4,5,6,7,8,9,...) oder (1,1,1,3,5,7,9,...)?
So wie ich die Aufgabenstellung verstehen, sind damit Anfangsstücke gemeint. (1, 1, 1, 3, ...) steht also stellvertretend für alle Gradfolgen, die mit 1, 1, 1, 3 beginnen.

Quoted

Zu Aufgabe 5:

Bedeutet "Knotenmenge m", dass die Anzahl der Knoten m beträgt (m ist eine Abkürzung für {1,...,m})?
Wenn die Knotenmenge {1,...,m} ist, dann muß es doch genau m Knoten geben, oder? :) Oder liegt das Problem beim Begriff "Knotenmenge"?


PS: Bitte bei Fragen zu Übungen immer einen Link zu den jeweiligen Aufgabenstellungen mit angeben. Das spart den Leuten Zeit, die die jeweilige Veranstaltung zwar nicht besuchen, aber trotzdem helfen wollen. :)

http://www-ifm.math.uni-hannover.de/~pig…en/huebg_06.pdf
The purpose of computing is insight, not numbers.
– Richard Hamming, 1962
  • Send private message

BLUESCREEN

Junior Schreiberling

  • "BLUESCREEN" is male
  • "BLUESCREEN" started this thread

Posts: 244

Date of registration: Oct 11th 2005

3

Sunday, July 2nd 2006, 5:46pm

RE: Diskrete Strukturen - Übungsblatt 6

Quoted

Original von Joachim
So wie ich die Aufgabenstellung verstehen, sind damit Anfangsstücke gemeint. (1, 1, 1, 3, ...) steht also stellvertretend für alle Gradfolgen, die mit 1, 1, 1, 3 beginnen.

Daran hatte ich auch schon gedacht, halte das aber für unwahrscheinlich, da wir in der letzten Übung Bäume mit der Gradfolge (1,...,1,1,2,3,4,5,6,7,8,9,...,n) betrachtet haben.

Quoted

Original von Joachim
Oder liegt das Problem beim Begriff "Knotenmenge"?

Falls das wirklich heißen soll, dass es m Knoten gibt, dann verwirrte mich nur die umständliche Schreibweise :D
  • Send private message

Cid

Trainee

  • "Cid" is male

Posts: 81

Date of registration: Oct 5th 2005

Occupation: Informatik

4

Sunday, July 2nd 2006, 7:39pm

Wenn man da alle Gradfolgen betrachten soll,
ist es wahrscheinlich, dass man verschiedene Formeln angeben soll
oder einzelne Graphen ausschließen soll, weil die Gradfolge unmöglich ist...
z.B. 1,1,2,3 => Summe ist ungerade, Graph kann man nicht konstruieren...

Lese ich mir nach Java erst durch...
Ich bin ein Zweitsemester - bitte, belästigen Sie mich nicht damit! :sleeping:
Ein Mathematiker ist eine Maschine, die Kaffee in Theoreme verwandelt. -Paul Erdös
  • Send private message

sasa

Junior Schreiberling

  • "sasa" is male

Posts: 133

Date of registration: Oct 24th 2005

Location: Celle

Occupation: Software Engineer

5

Monday, July 3rd 2006, 11:53am

RE: Diskrete Strukturen - Übungsblatt 6

Quoted

Original von BLUESCREEN

Quoted

Original von Joachim
So wie ich die Aufgabenstellung verstehen, sind damit Anfangsstücke gemeint. (1, 1, 1, 3, ...) steht also stellvertretend für alle Gradfolgen, die mit 1, 1, 1, 3 beginnen.

Daran hatte ich auch schon gedacht, halte das aber für unwahrscheinlich, da wir in der letzten Übung Bäume mit der Gradfolge (1,...,1,1,2,3,4,5,6,7,8,9,...,n) betrachtet haben.


Das würde doch bedeuten, dass (a) (1, 1, 1, 3, ...) und (c) (1, 1, 1, 1, 3, ...) identisch sind?!
Außerdem würde ich auf den ersten Blick vermuten, dass es zu allen Gradfolgen unendlich viele Isomorphietypen geben müsste.

Betrachtet man dagegen nur gerade die Bäume, die genau den geforderten Anfang (beispielsweise
(1, 1, 1, 3, ...)) haben, kann ich meistens nur endlich viele Isomorphietypen finden.

Warum wir in der Übung diese anderen Gradfolgen behandelt, ist allerdings schon merkwürdig...
  • Send private message

BLUESCREEN

Junior Schreiberling

  • "BLUESCREEN" is male
  • "BLUESCREEN" started this thread

Posts: 244

Date of registration: Oct 11th 2005

6

Tuesday, July 4th 2006, 8:10pm

Ich habe nochmal nachgefragt und es geht bei Aufgabe 2 tatsächlich um vollkommen beliebige Gradfolgen von denen nur der Anfang bekannt ist.

Das ganze hat damit dann auch nichts mit der in der letzten Übung behandelten Formel zu tun.

Stattdessen sollen wir aus den gegebenen Valenzen irgendwelche Schlüsse ziehen...



Bei Aufgabe 4 gibt es auf dem Übungsblatt noch einen Fehler in der Aufgabenstellung (es muss m>8 und nicht m>=8 heißen - siehe auch Website zur Vorlesung).
  • Send private message

asbas

Trainee

Posts: 32

Date of registration: Jul 6th 2006

7

Thursday, July 6th 2006, 9:59pm

wenn die gradfolge aufsteigend sortiert ist bleibt bei der angabe (1,1,1,3,...) also ein baum mit drei blättern nicht viele möglichkeiten oder?

This post has been edited 1 times, last edit by "asbas" (Jul 6th 2006, 10:03pm)

  • Send private message

BLUESCREEN

Junior Schreiberling

  • "BLUESCREEN" is male
  • "BLUESCREEN" started this thread

Posts: 244

Date of registration: Oct 11th 2005

8

Friday, July 7th 2006, 1:16pm

Quoted

Original von asbas
wenn die gradfolge aufsteigend sortiert ist bleibt bei der angabe (1,1,1,3,...) also ein baum mit drei blättern nicht viele möglichkeiten oder?

Genau, und jetzt habe ich endlich verstanden, wie man die Aufgabe löst :D

Man hat den Anfang der Gradfolge und zwei unbekannte Werte: Die Anzahl der Knoten, die man noch hinzufügt und deren Valenzsumme.
Zu diesen beiden Variablen hat man zwei Bedingungen: Zum einen muss die Formel für die Valenzsumme weiterhin eingehalten werden und zum anderen muss jeder der neuen Knoten mindestens den gleichen Grad haben wie der letzte Knoten des vorgegebenen Anfangs der Gradfolge.
  • Send private message

sasa

Junior Schreiberling

  • "sasa" is male

Posts: 133

Date of registration: Oct 24th 2005

Location: Celle

Occupation: Software Engineer

9

Saturday, July 8th 2006, 10:32am

Frage zu Aufgabe 4

In Aufgabe 4 wird gefragt, für welche Zahlen m es [mindestens?] einen starren Baum mit m Knoten gibt.

Ich würde vermuten, dass es unendlich viele Zahlen m gibt.

Dann irritiert mich die Aufgabe „Skizzieren Sie für jedes m > 8 mindestens zwei nichtisomorphe starre Bäume!“ aber etwas. Demnach müsste man für zwei Isomorphietypen „Konstruktionsanleitungen“ mit entsprechender Knotenzahl m hinmalen?!
  • Send private message

BLUESCREEN

Junior Schreiberling

  • "BLUESCREEN" is male
  • "BLUESCREEN" started this thread

Posts: 244

Date of registration: Oct 11th 2005

10

Saturday, July 8th 2006, 11:07am

RE: Frage zu Aufgabe 4

Quoted

Original von sasa
mindestens?

mindestens.

Quoted

Original von sasa
Demnach müsste man für zwei Isomorphietypen „Konstruktionsanleitungen“ mit entsprechender Knotenzahl m hinmalen?!

Genau - einfach schematisch mit ein paar Punkten darstellen, wo im Graph beliebig viele Knoten sein können.
  • Send private message

sasa

Junior Schreiberling

  • "sasa" is male

Posts: 133

Date of registration: Oct 24th 2005

Location: Celle

Occupation: Software Engineer

11

Saturday, July 8th 2006, 3:36pm

RE: Frage zu Aufgabe 4

Quoted

Original von BLUESCREEN

Quoted

Original von sasa
mindestens?

mindestens.

Quoted

Original von sasa
Demnach müsste man für zwei Isomorphietypen „Konstruktionsanleitungen“ mit entsprechender Knotenzahl m hinmalen?!

Genau - einfach schematisch mit ein paar Punkten darstellen, wo im Graph beliebig viele Knoten sein können.


Gut, danke :)
  • Send private message

Wanja

Junior Schreiberling

Posts: 150

Date of registration: Feb 4th 2003

12

Wednesday, July 12th 2006, 12:18pm

vielleicht hab ich ja nen Brett vorm Kopf, aber wie konstruiert man bitte den Baum in Aufgabe 2b) ? Meiner Meinung nach nicht möglich, wenn der Baum nur 2 Blätter haben darf...

help :)

mfG Wanja

This post has been edited 2 times, last edit by "Wanja" (Jul 12th 2006, 12:19pm)

  • Send private message

Joachim

Guru

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

13

Wednesday, July 12th 2006, 1:38pm

Quoted

Original von Wanja
vielleicht hab ich ja nen Brett vorm Kopf, aber wie konstruiert man bitte den Baum in Aufgabe 2b) ? Meiner Meinung nach nicht möglich, wenn der Baum nur 2 Blätter haben darf...
Wenn das nicht nur Deine Meinung ist, sondern Du diese Aussage auch beweisen kannst, ist doch alles paletti. :)
The purpose of computing is insight, not numbers.
– Richard Hamming, 1962
  • Send private message

Wanja

Junior Schreiberling

Posts: 150

Date of registration: Feb 4th 2003

14

Thursday, July 13th 2006, 2:59pm

Was ich brauch, is ne 2te meinung, ob der baum konstruierbar ist oder nicht.

:)

mfG Wanja
  • Send private message

htk

Erfahrener Schreiberling

Posts: 262

Date of registration: Oct 16th 2003

15

Thursday, July 13th 2006, 3:09pm

wenn man sich die Definition von einem Baum anguckt ist es doch recht klar.
(kreisfrei und zusammenhängend)
surfs in mysterious ways
  • Send private message

Dude

Junior Schreiberling

Posts: 181

Date of registration: Oct 11th 2004

16

Thursday, July 13th 2006, 3:11pm

Quoted

Original von Wanja
Was ich brauch, is ne 2te meinung, ob der baum konstruierbar ist oder nicht.

:)

mfG Wanja

Nicht konstruierbar.
  • Send private message

Wanja

Junior Schreiberling

Posts: 150

Date of registration: Feb 4th 2003

17

Thursday, July 13th 2006, 3:59pm

gracias :D
  • Send private message

Joachim

Guru

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

18

Thursday, July 13th 2006, 4:13pm

Quoted

Original von Wanja
Was ich brauch, is ne 2te meinung, ob der baum konstruierbar ist oder nicht.
Wie gesagt: Versuch' Deine Meinung in Form eines Beweises abzusichern. Alles andere spielt in der Mathematik sowieso keine Rolle. :)
The purpose of computing is insight, not numbers.
– Richard Hamming, 1962
  • Send private message

julia

Trainee

Posts: 36

Date of registration: Jul 14th 2006

19

Friday, July 14th 2006, 5:31pm

Guten Abend,
ich brauche dringend Hilfe (Habe mich leider sehr spät entschieden diese Klausur mitzuschreiben :()

Es geht um das Theme Isomorphietypen von Bäumen.
In der Muterlösung habe ich die folgende Formel:

2* abs(E) = Sum(di) mit i=1,..,m

m ist doch die Anzahl der Knoten , richtig?
ein Baum ist konstruierbar genau dann ,wenn die Summe der Gradfolge gerade ist , richtig?

Wie kommt man zu den folgenden Werten:
Teil a) 2*m-2>=3+3*(m-3)

Teil b) 2*m-2>=4+3*(m-3)

teil c)2*m-2>=4+3*(m-4)

und wie sieht man ,die Anzahl der Isomorphientypen ?

Ich bitte um Hilfe X(


Kann mir keiner helfen??? ?(

This post has been edited 1 times, last edit by "julia" (Jul 17th 2006, 6:54pm)

  • Send private message