图论：含节点全出边的特定环的名称及高效查找算法问询

Great question! Let's break this down into two parts: the naming of these cycles, and efficient algorithms to find them.

Naming the Cycles #

First, there isn't a widely accepted, standard technical term for this specific class of cycles in mainstream graph theory. That said, you can use descriptive names to refer to them clearly in your work:

• For undirected graphs: "Cycles with a fully intra-cycle neighborhood node" (since the node's entire set of neighbors lies within the cycle's node set)
• For directed graphs: "Cycles with a fully intra-cycle out-neighborhood node" (focusing on the node's outgoing edges staying within the cycle)

Some might also refer to the qualifying node as a "closed neighborhood node" relative to the cycle, but this isn't a formal term—just make sure you explicitly define what you mean if you're using these labels in documentation or papers.

Efficient Algorithms (Better Than Random Cycle Checking) #

Randomly finding cycles and verifying the condition is inefficient, especially for large graphs. Instead, we can leverage graph decomposition techniques to target these cycles directly:

For Undirected Graphs

1. Compute Biconnected Components (BCCs)
   Use Tarjan's algorithm (runs in linear time, O(V+E)) to split the graph into its biconnected components. All simple cycles in an undirected graph are contained within BCCs, which are maximal subgraphs where no single node removal can disconnect the component.
2. Identify Qualifying Nodes
   For each BCC:
   • Iterate over every node v in the component.
   • Check if all of v's neighbors (from the original graph) are also in this BCC. This is equivalent to verifying that v's degree in the original graph equals its degree within the BCC.
3. Extract Valid Cycles
   Any simple cycle in the BCC that includes v will satisfy your requirement. Since BCCs are biconnected, you can easily find such a cycle using a modified DFS that tracks paths back to v.

For Directed Graphs

1. Compute Strongly Connected Components (SCCs)
   Use algorithms like Kosaraju's, Tarjan's, or Gabow's (all linear time, O(V+E)) to decompose the graph into SCCs. All directed simple cycles are contained within SCCs, which are maximal subgraphs where every node is reachable from every other node.
2. Identify Qualifying Nodes
   For each SCC:
   • Iterate over every node v in the component.
   • Check if all of v's outgoing edges (from the original graph) point to nodes within this SCC. This means v's out-degree in the original graph equals its out-degree within the SCC.
3. Extract Valid Cycles
   Since the SCC is strongly connected, there must be at least one cycle containing v. You can use algorithms like Johnson's cycle-finding algorithm (optimized for SCCs) or a targeted DFS to find such a cycle quickly.

Quick Optimizations #

• If an undirected BCC is itself a simple cycle (every node has degree 2), every node in the cycle qualifies—so the entire cycle is valid.
• If a directed SCC is a simple directed cycle, every node in the cycle has all outgoing edges within the cycle, so the whole cycle meets your criteria.

内容的提问来源于stack exchange，提问作者Travis Black