FindCycle

FindCycle[g]

找出图 g 的一个圈.

FindCycle[g,k]

找出图 g 中长度最多为 k 的圈.

FindCycle[g,{k}]

找出长度恰好为 k 的圈.

FindCycle[g,{kmin,kmax}]

找出长度介于 kmin 和 kmax 之间的圈.

FindCycle[g,kspec,s]

找出最多 s 个圈.

FindCycle[{g,v},…]

找出包含顶点 v 的圈.

FindCycle[{vw,…},…]

用规则 vw 指定图 g.

更多信息

  • 圈也被称为环路或循环.
  • 圈是由除了起止顶点之外无重复的顶点或边组成的路径.
  • FindCycle 会给出圈的列表. 每个圈都以边的列表的形式给出.
  • 若没有圈则 FindCycle 会返回一个空列表.
  • FindCycle[g,kspec,All] 会找出所有的圈.
  • 对于加权图，FindCycle[g,k] 会给出所有总权重小于 k 的圈.
  • FindCycle 适用于无向图、有向图和多重图.

背景

  • FindCycle 试图找出图中的一个或多个不同的圈. 圈以一系列边列表的形式返回，若不存在任何圈则返回 {}. 图的圈（若该圈被显式路径标明且路径由特定端点组成，则更适合被称为环路）是由不同边组成的一个连续序列，头尾两条边的端点是重合的. 圈的枚举可用于规划许多情况下的环路（地铁、公路旅行等等），计算电子电路中的电压或电流，或者发现计算机程序中的无限循环.
  • 一般来说，FindCycle[g,kspec,s] 试图找出 s 个长度为 kspec 的圈. 计数要求 s 可以被省略（在这种情况下它取值为 1），可以是一个正整数，或者是 All. 长度要求 kspec 可以是一个正整数 k（在这种情况下它表示圈长度小于或等于 k），可以是 Infinity，可以是有一个正整数的列表 {k}（在这种情况下它表示圈长度正好等于 k），或者是有两个正整数的列表 {kmin,kmax}（在这种情况下它表示圈长度从 kmin 到 kmax）.
  • 对于 FindCycle[g,{3}] 返回 {} 的图被称为无三角形图；对 FindCycle[g,{4}] 返回 {} 的图被称为无正方形图. 长度为 n 的环被称为哈密顿环，其中 n 是图的顶点数，拥有这种环的图被称为哈密顿图.
  • 不包含任何圈的图被称为无圈图并可用 AcyclicGraphQ 检测.
  • FindCycle 返回的是简单的圈，而 FindHamiltonianCycle、FindEulerianCycle 和 FindFundamentalCycles 返回的是特殊类型的圈. FindPath 可被用于寻找两个指定顶点之间的路径（两端端点不重合的边的集合），返回值是沿着路径的连续顶点组成的集合.

范例

打开所有单元关闭所有单元

基本范例  (2)

找出图的一个圈：

突出显示该圈：

找出图中所有的圈：

范围  (12)

Specification  (6)

FindCycle 适用于无向图：

有向图：

加权图：

多重图：

用规则指定图：

FindCycle 适用于大型图：

Enumeration  (6)

长度恰好为8的圈：

长度最多为6的圈：

长度介于3和5之间的圈：

包含给定顶点的圈：

找出所有的圈：

若没有圈 FindCycle 会给出空列表：

应用  (4)

找出经过每个顶点恰好一次的哈密尔顿圈：

显示这个圈：

找出带有给定性质的圈：

包含一个顶点：

包含一条边：

找出韩国釜山地铁的最长环线：

最长环线的长度：

找出该环线：

计划遛狗的路线：

对给定的起始结点，找出5条长度至少是20的避开有坏狗的街道的路线：

属性和关系  (3)

用 FindHamiltonianCycle 找出访问每个顶点恰好一次的圈：

等价于：

EdgeCycleMatrix 给出了所有的圈的基：

构造全部的圈：

从 FindCycle 找出全部的圈：

FindCycle 对无向图给出空列表：

可能存在的问题  (1)

FindCycle 忽略了自圈：

Wolfram Research (2014)，FindCycle，Wolfram 语言函数，https://reference.wolfram.com/language/ref/FindCycle.html （更新于 2015 年）.

文本

Wolfram Research (2014)，FindCycle，Wolfram 语言函数，https://reference.wolfram.com/language/ref/FindCycle.html （更新于 2015 年）.

CMS

Wolfram 语言. 2014. "FindCycle." Wolfram 语言与系统参考资料中心. Wolfram Research. 最新版本 2015. https://reference.wolfram.com/language/ref/FindCycle.html.

APA

Wolfram 语言. (2014). FindCycle. Wolfram 语言与系统参考资料中心. 追溯自 https://reference.wolfram.com/language/ref/FindCycle.html 年

BibTeX

@misc{reference.wolfram_2024_findcycle, author="Wolfram Research", title="{FindCycle}", year="2015", howpublished="\url{https://reference.wolfram.com/language/ref/FindCycle.html}", note=[Accessed: 18-November-2024 ]}

BibLaTeX

@online{reference.wolfram_2024_findcycle, organization={Wolfram Research}, title={FindCycle}, year={2015}, url={https://reference.wolfram.com/language/ref/FindCycle.html}, note=[Accessed: 18-November-2024 ]}