Mathebeispiele für Montag, 22.04.2002

[dj_m.o.h.t.]

Schreibe euch wieder alle Beispiele für die kommende Matheübung am Montag auf. Bei 2 Beispielen habe ich ein bisschen Probleme, aber ich werde es euch eh hinschreiben und ich freue mich wieder auf eure Lösungsvorschläge, die ihr macht, wenn ich ein Beispiel falsch habe.

[dj_m.o.h.t.]

R-Relation m,n element {2,3,4,5,7,8,11,13}
mRn <=> m+n ungerade oder m=n

reflexiv: aRa => ist reflexiv

symmetrisch: aRb => bRa
Addition ist kommutativ => symmetrisch

transitiv: aRb und bRc => aRc
ein Gegenbeispiel:
2R3 und 3R4 => 2R4 => nicht transitiv

[dj_m.o.h.t.]

3-regulärer Graph

n=4

V={0,...,n-1}
E={[i,j]: (i-j) mod n element S}
S = {1,-1,n/2}

weiter weiß ich leider auch nicht.

[dj_m.o.h.t.]

soviel ich herausgefunden habe, müsste es 5 nicht isomorphe Graphen geben.

1.Graph:
.
.
.
.
.
.

2.Graph:
.
. .
.
.
.

3.Graph:
. .
. .
.
.

4.Graph:
.
.
. .
.
.

5.Graph:
. .
.
.
. .

[dj_m.o.h.t.]

Es gibt keine stark zusammenhängende Komponenten, weil man nicht von jedem beliebigen Eckpunkt zu jedem anderen Punkt gelangen kann.

[dj_m.o.h.t.]

stark zusammenhängend:
{1,2,8}
{3,4,5,6}

schwach zusammenhängend:
{1,2,8}
{1,2,8,7,6}
{1,2,8,7,6,3}
{4,5,6}

usw.

Es gibt unendlich viele.

[dj_m.o.h.t.]

gerichtete Kreise:
{5,2,3,5}
{5,4,3,5}

Weggrade weiß ich leider nicht!

[dj_m.o.h.t.]

I have no idea!

[-z0nk-]

hmm ... hab da ein paar fragen:
was bedeuten die begriffe "digraph", "ordnung eines graphen" und "3-regulärer Graph" ?

... haben wir, soweit ich das mitbekommen habe, in der VO noch nicht besprochen.

mfg,
-z0nk-

[Bernie]

wenn ich nicht völlig geschlafen hab dann war von dem noch nix in der vorlesung. und lustigerweise find ich auch im skriptum keinen der begriffe digraph und 3-regulärer graph...

[Petzi]

ich könnt mich auch net erinnern, dass wir sowas wie Digraph und 3-regülärer Graph in der VO schon gemacht haben.

[dj_m.o.h.t.]

Digraph = gerichteter Graph

[PliniusSecundus]

3-regulärer Graph=ein ungerichteter Graph, in dem alle Knoten Grad 3 haben.
Beispiel am Übungsblatt 4 Knoten:
1---2
| X |
3---4

[Heavy]

Hallo,

Könnte bitte jemand von Euch die genauen Angaben der Mathe Beispiele posten?
Dummerweise hab ich vergessen die UE-Blätter zu kaufen...Danke

[Chris]

die beispiele für übermorgen sind eh noch auf den alten übungsblättern drauf..

[Heavy]

Wirklich? Dann fehlt mir die letzte Seite....die ist wirklich weg. :(

[Phil]

Original geschrieben von robby
R-Relation m,n element {2,3,4,5,7,8,11,13}
mRn <=> m+n ungerade oder m=n

reflexiv: aRa => ist reflexiv

symmetrisch: aRb => bRa
Addition ist kommutativ => symmetrisch

transitiv: aRb und bRc => aRc
ein Gegenbeispiel:
2R3 und 3R4 => 2R4 => nicht transitiv

Beispiel 444:
reflexiv, symmetrisch ja; nicht transitv.
1.) Graph
http://stud3.tuwien.ac.at/~e9406638/Bsp444a.gif

2.) Koordinatensystem
http://stud3.tuwien.ac.at/~e9406638/444b.gif

[Phil]

Original geschrieben von robby
3-regulärer Graph

n=4

V={0,...,n-1}
E={[i,j]: (i-j) mod n element S}
S = {1,-1,n/2}

weiter weiß ich leider auch nicht.

hab das mit theo für beliebige (gerade) n konstruiert:

http://stud3.tuwien.ac.at/~e9406638/449.gif

für ungerade n nicht möglich;

[kitti]

Ich bin mir nicht sicher aber ich glaube das als Weggerade die hamiltonsche Linie gemeint ist. Hamiltonsche Linie ist ein Weg der jeden Knoten einmal enthält. => {6,1,2,3,5,4}

Außerdem müßte der Kreis {5,4,2,3,5} auch möglich sein!

[Phil]

theo und ich haben folgende 6 gefunden, die anderen sind isomorph:

http://stud3.tuwien.ac.at/~e9406638/Bsp456.gif

[Phil]

a)
Weggrade:
d+(1)=1
d+(2)=1
d+(3)=1
d+(4)=2
d+(5)=2
d+(6)=2
die Weggrade sind laut Skript die Anzahl der wegführenden Kanten bei jedem Knoten.
Gerichtete Kreise:
{2,3,5,2}
{3,5,4,3}
{5,4,2,3,5}
Das Bild dazu:
http://stud3.tuwien.ac.at/~e9406638/461.gif

b)
Die Knotenmenge: V(G)={x1, x2, x3,....., xn}
Die Kantenmenge: E(G)={e1, e2, e3,.....,en} hier wären
noch weitere Kanten möglich, ist aber nicht relevant.

|V(G)|<=|E(G)| es gibt zumindest genausoviele Kanten wie Knoten.
jetzt bekommt jede Kante "seine" Knoten (positiver Weggrad heißt hier wohl: es führt zumindest eine Kante weg):
das mache ich mit einer Zuordnung:
phi(e1)=(x1,x2) mit x1 != x2 sonst wäre es schon ein Zyklus der Länge 0
phi(e2)=(x2,x3) x2 != x3 , x3=! x1 sonst wäre es ein Zyklus;
es muss immer ein "neuer" Knoten als Endpunkt gewählt werden. Als Startpunkt wähle ich immer den Nächsten Knoten (von jedem x muss ein e wegführen)
.....
für die letzte Kante geht sich das nimmer aus, alle Knoten sind verbraucht
phi(en)=(xn,xi) hier steht das xi für einen Knoten, der noch nicht Startpunkt sein soll, sonst kommt irgndwo ein Zyklus raus (auch solche Zyklen sind Zyklen: {1,1} oder {1,2,1} ). Das ist aber nicht möglich, alle Knoten sind scon weg.

Vielleicht kann das wer mathematisch korrekter anschreiben. Ich hoffe es versteht irgendjemand den Gedankengang.

[Phil]

a) keine
b) schwach:
{1,2,3,4,5,6,8}
{3,4,5,6}
{1,2,3,4,5,6,7,8}
stark:
{3,4,5,6}

[-z0nk-]

würde folgender graph nicht auch noch dazuzählen ?

o
|
o--o--o
|
o
|
o


der ist doch nicht isomorph zu den bisher erwähnten, oder ?

mfg, zonk

[-z0nk-]

doch ist er ;)

sorry :)

zum bsp 458: könnte bitte jemand erklären, wie man den schatten eines gerichteten graphen erzeugt, das is in der VO ziemlich rasch und kleingeschrieben abgelaufen ;)

mfg, z0nk

[Phil]

Original geschrieben von -z0nk-
doch ist er ;)

sorry :)

zum bsp 458: könnte bitte jemand erklären, wie man den schatten eines gerichteten graphen erzeugt, das is in der VO ziemlich rasch und kleingeschrieben abgelaufen ;)

mfg, z0nk

Schatten geht so:

Du übernimmst alle Knoten wie sie sind. Dann zeichnest du die Kanten folgendermaßen:
Zwischen 2 Knoten x und y zeichnest du max(x,y) ungerichtete Kanten.
z.B. von x nach y gehen 2 Kanten von y nach x eine -> sind 2 ungerichtete Kanten. Meist sinds 0 und 1 dann zeichnest du eine Kante ein, genauso wenn es eine von x nach y und eine von y nach x ist.

[lj_scampo]

bsp 444:

Tolle Zeichnungen von Phil! ;)
Allerdings muss beim Graphen noch bei jedem Knoten eine Schleife rein (aRa reflexiv)

[Chris]

bsp 456:

@robby:
steht eigentlich irgendwo versteckt in der angabe, dass jeder knoten nur maximal 2 kinder haben darf?
(ich hoffe, dass es irgendwo steht, weil sonst gäbs ziemlich viele lösungen für das beispiel..)

wäre sowas nicht auch ein baum:

[-z0nk-]

Original geschrieben von Chris
bsp 456:

@robby:
steht eigentlich irgendwo versteckt in der angabe, dass jeder knoten nur maximal 2 kinder haben darf?
(ich hoffe, dass es irgendwo steht, weil sonst gäbs ziemlich viele lösungen für das beispiel..)

wäre sowas nicht auch ein baum:

da geht´s doch nicht um kinder, oder ? die anordnung (also oben, unten) ist - glaub ich - egal, wir sind ja hier nicht in algodat ;)

und der, den du aufgemalt hast ist isomorph zum oben gezeichneten 6er Graphen.

mfg, -z0nk-

[Faceless]

458 b)

wie kommt ihr darauf, dass des KEINE stark zusammenhängenden Komponenten gibt?
denn für mich sind ja schon 2 durch eine gerichtete Kante verbundene Knoten bereits eine stark zusammenhängende Komponente... denn von Knoten a nach b ist doch bereits laut definition ein Weg!
verstehe ich da was falsch?

461 b)

zonk: ich kann deine begründung nachvollziehen, jedoch ist doch bei der aufgabe zu zeigen, dass es MINDESTENS EINEN kreis bei dieser konstellation gibt!
und deine schlussfolgerung ist daher doch nicht richtig... du gehst davon aus, dass immer ein anderer knoten von der kante "getroffen" werden muss. das ist nur bis zur vorletzten kante möglich - die letzte muss zu einem knoten, der bereits einen hingrad von 1 hat. (das alte zerteile-ein-brett-in-12-teile-wieviele-schnitte-benötigst-du-spielchen ... antwort: 11)
d.h.: es gibt auf jeden fall mindestens einen kreis

mfg,
martin

[Chris]

Original geschrieben von -z0nk-

da geht´s doch nicht um kinder, oder ? die anordnung (also oben, unten) ist - glaub ich - egal, wir sind ja hier nicht in algodat ;)
und der, den du aufgemalt hast ist isomorph zum oben gezeichneten 6er Graphen.


eh nicht kinder... die anordnung würde ich auch als egal sehen.
nur gibts hier halt einen knoten, der mit allen anderen verbunden ist (der oberste). Zu welchem graphen vom Robby ist der isomorph?

sry, wenn das kompletter quatsch ist.. bin schon ein bisserl fertig heut..

[-z0nk-]

ok missverständnis ;)

beim robby eh net, aber beim phil !

mfg, -z0nk-

[Joachim]

@faceless 458: Deine Argumentation für 2 Knoten stimmt nicht denn wie bekommst Du einen gerichteten Weg von b nach a ohne einen Kreis zu bilden???
Allerdings verstehe ich auch nicht, warum es keine gibt, denn bei 3 Knoten funktioniert es! Mit den Kanten [1,2] [2,1] [2,3] [3,2] habe ich keinen Kreis und komme auch zu jedem Knoten über einen gerichteten Weg, was doch die Definition eines stark zusammenhängenden Graphen ist???

[-z0nk-]

@joachim: ich denke [1,2], [2,1] bildet einen kreis. genauso [2,3] und [3,2]

oder red ich da grad stuss ? ;)

[Chris]

Original geschrieben von -z0nk-
ok missverständnis ;)

beim robby eh net, aber beim phil !

mfg, -z0nk-

dankeschön... das kommt davon, wenn man die andern postings nur irgendwie überfliegt.. :(


mfg, Chris

[Joachim]

@zOnk: hast recht, hab' immer den graphen als gesamtheit betrachtet aber azyklisch heist ja, dass der graph überhaupt keine kreise enthalten darf...sorry, war mein denkfehler...ok, es kann bei einem azyklischen graphen keinen stark zusammenhängenden komponenten geben... ;-)

[CitizenX]

ad 449.)

kann ich da nicht sagen E(X) = Knotenanzahl mal Grad der Knoten mal einhalb => wenn ich jetzt aber 5,7,9,... Knoten hab bekomm ich eine Kantenanzahl von *,5 heraus => halbe Kante ?!?! => falsche Aussage

kann mir jemand sagen ob dieser Gedankengang stimmt

Greets X :coolsmile

[Joachim]

ich habe meine Lösung zu 449 im thread "beispiel 449" gepostet...
was willst du mit diesem gedankengang eigentlich aussagen?
das es mit ungeraden n nicht funktioniert besagt schon alleine die regel, dass ein ungerader knotengrad nur eine gerade anzahl von knoten haben kann....

ich komme mit bsp 456 net klar...hat da wer eine lsg.
warum ist der graph 2 und 3 von phil nicht isomorph???

mfg,
Joachim

[CitizenX]

das es mit ungeraden n nicht funktioniert besagt schon alleine die regel, dass ein ungerader knotengrad nur eine gerade anzahl von knoten haben kann....

Das gilt doch bewiesen zu werden
Man konstruieren... ...Ist dies auch für ungerades n möglich?

dies sollte ein "möglichst einfacher Beweisversuch" sein

Greets X :coolsmile

[Joachim]

also ein beweis ist nicht verlangt...die frage ist doch nur ob es möglich ist oder nicht....da würde sogar ein simples "nein" reichen.... :-))) diese problemstellung war doch schon bei einem vergangenen beispiel(431)

[Joachim]

@phil 458b: bei den stark zusammenhängenden komponenten gibt es 2 --> siehe lsg robby!
aber wie kommst du bitte auf die 3 schwachen?? irre ich mich oder ensteht nicht durch die bildung des schatten sowieso ein kreis, d.h. es ist sowieso jeder knoten von jedem anderen aus durch einen weg erreichbar! stellt sich nur noch die frage wieviel komponenten es gibt---> also summe über k = 2bis8 (8 über k) möglichkeiten sprich komponenten gibt es. (also auch nicht undendlich viel wie von robby angenommen)

müßte doch stimmen, oder hab' ich einen denkfehler?

[-z0nk-]

falls der beweis doch jemanden interessiert, hier:

die summe über alle knotengrade = 2*kantenmenge

==> summe über alle knotengrade ist gerade
==> die anzahl der ungeradgradigen knoten muss gerade sein.

mfg,
-z0nk-

[Shade]

@ 456
was ist denn mit diesen beiden Graphen?die sollten auch nicht isomorph sein.
damit wär ich bei neun graphen

[-z0nk-]

Original geschrieben von Faceless
461 b)

zonk: ich kann deine begründung nachvollziehen, jedoch [...]

hab doch garnicht ich geschrieben :)

stimmt trotzdem ;)

[-z0nk-]

Original geschrieben von Phil

Vielleicht kann das wer mathematisch korrekter anschreiben. Ich hoffe es versteht irgendjemand den Gedankengang.


klar, der gedankengang ist volkommen richtig. ich fürcht nur, dass die einen induktiven beweis von uns wollen, und induktion war noch nie so meins ;)

naja, ich mach mal den anfang:

Induktion nach Anzahl n der Knoten:

Ind. Anfang: n=1
--> trivialerweise richtig, da mit einem knoten nur schlingen (also kreise) gebildet werden können.


so jetzt darf jemand anderer fortsetzen :)

[CitizenX]

@458b :
In der Angabe steht doch nicht das der Digraph azyklisch sein muss => somit sind Loops nicht auszuschliessen und somit wären auch {1,2}, {1,8}, {5,6} stark zusammenhängende Komponenten (Komponente = Teilgraph der diese Bedingung erfüllt)

Greets X :coolsmile

[Shade]

hier mal alle lösungen die ich für 456 hab (11 Stück):

[Shade]

wollt eigentlich ein ascii bild machen das wurde aber immer umformatiert:mad:
also hab ichs schnell was gemalt
kommentare erwünscht

[Phil]

ich denke du hast zu viele aufgemalt. dein 1. und 2. sind schon gleich. ein graph wird ja beschrieben, indem man die Knoten angibt und die Kanten (z.b. von x nach y) und nicht wie man sie aufmalen könnte.
isomorph wäre dann glaub ich dass man die "Namen" der Knoten vertauscht, also beim 1. nicht {1,2,3,4,5,6} sondern {1,3,4,5,6,2}.

[Phil]

Original geschrieben von Joachim
@phil 458b: bei den stark zusammenhängenden komponenten gibt es 2 --> siehe lsg robby!
aber wie kommst du bitte auf die 3 schwachen?? irre ich mich oder ensteht nicht durch die bildung des schatten sowieso ein kreis, d.h. es ist sowieso jeder knoten von jedem anderen aus durch einen weg erreichbar! stellt sich nur noch die frage wieviel komponenten es gibt---> also summe über k = 2bis8 (8 über k) möglichkeiten sprich komponenten gibt es. (also auch nicht undendlich viel wie von robby angenommen)

müßte doch stimmen, oder hab' ich einen denkfehler?

ist unsinn was ich da gepostet habe. 2 starke sind mir klar. bei den schwachen bin ich mir nicht sicher

[Bking]

gibts diesmal garkein pdf-file? :D

[Benno]

ja, ein pdf wär fein!!! biitttteeee

[Woeni]

Original geschrieben von Benno
ja, ein pdf wär fein!!! biitttteeee
+:thumb: +:thumb: +:thumb: +:thumb: +:thumb:

[shabby]

Aber wirklich, wo bleibt das wöchentliche PDF ? :coolgrim:
Jaja, an so ein Service gewöhnt man sich schnell, Abhängigkeit und Hilflosigkeit bei dessen Fehlen sind die Folge ... :ahhh:

Vorschlag und Appell an die Ersteller der Beiträge hier: Nachdem für Montag eh ein eigener Room existiert, bitte jedes Beispiel in eigenes Topic (ausnahme: .pdf ' s natürlich). 52 Beiträge sind total unübersichtlich, wenn sie sich auf verschiedene Beispiele beziehen.
(@ Robby: da du eh meistens als erster 5 Beiträge schreibst, könntest du das gleich übernehmen)
ansonsten wie immer danke für die Mühe
mfg,B.

[dj_m.o.h.t.]

Ok! Dann werde ich das so machen, dass ich pro Beispiel einen neuen Thread schreibe. Dann wird es wenigstens übersichtlicher. Bezüglich PDF-File! Das schreibe ich erst immer nach der Matheübung, da ich ja vorher schaue, was ich richtig bzw. falsch habe und es dann schon ausgebessert als File schreibe und wie immer dann an Kenny schicke. Und auf http://www.mworx.at/infoworx/ findet ihr wie immer dann die Beispiele!

[thita]

hier ein hilfreicher link: http://www.abbiseite.de/informatik/#30

[MrBurnst]

hier noch ein link der mir zumindest geholfen hat ein bisserl was abzuchecken: http://www.cs.fh-aargau.ch/~gruntz/courses/inf3/slides/GraphDefinitionen.pdf

[Kenny]

eigenes thema pro bsp find ich eine super idee!

weil das hier mit den 4 seiten zu lesen, wo auf seite 1 der anfang eines bsp steht, auf seite 2 eine frage dazu, auf seite 3 schreibt wer dass alles falsch is und auf seite 4 kommt eine ausbesserung, das is eine zumutung...

die pdf's kommen zwar meistens erst im nachhinein, aber natürlich thx an robby, auf www.mworx.at/infoworx zum download !

[dj_m.o.h.t.]

Bezüglich zu den nächsten Beispielen: Werde erst am Donnerstag dazukommen, die Beispiele im Forum zu posten, da ich mein Kollege, mit dem ich die Beispiele immer durchrechne, erst am Donnerstag Zeit hat. Aber hoffentlich macht das euch nix aus. Denn wir haben ja eh immer das ganze Wochenende Zeit die Beispiele zu rechnen. Aber ich werde mich wie immer bemühen, das so schnell wie möglich zu erledigen.

[Länz]

Original geschrieben von robby
erst am Donnerstag........

ERST AM DONNERSTAG! Das wird dann aber ganz schön knapp.;)
....
naja dann werd ich halt as usual am Montag am Morgen so gegen 12Uhr anfangen - denn das ist sich ja noch immer bis 15:30 ausgegangen.

[Benno]

nana, des passt scho! bin überhaupt froh, dass ein schlauer kopf mir ungefähr sagt, was überhaupt zu tun ist bzw. mir denkhilfen gibt ... bis jetzt hats einfach super funktioniert!!!

lg

[Kenny]

ja benno ich merks ihr habt eh immer alle 5 bsp... mir reichen 4 eigentlich auch meistens, bin da ned so ;)