Anzahl bestimmen < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
Hallo,
wir haben einen Graph [mm] G_n [/mm] = [mm] (V_n, E_n).
[/mm]
[mm] V_n [/mm] = {1,2,...,n} für alle n [mm] \in \IN^{+} [/mm]
[mm] E_n [/mm] = { {u,v} | u,v [mm] \in V_n \wedge [/mm] 1 [mm] \le [/mm] |u-v| [mm] \le [/mm] 2}
Zu bestimmen ist die Größe [mm] |E_n| [/mm] für alle n [mm] \ge [/mm] 2
Also, ich habe das mal für n = 3 gemacht
Dann haben wir 3 Knoten
nämlich Knoten 1, 2 und 3
Dann ist [mm] E_n [/mm] = { {1,2}, {2,1} , {1,3}, {3,1}, {2,3}, {3,2}}
hat also 6 Elemente für n = 3
n= 7 , also 7 Knoten, hat 22 Elemente , also [mm] |E_n| [/mm] = 22
Wie komme ich hier auf eine vernünftige Formel, sodass ich für beliebige n [mm] \ge [/mm] 2 die Größe von [mm] E_n [/mm] bestimmen kann? Könnte mir bitte jemand einen Denkanstoß geben.
Vielen Dank im Voraus.
|
|
| |
|
Nehmen wir doch das Beispiel [mm]n=7[/mm]. Wir betrachten zunächst [mm](u,v)[/mm] mit [mm]u
(1,2),(1,3)
(2,3),(2,4)
(3,4),(3,5)
(4,5),(4,6)
(5,6),(5,7)
(6,7)
An den rot markierten Zahlen kannst du die Anzahl der Punktepaare zählen. Die Nummerierung geht bis 5, es sind also 2 Paare weniger als die Knotenzahl. Dazu kommt noch ein Single. Es sind somit [mm]5 \cdot 2 + 1 = 11[/mm] Möglichkeiten. Und jetzt kann man die beiden Koordinaten jeweils noch vertauschen. Insgesamt sind es also [mm]2 \cdot 11 = 22[/mm] Möglichkeiten.
Jetzt vom konkreten Fall auf ein allgemeines [mm]n[/mm] abstrahieren.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:01 Do 05.01.2017 | | Autor: | pc_doctor |
Hallo,
perfekt. Ich danke dir für die Antwort.
|
|
|
|
