我在网上寻找稀疏图的良好定义，但我很困惑。稀疏图实际上是一个大图，有数百万/数十亿个节点。一个例子，是一个现实世界的一个像Facebook。或者他们也可以在小型网络中？
提前感谢！
一般来说，有n顶点的图如果有Theta（n^2）边，则稠密，否则稀疏。这意味着，如果每个顶点的平均度是线性的，则图是稠密的，如果是次线性的，那么图是稀疏的。
稀疏性并不取决于大小。例如，树是稀疏的（因为具有n节点的树具有n-1边）。
查看此定义。我想你可以说，如果每个垂直线都是少数边的一部分，而如果图是完整的，它将是多少边的一部份，那么图可以被认为是稀疏的。
所以基本上，图不一定要很大才能稀疏。例如，任何树都可以被视为稀疏图，而不考虑节点的数量。
我希望这能有所帮助！