Wir betrachten die Graphen Gn und Hn ‚ deren Knotenmenge alle n-stelligen Dezimalzahlen (erste Stelle ungleich Null) sind.
Zwei Zahlen sind adjazent in Gn ‚ wenn sie sich an genau einer Stelle unterscheiden.
Zwei Zahlen sind adjazent in Hn ‚ wenn sie sich an genau einer Stelle unterscheiden und der Unterschied zwischen den beiden Ziffern an dieser Stelle genau Eins ist.
a) Wieviele Knoten und wieviele Kanten haben die Graphen G1 und G2. Wieviel Kanten hat der Graph Gn allgemein (kurze Begründung)?
1-stellig sind die Zahlen 1 bis 9.
G1 jede Zahl unterscheidet sich von jeder andern an genau einer Stelle.
Also: (9 tief 2) = 9*8/2 = 36 Kanten.
2-stellig sind die Zahlen 10 bis 99. Also 90 Zahlen
G2
Kanten gehen von 10 nach 11,12,13,14,…19 und nach 20,30,40,50,…90. von 10 aus 17 (=9+8) Kanten.
Kanten gehen von 36 nach 30,…35,37,38,39 und nach 16,26,46,56,…96. von 36 aus 17 (=9+8) Kanten.
Von jedem Knoten aus 17 Kanten. Alle werden doppelt gewählt. Daher 90*17/2 = 765 Kanten.
n-stellig sind 10^n - 10^{n-1} Zahlen.
Gn
Von jedem Knoten aus gehen 8 + (n-1)*9 = 9n-1 Kanten
Alle werde so doppelt gewählt (hin und zurück) Also Total (10^n - 10^{n-1})*(9n-1)) /2 Kanten
b) Wieviele Knoten und wieviele Kanten haben die Graphen H1 und H2. Wieviel Kanten hat der Graph Hn allgemein (kurze Begründung)?
Zwei Zahlen sind adjazent in Hn ‚ wenn sie sich an genau einer Stelle unterscheiden und der Unterschied zwischen den beiden Ziffern an dieser Stelle genau Eins ist.
1-stellig sind die Zahlen 1 bis 9.
H1
Kanten von 1 aus: nach 2. Also eine!
Kanten von 2 aus: nach 1 und nach 3. Also 2!
immer 2 bis
Kanten von 9 aus: nach 8. Also eine!
Total: (7*2 + 2)/2 = 8 Kanten
2-stellig sind die Zahlen 10 bis 99. Also 90 Zahlen
H2
Kanten gehen von 10 nach 11 und nach 20.------> von 10 aus 2 Kanten.
Kanten gehen von 11 nach 10,12 und nach 21. ------->von 11 aus 3 Kanten.
Kanten gehen von 19 nach 18 und nach 29. → von 19 aus 2 Kanten.
Kanten gehen von 20 nach 21 und nach 10,30. → von 20 aus 3 Kanten.
von 21 aus 4 Kanten.
…
von 29 aus 3 Kanten
von 30 aus 3 Kanten
von 31 aus 4 Kanten
von 90 aus 2 Kanten
von 91 aus 3 Kanten
…
von 98 aus 3 Kanten
von 99 aus 2 Kanten
Von allen mindestens 2 Kanten: 2*90
genau 2 Kanten von 10 , 19, 90 und 99 also von 4 Knoten aus
genau 3 Kanten von 11 bis 18 und 20, 29,30,39,40,49,50,59,60,69,70,79,80,89, 91…98
also von 8 + 14 +8 = 30 Knoten aus
genau 4 Kanten von 7*8 = 56 Knoten aus
Total: (2*90 + 1*30 + 2*56)/2 = 161 Kanten
n-stellig sind 10^n - 10^{n-1} Zahlen.
Hn
Hierzu fällt mir im Moment keine einfache Berechnung ein.
c) Welche Durchmesser haben die Grahen Gn und H n?
Was ist genau der Durchmesser eines Graphen?
