Graphentheorie: Gradfolge

02.05.2009, 11:23	eierkopf1	Auf diesen Beitrag antworten »
Graphentheorie: Gradfolge Hallo! Folgendes Beispiel: "Sei die Gradfolge eines Graphen in monotoner Weise $\begin{eqnarray} d_1 \geq d_2 \geq \dots \geq d_n \end{eqnarray}$ gegeben. Zeige, dass $\begin{eqnarray} \sum_{i=1}^k d_i \leq k(k - 1) + \sum_{ j=k+1}^n \min(d_j , k) \end{eqnarray}$ für alle k gilt." Hinweis: Betrachte die Anzahl der Kanten zwischen den ersten k Ecken und dem Rest. " Ich habe mir ein paar Beispiel angeschaut und auch den Hinweis betrachtet. Was ich weiß: $\begin{eqnarray} \sum_{i=1}^n d_i = 2 \|E\| \end{eqnarray}$ Auch weiß ich, dass die Anzahl der ungeraden Grade gerade ist bei einem Graph. Jedoch habe ich keine Idee, wie ich das lösen könnte. Wie mache ich das?
02.05.2009, 13:20	Abakus	Auf diesen Beitrag antworten »
RE: Graphentheorie: Gradfolge Eine Lösung hab ich noch nicht, aber was passiert denn, wenn du die ersten k Ecken (ggf. als Teilgraph) betrachtest? Grüße Abakus
02.05.2009, 14:03	eierkopf1	Auf diesen Beitrag antworten »
RE: Graphentheorie: Gradfolge Die ersten Ecken haben die größten Grade und es müssen min. $\begin{eqnarray} d_1 + 1 \end{eqnarray}$ Ecken betrachtet werden, damit es überhaupt einen Graphen mit dieser Gradfolge geben kann. Aber mehr fällt mir dazu auch nicht ein.
02.05.2009, 20:15	AD	Auf diesen Beitrag antworten »
An sich gibt es nicht die geringsten Schwierigkeiten. Vielleicht ist alles nur eine Frage des geschickten Aufschreibens: Betrachten wir $\begin{eqnarray} a_{ij} = \begin{cases} 1 & \;\mbox{es existiert Kante $(i,j)$} \\ 0 & \;\mbox{sonst} \end{cases} \end{eqnarray}$ , dann ist $\begin{eqnarray} a_{ii}=0 \end{eqnarray}$ , $\begin{eqnarray} a_{ij} = a_{ji} \end{eqnarray}$ sowie $\begin{eqnarray} d_i = \sum_{j=1}^n a_{ij} \end{eqnarray}$ . Jetzt kannst du unter Beachtung des Hinweises abschätzen: $\begin{eqnarray} \sum_{i=1}^k d_i = \sum_{i=1}^k \sum_{j=1}^n a_{ij} = \sum_{i=1}^k \left( \sum_{j=1}^k a_{ij} + \sum_{j=k+1}^n a_{ij} \right) \leq \sum_{i=1}^k \left( k-1 + \sum_{j=k+1}^n a_{ji} \right) = k(k-1) + \sum_{j=k+1}^n \sum_{i=1}^k a_{ji} \leq k(k-1) + \sum_{j=k+1}^n \min(k,d_j) \end{eqnarray}$ . Die Voraussetzung $\begin{eqnarray} d_1 \geq d_2 \geq \dots \geq d_n \end{eqnarray}$ wird also gar nicht gebraucht - mag aber sein, dass die Anwendung dieser Ungleichung für diesen Fall besonders Sinn macht.
03.05.2009, 01:13	eierkopf1	Auf diesen Beitrag antworten »
Danke für diese sehr elegante Lösung! Echt bewundernswert

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »