Minimalgrad

02.05.2010, 17:36

RsSaengerin

Minimalgrad

Hallo Leute,
folgende Frage:

Für ungerichtete Graphen G=(V,E) mit Grad deg v ( v € V) und Untergraphen H gilt:

$\begin{eqnarray*} \epsilon (G) = |E| / |V| \end{eqnarray*}$
und
$\begin{eqnarray*} \delta (G) = min{deg_v} \end{eqnarray*}$

zu zeigen ist dann:
$\begin{eqnarray*} \delta (H) > \epsilon (H) \geq \epsilon (G) \end{eqnarray*}$

Ich nehme an, indultiv hat das nicht viel Sinn weil man zwschen zu vielen Dingen differenzieren muss...oder?

Ein kleiner Gedankenanstoß, wie ich rangehen kann, wäre nett smile

03.05.2010, 17:43

Dummling

Auf diesen Beitrag antworten »

RE: Minimalgrad
Hi!

Meinem Verständnis nach müsse die letzte Ungleichung schon anders herum gelten:
$\begin{eqnarray*} \epsilon (H) := |E_H|/|V| \leq |E_G|/|V| =: \epsilon (G) \end{eqnarray*}$ mit $\begin{eqnarray*} E_H \subseteq E_G \end{eqnarray*}$

Dummling

Edit: Das gilt natürlich nur, wenn beim Subgraphen die Knotenmenge unangefasst bleibt.

03.05.2010, 17:55

Dummling

Auf diesen Beitrag antworten »

Nachtrag: Deine Ungleichung ist (im hinteren Teil) falsch.

Betrachte z. B. den $\begin{eqnarray*} K^4 \end{eqnarray*}$ und $\begin{eqnarray*} K^3 \subset K^4 \end{eqnarray*}$ . Hier gilt $\begin{eqnarray*} \epsilon(K^4)=\frac{6}{4} \geq \epsilon(K^3)=\frac{3}{3} \end{eqnarray*}$ .

03.05.2010, 18:19

Dummling

Auf diesen Beitrag antworten »

...und für einen Graphen G gilt doch:
$\begin{eqnarray*} 2 \cdot |E| = \sum\limits_{v \in V} deg(v) \geq |V| \cdot \delta(G) \Leftrightarrow \epsilon(G) = \frac{|E|}{|V|} \geq \frac{\delta(G)}{2} \end{eqnarray*}$

Vielleicht hilft dir das weiter?

03.05.2010, 23:35

RsSaengerin

Auf diesen Beitrag antworten »

nein hilft nicht, aber trotzdem danke ^^

konnte es mitlerweile auch schon allein lösen :-)

04.05.2010, 10:08

Dummling

Auf diesen Beitrag antworten »

Zitat:

Original von RsSaengerin
konnte es mitlerweile auch schon allein lösen :-)

Nämlich wie?

Habe ich einen Denkfehler in meinem obigen Widerspruch oder hast du dich einfach bei den Ungleichheitszeichen geirrt?

Dummling

Neue Frage »

Antworten »

Minimalgrad

Verwandte Themen