图的术语 第七章图 图的顶点数n和边数e的关系:对有向图,0≤e≤m(n-1);对无 向图,0≤c5mm 有向完全图:恰有n(n-1)条有向边(即弧)的有向图 无向完全图:恰有2mn-1)条无向边的无向图 稀疏图:图中边或弧的数目e<<n?2 稠密图:图中边或弧的数目e~n2(准确地说,无向图的e接近 于2(m-1)有向图的e接近于n(m-1) 第10页第七章 图 第10页 图的顶点数n和边数e的关系：对有向图，0≤e≤n(n-1)；对无 向图， 。 有向完全图：恰有n(n-1)条有向边（即弧）的有向图。 无向完全图：恰有 条无向边的无向图。 稀疏图：图中边或弧的数目e<<n2 。 稠密图：图中边或弧的数目e≈n2（准确地说，无向图的e 接近 于 ，有向图的e接近于n(n-1)。 ( 1) 2 1 0  e  n n − ( 1) 2 1 n n − ( 1) 2 1 n n − ⚫ 图的术语 V1 V2 V3 V4 V1 V2 V4 V5 V3