图论基础

[Ir1d]

https://oi-wiki.org/graph/basic/

[axiomofchoice-hjt]

为什么简单路径意味着每条边至多经过一次，而简单回路意味着每个点（除了起点终点）至多经过一次呢？(是不是简单路径/回路在不同语境下有不同含义？）

[Ir1d]

@HouJinTao 嗯，这种定义都是需要根据上下文仔细甄别的

[axiomofchoice-hjt]

为什么我感觉所有子图都是边导出子图qwq，边导出子图有用吗

[VickersChui]

谢谢分享

[IceySakura]

在简单图的定义中，“非空简单图中一定存在度相同的结点”，这个性质应该是被限制在无向图中的，因为有向图是很容易构造出反例的。

[Yangff]

@SingerCoder Hmmm.. 对有向图的入度和出度也分别成立吧？

[IceySakura]

@Yangff
@SingerCoder Hmmm.. 对有向图的入度和出度也分别成立吧？

出度和入度好像都是不成立的，令一个n阶图的每个点的出度和入度都为[0,n-1]的一个排列即可：
n=2，1->2

[IceySakura]

无向图能成立就是因为度数为0的和为n-1的点不能同时存在，有向图好像就保证不了这个性质了

[kevin335200]

相邻的概念应该不需要无向图的前提？对于图都成立吧

[dfsaab]

边覆盖集里的图指的是没有孤立顶点的图吧

[CCXXXI]

空图是 $G$ 的支撑子图

边集为空的图称为 零图 (Null graph)

两处 空图/零图 看起来指同一概念，统一用词会更好；另外在用到这个概念之后那么远才给定义也有点难读。

[Joecai9]

怎样理解同构呢

[q779]

仙人掌分为点仙人掌和边仙人掌，这里只说了边仙人掌。
参考https://ddosvoid.github.io/2021/07/09/%E4%BB%99%E4%BA%BA%E6%8E%8C/