^Silberschatz, Abraham; Peter Galvin; Greg Gagne. Operating System Concepts. John Wiley & Sons, INC. 2003: 260. ISBN 0-471-25060-0.
^Veblen, Oswald, An Application of Modular Equations in Analysis Situs, 數學年刊, Second Series, 1912, 14 (1): 86–94, JSTOR 1967604, doi:10.2307/1967604.
^Richard M. Karp, Reducibility Among Combinatorial Problems (PDF), R. E. Miller and J. W. Thatcher (编), Complexity of Computer Computations, New York: Plenum: 85–103, 1972 [2020-10-04], (原始内容 (PDF)于2021-02-10).
^Ore, Ø., Note on Hamilton circuits, 美國數學月刊, 1960, 67 (1): 55, JSTOR 2308928, doi:10.2307/2308928.
^Jaeger, F., A survey of the cycle double cover conjecture, Annals of Discrete Mathematics 27 – Cycles in Graphs, North-Holland Mathematics Studies 27: 1–12, 1985, doi:10.1016/S0304-0208(08)72993-1..
十月 18, 2023
圖論, 此條目目前正依照en, cycle, graph, theory, 上的内容进行翻译, 2020年10月4日, 如果您擅长翻译, 並清楚本條目的領域, 欢迎协助翻譯, 改善或校对本條目, 此外, 长期闲置, 未翻譯或影響閱讀的内容可能会被移除, 目前的翻译进度为, 在图论中, 环是一条只有第一个和最后一个顶点重复的非空路徑, 一个没有环的图被称作无环图, 一个没有有向环的有向图被称做有向无环图, 一个无环的连通图被称作树, 一个有向闭路的环, 目录, 定义, 回路, 有向回路, 有向环路, 无弦环, 在图上. 此條目目前正依照en Cycle graph theory 上的内容进行翻译 2020年10月4日 如果您擅长翻译 並清楚本條目的領域 欢迎协助翻譯 改善或校对本條目 此外 长期闲置 未翻譯或影響閱讀的内容可能会被移除 目前的翻译进度为 96 在图论中 环是一条只有第一个和最后一个顶点重复的非空路徑 一个没有环的图被称作无环图 一个没有有向环的有向图被称做有向无环图 一个无环的连通图被称作树 一个有向闭路的环 目录 1 定义 1 1 回路 环 1 2 有向回路 有向环路 2 无弦环 3 在图上探测环 4 用环覆盖图 5 由环刻画的图类别 6 參見 7 參考文獻定义 编辑回路 环 编辑 一个回路是一条非空的路径 其中第一个顶点和最后一个顶点相同 令图G V E displaystyle G V E varnothing nbsp 一个回路是一条非空路径 e 1 e 2 e n displaystyle e 1 e 2 ldots e n nbsp 其顶点序列为 v 1 v 2 v n v 1 displaystyle v 1 v 2 ldots v n v 1 nbsp 一个环路或简单回路是只有第一个与最后一个顶点相同的回路 回路和环的长度是它们经过的边的个数 有向回路 有向环路 编辑 一个有向回路是一个非空的有向路径 其第一个与最后一个顶点相同 令有向图G V E displaystyle G V E varnothing nbsp 一个回路是一条非空有向路径 e 1 e 2 e n displaystyle e 1 e 2 ldots e n nbsp 其顶点序列为 v 1 v 2 v n v 1 displaystyle v 1 v 2 ldots v n v 1 nbsp 一个有向环路 或者简单有向回路 是只有第一个与最后一个顶点重复的有向回路 无弦环 编辑如果环上任意两个顶点都不会被一条不属于环的边相连 则它被称作图中的无弦环或洞 其补被称作反洞 antihole 无弦环可以被用来刻画完美图 英语 Perfect graph 根据强完美图定理 英语 strong perfect graph theorem 一个图是完美图的充要条件是它不存在顶点数为奇数的洞或反洞 弦图是一种特殊的完美图 其不存在顶点数大于等于3的无弦环图的围长是这个图包含的最短的环的长度 根据这个定义 最短环一定是无弦的 笼 英语 Cage graph theory 被定义为给定了围长和度之后的最小的正则图 Peripheral cycle 英语 Peripheral cycle 是图上具有一些特殊性质的环 对任意两个不在环上的顶点 任意连接它们的路径必须经过这个环上的顶点 如果一个图不是由一个环添加一条边构成的 则peripheral cycle一定是导出环 在图上探测环 编辑在有向图和无向图上的环可以被使用深度优先搜索 DFS 的方法 通过寻找一条连接当前顶点与之前顶点的边 它包含了一条后向边 我们可以探测有向图和无向图上环的存在 1 所有DFS跳过的后向边都是某些环的一部分 2 在一个无向图上 指向父节点的边不能被算作后向边 但是找到已经被经过了的顶点意味着后向边的存在 在无向图的情况下 找到一个阶数为n displaystyle n nbsp 图上的环只需要O n 时间 许多拓扑排序算法也会探测环的存在 因为这些环会成为拓扑排序存在的障碍 另外 如果一个有向图被分成了几个强连通分量 那么环只会在这些分量内部存在 而不会连接这几个分量 因为环本身就是强连接的 2 对于有向图 还可以使用基于分布式信息的算法 这些算法的思路基于一条从一个顶点发出的信息可以通过环回到这个顶点 分布式环检测算法对于在计算机集群上使用分布式图处理系统来处理大规模的图很有帮助 环检测的应用包含了使用wait for graph 英语 wait for graph 来检测并行系统中的死锁 3 用环覆盖图 编辑1736年 欧拉证明了对于一个有限无向的图 存在一个环不重复地经过图上的每一条边地充要条件是除了孤立的定点之外 它是连通的 同时每个点的度都是偶数 相对应地 对于一个有向图来说 存在一个闭的漫游 closed walk 不重复地经过图上的每条边的充要条件是这个图是强连接的 并且每个顶点都有相同的出度和入度 在这两个情况下 这个环或漫游被称作欧拉环 如果一个有限的无向图 不论它是否连通 如果其每个顶点的度都是偶数 则可以找到一组简单的环不重复地覆盖每一条边 这被称作Veblen s theorem 英语 Veblen s theorem 4 即使当一个连通图并不满足欧拉定理的条件 我们仍然可以在多项式时间内通过解邮递员问题来找到一个长度最短的闭漫游使其经过每一条边至少一次 在图上找到一个简单的环使其经过不重复地每一个顶点的问题 相比较而言更加困难 这样的环是一个哈密顿环 确定图上是否存在哈密顿环是一个NP完全问题 5 很多研究已经找到了一些种类的图 在它们上一定能够找到哈密顿环 其中的一个例子是奧爾定理 如果图上每一对不相邻的顶点的度之和大于等于图的阶数 则这个图有哈密顿环 6 cycle double cover conjecture 英语 cycle double cover conjecture 可以表述为 对于每个无桥的图 存在一个简单环组成的多重集使得它们一起能够覆盖每一条边恰好两次 目前这个猜想仍未被证明或证伪 7 由环刻画的图类别 编辑有一些重要的图的类型可以被环来刻画和定义 它们包括 二分图 不存在奇数长的环的图 仙人掌圖 英语 Cactus graph a graph in which every nontrivial biconnected component is a cycle 环图 一个环组成的图 弦圖 不存在长度大于3的导出环 induced cycle 的图 有向无环图 a directed graph with no cycles 线完美图 每一个奇数长度的简单环都是一个三角形 完美图 不存在长度大于3的洞 hole 或反洞 antihole Pseudoforest 英语 Pseudoforest a graph in which each connected component has at most one cycle Strangulated graph 英语 Strangulated graph a graph in which every peripheral cycle is a triangle 强连通图 一个有向图 其中每一条边都是环的一部分 無三角形圖 英语 Triangle free graph a graph without three vertex cycles參見 编辑环空间 英语 Cycle space 循環基底 英语 Cycle basis Cycle detection in a sequence of iterated function values參考文獻 编辑 Tucker Alan 英语 Alan Tucker Chapter 2 Covering Circuits and Graph Colorings Applied Combinatorics 5th Hoboken John Wiley amp sons 2006 49 ISBN 978 0 471 73507 6 2 0 2 1 Sedgewick Robert Graph algorithms Algorithms Addison Wesley 1983 ISBN 0 201 06672 6 Silberschatz Abraham Peter Galvin Greg Gagne Operating System Concepts John Wiley amp Sons INC 2003 260 ISBN 0 471 25060 0 Veblen Oswald An Application of Modular Equations in Analysis Situs 數學年刊 Second Series 1912 14 1 86 94 JSTOR 1967604 doi 10 2307 1967604 Richard M Karp Reducibility Among Combinatorial Problems PDF R E Miller and J W Thatcher 编 Complexity of Computer Computations New York Plenum 85 103 1972 2020 10 04 原始内容存档 PDF 于2021 02 10 Ore O Note on Hamilton circuits 美國數學月刊 1960 67 1 55 JSTOR 2308928 doi 10 2307 2308928 Jaeger F A survey of the cycle double cover conjecture Annals of Discrete Mathematics 27 Cycles in Graphs North Holland Mathematics Studies 27 1 12 1985 doi 10 1016 S0304 0208 08 72993 1 取自 https zh wikipedia org w index php title 環 圖論 amp oldid 75883803, 维基百科,wiki,书籍,书籍,图书馆,