In der Graph-Theorie kann sich der Begriff Zyklus auf einen geschlossenen Pfad beziehen. Wenn wiederholten Scheitelpunkten erlaubt wird, wird es öfter einen geschlossenen Spaziergang genannt. Wenn der Pfad ein einfacher Pfad, ohne wiederholte Scheitelpunkte oder Ränder außer dem Starten und Ende von Scheitelpunkten ist, kann es auch einen einfachen Zyklus, Stromkreis, Kreis oder Vieleck genannt werden; sieh Zyklus-Graphen. Ein Zyklus in einem geleiteten Graphen wird einen geleiteten Zyklus genannt.

Der Begriff Zyklus kann sich auch beziehen auf:

• Ein Element der Dualzahl oder des Integrals (oder echt, kompliziert, usw.) Zyklus-Raum eines Graphen. Das ist der Gebrauch, der daran im Rest der Mathematik in der besonderen algebraischen Topologie am nächsten ist. Solch ein Zyklus kann einen binären Zyklus, integrierten Zyklus usw. genannt werden.
• Ein Rand ist untergegangen, der sogar Grad an jedem Scheitelpunkt hat; auch genannt einen gleichen Rand geht unter oder, wenn genommen, zusammen mit seinen Scheitelpunkten, einem gleichen Subgraphen. Das ist zu einem binären Zyklus gleichwertig, da ein binärer Zyklus die Anzeigefunktion eines Rand-Satzes dieses Typs ist.

Zyklen von Chordless in einem Graphen werden manchmal Graph-Löcher genannt. Ein Graph-Antiloch ist die Ergänzung eines Graph-Loches.

Zyklus-Entdeckung

Ein ungeleiteter Graph hat einen Zyklus, wenn, und nur wenn eine Tiefensuche (DFS) einen Rand findet, der zu einem bereits besuchten Scheitelpunkt (ein Zurückrand) hinweist.

Gleichwertig sind alle Zurückränder, der DFS-Hopser, ein Teil von Zyklen. Im Fall von ungeleiteten Graphen, nur O (n) Zeit ist erforderlich, seitdem am grössten Teil von n  1 Ränder kann Baumränder sein (wo n die Zahl von Scheitelpunkten ist).

Ein geleiteter Graph hat einen Zyklus, wenn, und nur wenn ein DFS einen Zurückrand findet. Schicken Sie nach und treffen Sie sich Ränder zeigen Zyklen nicht notwendigerweise an. Viele topologische Sortieren-Algorithmen werden Zyklen auch entdecken, da diejenigen Hindernisse für die topologische Ordnung sind zu bestehen. Außerdem, wenn ein geleiteter Graph in stark verbundene Bestandteile geteilt worden ist, bestehen Zyklen nur innerhalb der Bestandteile und nicht zwischen ihnen, da Zyklen stark verbunden werden.

Siehe auch

• Zyklus von Euler
• Zyklus von Hamiltonian
• Graph von Chordal