Wie beweist man, dass jeder einfache, ungerichtete Graph mit … zusammenhängend ist?

Question

Hallo , 

ich brauch mal wieder Hilfe, diesmal aus dem Bereich der Graphentheorie. 

Ich hab leider keine Ahnung wie man das machen soll, da ich das Thema selber noch nicht ganz verstanden habe. 

Hier die Aufgabe

Ich hoffe mir kann jemand helfen diese Aufgabe zu lösen. :))

Comments

Hast du schon nachgeschaut, was mit V(G) gemeint ist? 

---

nein, leider nicht. ich habe absolut gar keine Ahnung oder Idee. :(

---

G= (V , E) 

E dürfte Englisch für edge stehen. 

Graphen bestehen aus Kanten und Knoten. Eines davon ist "edge", das andere "v..." .

Versuche es mal über ein Wörterbuch oder die englische Wikipedia (Stichwort: Graph) 

|V(G)| ist dann die Anzahl der v... des Graphen. 

https://en.wikipedia.org/wiki/Graph_(discrete_mathematics)#Definitio…

und dazu im Vergleich https://de.wikipedia.org/wiki/Graph_(Graphentheorie)#Definitionen 

Answer 1

Na ja - man kann sich z.B. fragen, wie viele Kanten ein einfacher ungerichteter Graph maximal haben kann und wieviele Kanten man davon mindestens wegnehmen muss, damit er nicht mehr zusammenhängend ist. Umgekehrt kann man dann sagen, dass ein Graph, der mehr Kanten hat, als diese oben beschriebene Anzahl, immer zusammenhängend sein muss.

Denk' mal selber nach und drücke nicht sofort auf den 'Spoiler'.

Wenn jeder Knoten mit jedem anderen über eine Kante verbunden ist, so hat der Graph $E_{\max}$ Kanten.
$$E_{\max}(|V(G)|=1) = 0$$$$E_{\max}(|V(G)|=2) = 1$$$$E_{\max}(|V(G)|=3) = 3$$$$E_{\max}(|V(G)|=n) = E_{\max}(|V(G)|=n-1) + n$$ $$E_{\max}(|V(G)|=n) = \frac{n}{2}(n-1)$$

Man muss also von einem Graphen mit $E_{\max}$ Kanten mindestens $|V(G)|-1$ Kanten entfernen - nämlich alle, die zu genau einem Knoten führen - um diesen einen Knoten zu isolieren. Die Anzahl $E_{\text{krit.}}$ der verbleibenden Kanten ist dann

$$E_{\text{krit.}} = \frac12 \left( |V(G)| - 1 \right) \left( |V(G)| - 2 \right) = \frac{ \left( |V(G)| - 1 \right)! }{\left( |V(G)| - 3 \right)! \cdot 2!} = \binom{ |V(G)| - 1}{2}$$

hat ein Graph $G$ mehr Kanten als $E_{\text{krit.}}$ so ist es zwangsläufig ein zusammen hängender.

Comments

vielen Dank für die Hilfe aber so richtig verstanden habe ich das trotzdem noch nicht richtig 

---

Welche Zeile verstehst du denn nicht? 

---

... es wäre extrem hilfreich für DICH, wenn Du uns mitteilst, was Du nicht verstanden hast.

$|V(G)|$ ist die Anzahl der Knoten im Graph $G$. $V$ kommt von vertex engl. 'Ecke'. In meiner Antwort ist $E$ die Anzahl der Kanten des Graphs $G$. $E$ kommt von edge engl. 'Kante'. 

Und  $E_{\max}(|V(G)|)$ ist die maximal mögliche Anzahl der Kanten in Abhängigkeit der Anzahl der Knoten.

---

Hallo Werner-Salamon,

kannst du für ein besseres Verständnis nochmal erklären, wie du von E_\text{krit.} = \frac{ \left( |V(G)| - 1 \right)!  }{\left( |V(G)| - 3 \right)! \cdot 2!} \text{ auf } = \binom{ |V(G)| - 1}{2} gekommen bist?

---

Sry, ich meinte das hier: Kannst du die Umformung nochmal genau erklären bzw. wie man auf die Anzahl der verbliebenden Kanten kommt?

---

Das ist eine Definition des Binomialkoeffizienten (findest du z.B. in Wikipedia). 

---

Bitte. Und Dank an Werner-Salomon! 

---

Ja, genau - danke für den schönen Beweis!