Würfefgraph, Anzahl Kanten < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
Hallo,
im Skript wird der Beweis so geführt:
Mit |V(Qn)| = [mm] 2^n [/mm] folgt: (steht im Skript)
2|E(Qn)| = [mm] \summe_{v \in V(Qn)} [/mm] deg(v) = [mm] \summe_{v \in V(Qn)} [/mm] n
= [mm] 2^n [/mm] * n
|E(Qn)| = n * [mm] 2^{n-1}
[/mm]
Im Skript ist auch: 2|E(Qn)| = [mm] \summe_{v \in V(Qn)} [/mm] deg(v) gegeben, kann man dann nicht einfach sagen:
Die Anzahl der Karten eines Würfel Qn ist:
[mm] \bruch{\summe_{v \in V(Qn)} deg(v)}{2} [/mm] ?
|
|
| |
|
Hallo studentxyz!
> Hallo,
>
> im Skript wird der Beweis so geführt:
>
>
> Mit |V(Qn)| = [mm]2^n[/mm] folgt: (steht im Skript)
> 2|E(Qn)| = [mm]\summe_{v \in V(Qn)}[/mm] deg(v) = [mm]\summe_{v \in V(Qn)}[/mm]
> n
> = [mm]2^n[/mm] * n
>
> |E(Qn)| = n * [mm]2^{n-1}[/mm]
>
>
>
> Im Skript ist auch: 2|E(Qn)| = [mm]\summe_{v \in V(Qn)}[/mm] deg(v)
> gegeben, kann man dann nicht einfach sagen:
>
> Die Anzahl der Karten eines Würfel Qn ist:
>
> [mm]\bruch{\summe_{v \in V(Qn)} deg(v)}{2}[/mm] ?
Ja, das kann man sagen, da ganz allgemein für die Anzahl $|E|$ der Kanten eines endlichen Graphen $G = (V,E)$ gilt, dass [mm] $|E|=\frac{1}{2}\sum\limits_{v\in V} \text{deg}(v)$ [/mm] ist.
Für die Anzahl der Kanten eines $n$-dimensionalen Würfels [mm] $Q_n [/mm] = [mm] (V(Q_n),E(Q_n))$, [/mm] kann man zusätzlich ausnutzen, dass eine beliebige Ecke [mm] $v\in V(Q_n)$ [/mm] den Grad [mm] $\text{deg}(v) [/mm] = n$ hat und dass [mm] $V(Q_n) [/mm] = [mm] 2^n$ [/mm] ist.
LG mathfunnel
|
|
|
| |
|
Ok, danke.
Wo wir gerade beim Thema sind, wie zeigt man das ein Würfelgraph zusammenhängend ist?
|
|
|
| |
|
Hallo studentxyz!
> Ok, danke.
>
> Wo wir gerade beim Thema sind, wie zeigt man das ein
> Würfelgraph zusammenhängend ist?
Betrachte für $n>1$ zwei geeignete Untergraphen eines $n$-dimesionalen Würfels, die $n-1$-dimesionale Würfel sind.
LG mathfunnel
|
|
|
| |
|
> Hallo studentxyz!
>
> > Ok, danke.
> >
> > Wo wir gerade beim Thema sind, wie zeigt man das ein
> > Würfelgraph zusammenhängend ist?
>
> Betrachte für [mm]n>1[/mm] zwei geeignete Untergraphen eines
> [mm]n[/mm]-dimesionalen Würfels, die [mm]n-1[/mm]-dimesionale Würfel sind.
Wenn ich anstatt Q3 Q2 betrachte sehe ich zwar wieder das er zusamenhängend ist, aber ein Beweiss fällt mir dazu nicht sein :(
|
|
|
| |
|
> > Hallo studentxyz!
> >
> > > Ok, danke.
> > >
> > > Wo wir gerade beim Thema sind, wie zeigt man das ein
> > > Würfelgraph zusammenhängend ist?
> >
> > Betrachte für [mm]n>1[/mm] zwei geeignete Untergraphen eines
> > [mm]n[/mm]-dimesionalen Würfels, die [mm]n-1[/mm]-dimesionale Würfel sind.
>
>
> Wenn ich anstatt Q3 Q2 betrachte sehe ich zwar wieder das
> er zusamenhängend ist, aber ein Beweis fällt mir dazu
> nicht sein :(
Führe den Beweis durch vollständige Induktion !
[mm] Q_0 [/mm] ist (als trivialer Graph mit einer einzigen Ecke
und keiner Kante) zusammenhängend. Zeige dann,
dass für n>0 der Graph [mm] Q_n [/mm] stets zwei disjunkte,
zueinander (und zu [mm] Q_{n-1}) [/mm] isomorphe Untergraphen hat,
welche (nach Induktionsvoraussetzung) zusam-
menhängend sind und (in [mm] Q_n) [/mm] miteinander verbunden
sind (nämlich durch je eine Kante zwischen zwei
sich in der Isomorphie entsprechenden Punkten).
Durch diese Betrachtung kommt man nebenbei auch
noch zur Darstellung:
$\ [mm] |E(Q_n)|\ [/mm] =\ [mm] 2*|E(Q_{n-1})|+|V(Q_{n-1})|$
[/mm]
LG Al-Chw.
|
|
|
|
