Cycle (graph theory)とは 意味・読み方・使い方

In graph theory, the term cycle may refer to several closely related objects.

• A closed walk, with repeated vertices allowed. See path (graph theory). (This usage is common in computer science. In graph theory it is more often called a closed walk.)
• A closed (simple) path, with no other repeated vertices or edges than the starting and ending vertices. (This usage is common in graph theory, see "Cycle graph") This may also be called a simple cycle, circuit, circle, or polygon.
• A closed directed walk, with repeated vertices allowed. (This usage is common in computer science. In graph theory it is more often called a closed directed walk.)
• A closed directed (simple) path, with no repeated vertices other than the starting and ending vertices. (This usage is common in graph theory.) This may also be called a simple (directed) cycle.
• The edge set of an undirected closed path without repeated vertices or edges. This may also be called a circuit, circle, or polygon.
• An element of the binary or integral (or real, complex, etc.) cycle space of a graph. (This is the usage closest to that in the rest of mathematics, in particular algebraic topology.) Such a cycle may be called a binary cycle, integral cycle, etc.
• An edge set that has even degree at every vertex; also called an even edge set or, when taken together with its vertices, an even subgraph. This is equivalent to a binary cycle, since a binary cycle is the indicator function of an edge set of this type.