Matematik
Rodtræ
"Et rodtræ er en retningsbestemt graf, der er sammenhængende, men som ikke indeholder en simpel kreds. Derudover skal én knude i grafen være rod, dvs. enhver kant i grafen skal være orienteret væk fra roden."
Mit spørgsmål går på, om følgende graf kan karakteriseres som et rodtræ ud fra ovenstående definition:
a
|\\
| \\
b c
|
|
a
Spørgsmålet bliver vel, om begge knuder a skal opfattes som rødder. I så fald vil det ikke være et rodtræ.
Svar #1
26. juni 2006 af Sabrina (Slettet)
Kan en gruppes orden godt være lig med 0? Således mængden G i (G,*) er tom?
De blandede spørgsmål skyldes, at jeg skal op til eksamen i projektet på 2. semester ved AAU på torsdag.
Svar #2
26. juni 2006 af Sansnom (Slettet)
Den graf du har tegnet er ikke retningsbestemt (orienteret), så dit spørgsmål giver ikke rigtigt mening.
Hvis den orienterede graf ser således ud:
d <- c <- a -> b
er a roden.
Hvis den derimod ser således ud:
d -> c -> a -> b
er d roden.
Da der ikke må være en kreds i grafen, og alle andre knuder skal kunne nåes fra roden, kan der kun være een rod. (kan sikkert bevises vha et modstridsbevis).
Svar #3
26. juni 2006 af Sansnom (Slettet)
Du kan sikkert finde svaret i din bog under definitionen på en gruppe. I Rings, Fields and Groups, Allenby er defitionen:
A group is an ordered pair (G,*) where G is a non-empty set ....
Så, G kan ikke være den tomme mængde.
Det ville også skabe problemer mht eksistensen af det neutrale element, mens de to andre axiomer (associativ og inverse) ikke ville være noget problem i den tomme mængde.
Svar #4
26. juni 2006 af fixer (Slettet)
1) Nej. Kæden a->b->a danner en simpel kreds.
2) Nej. En gruppe har altid mindst eet element; det neutrale element.
Svar #5
27. juni 2006 af Sabrina (Slettet)
Hehe, Martin. Du har sikkert travlt.
Svar #6
28. juni 2006 af Sabrina (Slettet)
Min graf ser forresten således ud
c <-- a --> b --> a
(a er rod)
Kan det ifølge vores definition være et rodtræ?
Hvad med følgende:
a --> b --> c --> b
(a er rod)
Når et rodtræ nu ikke må indeholde en simpel kreds, må det så heller ikke indeholde en kreds?
Angående en gruppes orden, så er vores definition af et inverst element e følgende:
eksisterer e i G: for alle a i G: e * a = a * e = a
(med kvantorer)
Men den siger kun, at der skal eksistere et e, således at for alle a i G, skal der gælde ovenstående ligning.
Men der er slet ikke nogen a i G, hvis G er tom, så behøver der være et e?
Svar #7
28. juni 2006 af Sansnom (Slettet)
Def (træ)
Et træ er en sammenhængende graf uden kreds(e).
Da den underliggende graf for et rod træ skal være et træ, må der ingen kreds være i grafen.
Du mener vist det neutrale element, hvor du skriver det inverse element.
Den bog jeg refererer til, specificere direkte, at G skal være ikke-tom.
Mht til axiomet, så siger det jo, at der skal findes et element e (som så opfylder nogle betingelser). At betingelsen er uden betydning i den tomme mængde ændrer ikke ved, at elementet skal findes.
Et (søgt) eksempel:
"I dette rum findes en mand, som kan tegne alle firkantede cirkler."
Hvis der slet ikke findes nogen mand i rummet, så er det falsk. Hvis der derimod findes en mand i rummet, så er det sandt, da betingelsen med de firkantede cirkler er tomt opfyldt.
Svar #8
28. juni 2006 af fixer (Slettet)
(1)
En rod i en graf G er en knude r hvorfra der er orienterede kanter til alle øvrige knuder i G. Hvis G er et træ er der højest een rod; hvis der er en rod i et træ G, har den indgangsvalens 0 og alle øvrige knuder i G har indgangsvalens 1.
(2)
En ikke-tom mængde S sammen med en binær operation i S kaldes en gruppe hvis
(i)
Der findes et neutral element e E S; med andre ord gælder
a*e = e*a for alle a E S
(ii)
For ethvert valg af elementer a,b,c E S gælder
(a*b)*c = a*(b*c)
(iii)
Ethvert element a E S har et inverst i S, d.v.s. der findes et element b E S så
a*b = e = b*a
Betingelserne (i)+(ii) sikrer at (S,*) er en semigruppe med neutral element. Antallet af elementer i S, |S|, kaldes gruppens orden. Det ses at da S != Ø er |S| >= 1.
Svar #9
30. juni 2006 af Sabrina (Slettet)
Jeg fik svaret på en hel del spørgsmål jævnt fordelt over kapitlerne. Det endte med, at jeg fik 11 og følgende kommentar fra censoren: "Du svarede skarpt (præcist)".
Derudover fik 4 af gruppens medlemmer 10, mens en fik 8.
Nu vil jeg holde velfortjent sommerferie :)
I skal have mange tak for jeres hjælp - håber jeg får mulighed for at kunne hente støtte herinde, når jeg påbegynder 3. semester.
I ønskes en rigtig god sommer!
Svar #10
30. juni 2006 af Sansnom (Slettet)
Det er for øvrigt sjovt, at folk, der ikke kender til den slags eksamener, ofte tror, at karaktererne ikke kan differentieres. Som du har oplevet, er det jo slet ikke tilfældet. Personligt kan jeg huske en gruppeeksamen, der gik fra 5 til 13.
Svar #11
01. juli 2006 af Sabrina (Slettet)
Wow - det var virkelig noget af et spring.
Den differentiering, der var ved vores eksamen, er faktisk også den største dette semester ved projekteksamenerne i vores faggruppe (matematik, datalogi, software, fysik og sundhedsmatematik).
Men jeg skal da ikke lægge skjul på, at det føles lidt rart at se, at en person, som ikke har løftet en finger hele semesteret, ikke ender med den samme karakter som resten af gruppens medlemmer.
Skriv et svar til: Rodtræ
Du skal være logget ind, for at skrive et svar til dette spørgsmål. Klik her for at logge ind.
Har du ikke en bruger på Studieportalen.dk?
Klik her for at oprette en bruger.