Natürliche Zahlen/Teilerfremdheitsgraph/Beispiel

Aus Wikiversity
Zur Navigation springen Zur Suche springen

Es sei eine Menge von natürlichen Zahlen. Wir verbinden zwei Zahlen durch eine Kante, wenn diese beiden Zahlen teilerfremd sind. Durch diese Vorschrift entsteht der Teilerfremdheitsgraph. Die ist zu jeder Zahl teilerfremd (auch zu sich selbst, das wird aber hier nicht berücksichtigt, da wir ohne Schleifen arbeiten) und damit mit jeder Zahl durch eine Kante verbunden (wenn die zu gehört), die ist nur zur teilerfremd. Im Komplementärgraph sind zwei Zahlen genau dann miteinander verbunden, wenn sie einen gemeinsamen Teiler haben.