Graphen: Zwei Ungleichungen

19.12.2008, 15:54	axelt	Auf diesen Beitrag antworten »
Graphen: Zwei Ungleichungen Die beiden Ungleichungen gehören zu einer Aufgabe, von der ich die Hälfte gelöst habe und diese Hälfte eben noch nicht. Es bleibt zu zeigen: Sei G=(V,E) ein beliebiger Graph $\begin{eqnarray} \frac{\mid V \mid}{\alpha(G)} \leq \Delta(G)+1 \end{eqnarray}$ $\begin{eqnarray} \frac{\mid V \mid}{\alpha(G)} \leq \chi(G) \end{eqnarray}$ Weil ich nicht weiss ob die Bezeichnungen immer so sind: Alpha = maximal n-stabile Menge Delta = maximaler auftretender Grad Chi = Färbungszahl Als Hinweis ist noch gegeben, dass eine maximale n-stabile Menge und ihre Nachbarschaft betrachtet werden soll (u.a.). Dabei ist mir allerdings nur aufgefallen das sie eben jeweils mit Knoten die nicht zur n-stabilen Menge gehören verbunden oder isoliert sind.
19.12.2008, 17:19	axelt	Auf diesen Beitrag antworten »
Noch eine kurze Frage zu dem Thema: Bedarf die Hilfsaussage "Wenn ein Graph kreisfrei ist, existiert für je zwei Knoten maximal ein x,y-Weg" eines Beweises? Ich meine die ist derart offensichtlich das ich eigentlich sagen würde nein, weil das entspricht ja nun mal eben einem Kreis ;-)
21.12.2008, 22:22	axelt	Auf diesen Beitrag antworten »
Gelöst.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »