Knoten Kanten und Grad < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:55 Do 13.11.2008 | | Autor: | Feiratos |
| Aufgabe | Gibt es einen Graphen mit folgenden Graden:
(a) 0, 2, 2, 2, 4, 4, 6;
(b) 2, 2, 3, 3, 4, 5? |
Hallo,
bei a) würde ich sagen nein, denn ein Knoten hat den Grad Null, d.h. er ist mit keinen anderen Knoten durch eine Kante verbunden.
Ddurch sind nur noch 5 Knoten übrig, die mit anderen Knoten durch Kanten verbunden werden können.
Da ein Knoten aber den Grad 6 hat, also dass von diesen 6 Kanten abgehen, kann es diesen Graph nicht geben, denn es ist max Grad 5 möglich.
bei b)
Jeder Graph hat eine gerade Anzahl von Ecken(Knoten) ungeraden Grades.
Folgerung: die Summe der Grade entspricht der doppelten Anzahl der Kanten.
Da hierbei die Anzahl der des Grades 19 beträgt, kann das hier kein Graph sein, denn von jeder (natürlichen) Zahl das doppelte ist gerade, und daher nicht 19.
Ich hoffe es stimmt so, denn ich komme oft mit den Begriffen Grad Kanten und Ecken Knoten durcheinander.
Ist es richtig, dass Knoten=Ecken sind?
und ich habe eigentlich das Gefühl, da Kanten =der Grad des Kntoen sind/ist.
deswegen bin ich bei der b) ausgewichen.denn wenn nach Definition die Summe der Grade die Summe der 2fachen Kantenanzahl betrifft...hätte ich mit meiner Idee, dass beide dasselbe sind verloren.
Kennt jemand einen Link wo es besser und für Dumme ganz leicht erklärt ist?
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:02 Do 13.11.2008 | | Autor: | Feiratos |
...?
|
|
|
| |
|
Hallo Feiratos!
Ich hoffe, ich kann dir ein bisschen helfen.
Höre in diesen Semester selbst zum ersten mal Diskrete Mathematik und bin daher auch noch nicht wirklich fit dadrin.
> bei a) würde ich sagen nein, denn ein Knoten hat den Grad
> Null, d.h. er ist mit keinen anderen Knoten durch eine
> Kante verbunden.
Find ich logisch.
> Ddurch sind nur noch 5 Knoten übrig, die mit anderen
> Knoten durch Kanten verbunden werden können.
> Da ein Knoten aber den Grad 6 hat, also dass von diesen 6
> Kanten abgehen, kann es diesen Graph nicht geben, denn es
> ist max Grad 5 möglich.
Hmm, was ist denn mit parallelen Kanten? Dann könnte doch ein Graph mit 5 Knoten und Grad >5 existieren, oder?
Geht es bei euch um zusammenhängende Graphen? Weil würde dann nicht schon das Argument mit der 0 genügen?
> bei b)
> Jeder Graph hat eine gerade Anzahl von Ecken(Knoten)
> ungeraden Grades.
> Folgerung: die Summe der Grade entspricht der doppelten
> Anzahl der Kanten.
> Da hierbei die Anzahl der des Grades 19 beträgt, kann das
> hier kein Graph sein, denn von jeder (natürlichen) Zahl das
> doppelte ist gerade, und daher nicht 19.
Genau diesen Satz (bzw. dessen Beweis) habe ich nicht verstanden 
Daher hierzu keine Antwort.
> Ich hoffe es stimmt so, denn ich komme oft mit den
> Begriffen Grad Kanten und Ecken Knoten durcheinander.
> Ist es richtig, dass Knoten=Ecken sind?
Wir hatten den Begriff der "Ecke" nicht, aber ich würde sagen, dass dem so ist.
> und ich habe eigentlich das Gefühl, da Kanten =der Grad
> des Kntoen sind/ist.
Vorsicht!
Kanten sind nicht der Grad eines Knotens.
Eine Kante verbindet zwei Knoten miteinander.
Der Grad eines Knotens ist die Anzahl an Kanten, die mit diesem Knoten verbunden sind.
Bei einen gerichteten Graphen kann man da noch zwischen eingehenden Kanten und ausgehenden Kanten unterscheiden.
> Kennt jemand einen Link wo es besser und für Dumme ganz
> leicht erklärt ist?
Leider nein. Ich hoffe, ich konnte es einigermaßen erklären.
LG, Nadine
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:40 Fr 14.11.2008 | | Autor: | Feiratos |
danke für die Antwort,
ja es geht um zusammenhängende Graphen.
Auch vielen Dank für deine Erklären bezüglich Kanten und Grade.
Das würde zum Beispiel Bedeuten, wenn es bei a umd einen Graphen ginge der nicht zusammenhängend wäre, dann könnte ja ein Knoten den Grad 6 haben, weil ja 6 Kanten abgehen könnten ohne dass sie alle auf andere Knoten gehen.
> > Hallo Feiratos! bei b)
> > Jeder Graph hat eine gerade Anzahl von Ecken(Knoten)
> > ungeraden Grades.
> > Folgerung: die Summe der Grade entspricht der doppelten
> > Anzahl der Kanten.
> > Da hierbei die Anzahl der des Grades 19 beträgt, kann
> > das
> > hier kein Graph sein, denn von jeder (natürlichen) Zahl das
> > doppelte ist gerade, und daher nicht 19.
>
> Genau diesen Satz (bzw. dessen Beweis) habe ich nicht
> verstanden
> Daher hierzu keine Antwort.
Na ja, ich habe die Folgerung aus einem Buch entnommen, und habe die Anzahl der Graden addiert=19. Na ja und in der Folgerung zu der Definition:
Jeder Graph hat eine gerade Anzahl von Ecken(Knoten)
ungeraden Grades; steht das die Summe der Graden die doppelte Anzahl der Kanten entspricht. Wenn diese Folgerung stimmt wäre es hier kein Graph, die Kantenzahl mal 2 würde immer zu einer geraden Zahl führen, und nicht zur 19, oder?
>
>
> > Ich hoffe es stimmt so, denn ich komme oft mit den
> > Begriffen Grad Kanten und Ecken Knoten durcheinander.
> > Ist es richtig, dass Knoten=Ecken sind
>
> Wir hatten den Begriff der "Ecke" nicht, aber ich würde
> sagen, dass dem so ist.
>
> > und ich habe eigentlich das Gefühl, da Kanten =der Grad
> > des Kntoen sind/ist.
>
> Vorsicht!
> Kanten sind nicht der Grad eines Knotens.
> Eine Kante verbindet zwei Knoten miteinander.
> Der Grad eines Knotens ist die Anzahl an Kanten, die mit
> diesem Knoten verbunden sind.
> Bei einen gerichteten Graphen kann man da noch zwischen
> eingehenden Kanten und ausgehenden Kanten unterscheiden.
>
Ich verstehe nur nicht wenn Kanten nur Kanten sind, wenn sie zwi Ecken verbinden, wieso nimmst du dann bei der Erklärung zum Grad"Der Grad eines Knotens ist die Anzahl an Kanten, die mit
diesem Knoten verbunden sind." Wieder die Bezeichnung Kante? Wie heissen die Die "Dinger" die von den Knoten abgehen, den Grad mitbestimmen und trotzdem keine Kanten sind :)?
>
LG
|
|
|
| |
|
Hallo Feiratos,
es gibt keine "Dinger", die von einem Knoten abgehen und nirgendwo ankommen und dann auch noch in die Bestimmung des Grades eingehen.
Eine Kante beginnt immer an genau einem Knoten und endet an genau einem Knoten. Das kann allerdings auch der gleiche sein! Dieser Fall wird aber meistens ausgeschlossen.
Es ist leicht zu zeigen, dass die Zahl der Knoten mit ungeradem Grad gerade sein muss. Der Grad ist ja die Zahl der "Kantenenden", die an einem Knoten ankommen. Insgesamt gibt es, wenn k die Zahl der Kanten ist, 2k solche Enden. Genau zu 2k müssen sich also auch die Grade der einzelnen Knoten addieren. Ist nun die Summe aller Knotengrade mit geradem Grad g=2m, so muss die Summe aller Knotengrade mit ungeradem Grad ... auch gerade sein. Das geht aber nur, wenn die Zahl dieser Knoten gerade ist.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:30 Fr 14.11.2008 | | Autor: | Feiratos |
Hallo,
Danke für die Infos, werde ich gleich mal verinnerlichen.
Ich hatte einfach Dinger gesagt, weil es bei der Erklärung so offen stand.
vielen Dank!:)
|
|
|
| |
|
Hallo
> Ich verstehe nur nicht wenn Kanten nur Kanten sind, wenn
> sie zwi Ecken verbinden, wieso nimmst du dann bei der
> Erklärung zum Grad"Der Grad eines Knotens ist die Anzahl an
> Kanten, die mit
> diesem Knoten verbunden sind." Wieder die Bezeichnung
> Kante? Wie heissen die Die "Dinger" die von den Knoten
> abgehen, den Grad mitbestimmen und trotzdem keine Kanten
> sind :)?
Versuche mal, es dir bildlich vorzustellen.
Zeichne für einen Knoten einen Punkt.
Dann zeichne noch ein Punkt.
Nun hast du zwei Knoten: [mm] v_1 [/mm] und [mm] v_2.
[/mm]
Nun kannst du die beiden Knoten mit einer Linie verbinden.
Diese Linie ist eine Kante, nennen wir sie [mm] e_1.
[/mm]
Nun zeichne noch einen Punkt.
Du hast nun einen weiteren Knoten [mm] v_3.
[/mm]
Ziehe nun eine Linie zwischen [mm] v_3 [/mm] und [mm] v_1.
[/mm]
Nun hast du eine zweite Kante, nennen wir sie [mm] e_2.
[/mm]
Sei der ganze Graph nun ein ungerichteter Graph (weißt du was das ist?)
Was ist nun der Grad des Knotens [mm] v_1?
[/mm]
So wie ich dich verstande habe, sind für dich Grad und Kanten das gleiche.
Das ist es nicht.
Eine Kante ist nach Definition ein Paar, das sich aus den beiden Ecken der Kante zusammensetzt, z.B. [mm] e_1=(v_1,v_2).
[/mm]
Ein Grad dagegen ist eine Zahl, nämlich die Anzahl an Kanten, die einen Knoten berühren.
So, nun wieder zum Beispiel.
Der Knoten [mm] v_1 [/mm] wird von zwei Kanten berührt, nämlich von Kante [mm] e_1 [/mm] und Kante [mm] e_2.
[/mm]
Der Grad von [mm] v_1 [/mm] ist also 2.
Der Knoten [mm] v_2 [/mm] wird von einer Kante berührt, nämlich von Kante [mm] e_1.
[/mm]
Der Grad von [mm] v_2 [/mm] ist also 1.
Der Knoten [mm] v_3 [/mm] wird von einer Kante berührt, nämlich von Kante [mm] e_2.
[/mm]
Der Grad von [mm] v_2 [/mm] ist also 1.
> "Dinger" die von den Knoten
> abgehen, den Grad mitbestimmen und trotzdem keine Kanten
> sind
Diese "Dinger gibt es nicht:
Es gibt nur Knoten und Kanten.
Von einem Knoten können nur Kanten abgehen, nichts anderes.
Und die Kanten bestimmen zwar den Grad eines Knotens, aber sie sind nicht der Grad.
Wie gesagt, der Grad ist eine Zahl, und zwar genau die Zahl, die sich ergibt, wenn du die Kanten abzählst, die von einem Knoten abgehen.
Ist es dir nun etwas klarer geworden?
LG, Nadine
|
|
|
|
