graphentheorîe, kreise?

Question

Aufgabe:

angenommen g ist ein vollständîger gvaph mit 20 knoten. wie berechne ich die anzahl von kreisen mit der laenge 3?

Problem/Ansatz:

Ich könnte mir das zeichnen und so herleiten, jedoch wird das schwierig bei sehr großen Knotenmengen. gibt es irgendeine rechnung?

Comments

n Kreise schneiden sich in maximal (n-1)·n Punkten.

5 Kreise schneiden sich in 4·5=20 Punkten. (vermute ich)

Answer 1

Da der Graph vollständig ist, bilden je 3 Knoten einen Kreis der Länge 3.

Also ist die Anzahl solcher Kreise gleich der Anzahl 3-elementiger

Teilmengen einer 20-elementigen Menge, also \(={{20}\choose 3}=1140\)