Anzahl der Knoten und Kanten eines Graphen

15.02.2016, 00:24	FaithNoMore	Auf diesen Beitrag antworten »
Anzahl der Knoten und Kanten eines Graphen Meine Frage: Hallo Eine Übungsaufgaben aus unserem Mathetutorium bereitet mir ziemlich Kopfschmerzen, da ich überhaupt nichts so recht damit anzufangen weiß: Es sei $\begin{eqnarray} n \in \mathbb N \end{eqnarray}$ mit $\begin{eqnarray} n \geq 2 \end{eqnarray}$ . Der Graph $\begin{eqnarray} H_n \end{eqnarray}$ sei wie folgt definiert: Die Knotenmenge von $\begin{eqnarray} H_n \end{eqnarray}$ sei die Menge aller n-Tupel $\begin{eqnarray} (x_1, ... ,x_n) \end{eqnarray}$ mit $\begin{eqnarray} x_i \in \{0,1,2\} \end{eqnarray}$ (für $\begin{eqnarray} i = 1, ... , n \end{eqnarray}$ ). Zwei Knoten seien genau dann durch eine Kante verbunden, wenn sie sich an genau 2 Stellen unterscheiden. a) Wie viele Knoten besitzt der Graph $\begin{eqnarray} H_n \end{eqnarray}$ ? b) Wie viele Kanten besitzt der Graph $\begin{eqnarray} H_n \end{eqnarray}$ ? Meine Ideen: Ich weiß gar nicht so recht, wie ich hier herangehen soll. In der Musterlösung steht für a) einfach nur die Lösung $\begin{eqnarray} 3^n \end{eqnarray}$ , aber woher weiß ich das eigentlich? Ich wäre sehr dankbar, wenn jemand Licht ins Dunkle bei mir bringen könnte. Es wurmt mich sehr, dass ich hierzu keinen Ansatz finde.
16.02.2016, 10:48	RavenOnJ	Auf diesen Beitrag antworten »
RE: Anzahl der Knoten und Kanten eines Graphen zu a) Wieviele maximal n-stellige Zahlen >= 0 gibt es im Zahlensystem zur Basis 3? zu b) Was ist der Grad eines Knotens $\begin{align} (x_1,x_2,x_2) \end{align}$ ? Dies kann man hier schon durch Abzählen lösen. Besser wäre natürlich eine kombinatorische Lösung. PS: Was hat die Aufgabe mit Numerik zu tun?

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »