0 Daumen
2,4k Aufrufe

Graphen, Knotenmenge usw bestimmen

 

Aufgabe 4: Graphen 3 + 3 + 2 Punkte

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)?

b) Wieviele Knoten und wieviele Kanten haben die Graphen H1 und H2. Wieviel Kanten hat der Graph Hn allgemein (kurze Begründung)?

c) Welche Durchmesser haben die Grahen Gn und H n?
 

Avatar von
Ich möchte mal vorsichtig darauf hinweisen, dass wir nicht hier sind, um deine Hausaufgaben zu machen, sondern um bei grundlegenden Problemen zu helfen. Was du hier gerade alles postest, geht weit über Grundlagen hinaus.

Ich weiß nicht, wo diese ganzen Aufgaben herkommen, aber falls du etwas in die Richtung studierst, dann solltest du dir vielleicht Gedanken machen, ob es für dich das richtige ist - wenn du das nur aus Interesse machst, dann sage ich dir, dass gerade das Rechnen der Aufgaben das entscheidende ist, um zu prüfen, ob du etwas verstanden hast.

(Noch dazu ist das so ein Wust aus unterschiedlichen Themen, die mir zusätzlich völlig fern sind, dass ich langsam keine Lust mehr hab, mir ständig irgendwelche Wikipedia-Artikel durchzulesen, um eine Ahnung von den Themen zu haben, nach denen du fragst, aber das ist ja mein persönliches Problem ;-)
Nee, das sind Klausuraufgaben, bei dem ich versuche sie zu lösen.

Ich brauche nur ansätze, sonst nichts. Wenn ich meine Ansätze poste. dann ist das viel schreibarbeit und es wird full
Das sind eigentlich die einzigen. ich habe vielleicht aufeinaml alles gepostet.

Ich würde mich freuen wenn ihr mir helfen würdet

Danke

1 Antwort

+1 Daumen
 
Beste Antwort

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?

Avatar von 162 k 🚀
Sehr gut und sehr ausführlich erklärt

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community