知识卡片
邻接描述顶点关系关联描述端点
图可记G=(V,E),V为顶点集、E为边关系。有向边(u,v)从u指向v,意味着从u可直接走到v,反向不一定成立;无向边两端地位对称,一条边不需要当成两条不同的数学边。
邻接是顶点之间的直接关系;关联描述顶点与边的端点关系。有向顶点入度统计终点为它的边,出度统计起点为它的边;无向度统计与之相接的边(含自环时须另按约定计数)。
02913中1→2并不同时有2→1,2与3则双向相邻。完全无向图要求任意两个不同顶点直接相邻;不能把能经路径到达当直接邻接。本书无向例不含自环,但一般无向模型并非一律禁止自环,须说明是否限定简单图。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
邻接(adjacency)和关联(incidence)。邻接是两个顶点之间的一种关系。如果图包含边(u,v),则称顶点v与顶点u邻接。在无向图中,这也暗示了顶点u也与顶点v邻接。换句话说,在无向图中邻接关系是对称的。而在有向图中则并非如此。比如,在图11-1a中,顶点2与顶点1相邻接,但顶点1并不与
参考来源
- 位置:《算法精解:C语言描述》第11章《图的描述》(spine1321;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1288.html;u186-ch11-006)。
- 结论依据:186正式G/V/E、有向/无向、邻接/关联/度全部段落和02913两图实读;保留方向与对象层次,纠正无向一概无自环的泛化。
- 原始内容:邻接(adjacency)和关联(incidence)。邻接是两个顶点之间的一种关系。如果图包含边(u,v),则称顶点v与顶点u邻接。在无向图中,这也暗示了顶点u也与顶点v邻接。换句话说,在无向图中邻接关系是对称的。而在有向图中则并非如此。比如,在图11-1a中,顶点2与顶点1相邻接,但顶点1并不与