Anzahl der Ecken < Topologie+Geometrie < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:10 Mi 15.07.2009 | | Autor: | durden88 |
| Aufgabe | a)In einem Graph ohne Schlinge mit k Kanten und der Eckenmenge [mm] \{E1,...,En\} [/mm] gilt:
y(E1)+y(E2)+y(E3)+....+y(En)=2*k
b) In einem Graphen ohne Schlinge ist die Anzahl der Ecken mit ungerader Ordnung eine gerade Zahl |
Hallo, also zu a) habe ich mir gedacht, ja diese Kante immer von zwei Ecken gebildet ist, also daran stoßt, ist die Aussage wahr (stimmt das denn, also reicht das aus?)
Bei b) habe ich leider keinen Anhaltspunkt :(
Danke schonmla im Vorraus :))
|
|
| |
|
Hallo durden88,
> a)In einem Graph ohne Schlinge mit k Kanten und der
> Eckenmenge [mm]\{E1,...,En\}[/mm] gilt:
>
> y(E1)+y(E2)+y(E3)+....+y(En)=2*k
>
> b) In einem Graphen ohne Schlinge ist die Anzahl der Ecken
> mit ungerader Ordnung eine gerade Zahl
> Hallo, also zu a) habe ich mir gedacht, ja diese Kante
> immer von zwei Ecken gebildet ist, also daran stoßt, ist
> die Aussage wahr (stimmt das denn, also reicht das aus?)
Ja, das ist das sog. Handschlag-Lemma.
Jede Kante wird 2mal gezählt, weil sie mit 2 Knoten inzidiert.
Das hast du also richtig begründet!
>
> Bei b) habe ich leider keinen Anhaltspunkt :(
Na, du weißt nach a), dass die Summe über alle Knotengrade eine gerade Zahl ist (2k).
Wie setzt die sich denn zusammen?
Doch als Summe der ungeraden Knotengrade und der geraden Knotengrade, also ...
>
> Danke schonmla im Vorraus :))
LG
schachuzipus
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:51 Mi 15.07.2009 | | Autor: | durden88 |
Ja genau, also Summe aus den geraden Knotenpunkten und ungeraden Knotenpunkten = 2*k. Kann ich dann einfach minus der gerade Knotenpunkten machen oder wie....blick da noch nicht ganz hinter :) danke
|
|
|
| |
|
Hallo nochmal,
> Ja genau, also Summe aus den geraden Knotenpunkten und
> ungeraden Knotenpunkten = 2*k. Kann ich dann einfach minus
> der gerade Knotenpunkten machen oder wie....blick da noch
> nicht ganz hinter :) danke
Ja, so ähnlich, aber du willst ja auf die Knotenzahl schließen.
Nimm mal an, es gäbe $l$ Knoten mit geradem Knotengrad, dann ist die Summe über all diese Knotengrade halt [mm] $l\cdot{}\text{eine gerade Zahl}$
[/mm]
Das ist - unabh. davon, ob l gerade oder ungerade ist - stets eine gerade Zahl.
Nun kannst du so vorgehen, wie beabsichtigt und "Minus" rechnen, dann hast du, dass die Summe über die ungeraden Knotengrade gerade sein muss, nämlich [mm] $=2k-l\cdot{}\text{eine gerade Zahl}$
[/mm]
Was wäre nun, wenn es ungeradzahlig viele Knoten gäbe, die ungeraden Knotengrad hätten, dann wäre die Summe ...
LG
schachuzipus
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:02 Mi 15.07.2009 | | Autor: | durden88 |
...ist das denn nicht damit schon bewiesen?....ich weiss nicht ganz was du mit der letzten Frage meinst....
danke schonmal
|
|
|
| |
|
Hallo nochmal,
> ...ist das denn nicht damit schon bewiesen?....ich weiss
> nicht ganz was du mit der letzten Frage meinst....
Ja, in etwa, ich wollte auf einen Widerspruch hinaus.
Wenn $m$ die Anzahl der Knoten mit ungerader Knotenzahl ist, so kann $m$ ja gerade oder ungerade sein.
Zeigen sollen wir, dass m gerade ist
Das geht gut indirekt: angenommen, m ist ungerade, dann ist die Summe über alle ungeraden Knotengrade = [mm] $m\cdot{}\text{was ungerades}$.
[/mm]
Das gibt immer eine ungerade Zahl für m ungerade.
Widerspruch, denn:
das darf nach dem, was wir oben festgehalten haben, nicht sein, die Summe über alle ungeraden Knotengrade muss gerade sein, also [mm] $m\cdot{}\text{ungerade Zahl}$ [/mm] muss eine gerade Zahl sein, also muss m gerade sein.
Genau das war zu zeigen
>
> danke schonmal
Gruß
schachuzipus
|
|
|
|
