1.图的定义 图G由两个集合构成,记作G=其中 V( vertex)是顶点的非空有限集合 E(edge)是边的有限集合,而边是顶点对的集合。 VO V2 V3 V4 G1= V1={vo,v1,V2,w3,v4 E1={(vo,V1),(vo,vy3),(v1,V2),(v,v4),(v2,v3)(v2,v)}
1. 图的定义 G1= V1={v0 ,v1,v2,v3,v4} E1={(v0,v1),(v0,v3),(v1,v2),(v1,v4),(v2,v3)(v2,v4)} V0 V3 V4 V1 V2 • 图G由两个集合构成,记作G= 其中: • V(vertex)是顶点的非空有限集合 • E(edge)是边的有限集合,而边是顶点对的集合
图的应用举例: 例1交通图(公路、铁路) 顶点:地点 边:连接地点的公路 交通图中的有单行道双行道,分别用有向边、无向边表示; 例2电路图 顶点:元件 边:连接元件之间的线路 例3通讯线路图 顶点:地点 边:地点间的连线 例4各种流程图 如产品的生产流程图 顶点:工序 边:各道工序之间的顺序关系
例1 交通图(公路、铁路) 顶点:地点 边:连接地点的公路 交通图中的有单行道双行道,分别用有向边、无向边表示; 例2 电路图 顶点:元件 边:连接元件之间的线路 例3 通讯线路图 顶点:地点 边:地点间的连线 例4 各种流程图 如产品的生产流程图 顶点:工序 边:各道工序之间的顺序关系 图的应用举例:
2图的基本术语 VO 有向图、无向图 有向边(弧)、弧尾、弧头 无向边(边) V4 ●完全图:总边数 有向完全图、无向完全图 子图 ●路径、路径长度 V3) ●简单路径、简单回路 ●连通图、连通分量、强连通图 网络:带权的图
2. 图的基本术语 有向图、无向图 有向边(弧)、弧尾、弧头 无向边(边) 完全图:总边数 有向完全图、无向完全图: 子图 路径、路径长度 简单路径、简单回路 连通图、连通分量、强连通图 网络:带权的图 V0 V3 V4 V1 V2 V0 V1 V2 V3
●邻接点、相邻接、边与顶点关联 无向图中顶点的度 VO 有向图中顶点的度=入度+出度 ●生成树、生成林 V V4) VO V V3
邻接点、相邻接、边与顶点关联 无向图中顶点的度 有向图中顶点的度=入度+出度 生成树、生成林 V0 V3 V4 V1 V2 V0 V1 V2 V3
有向边(弧)、弧尾、弧头;无向边(边) 无向图在图G中,若所有边是无向边 有向图在图G中,若所有边是有向边 混和图:在图G中,即有无向边也有有向边 完全图 无向完全图:任意两顶点间都有边的图。 在一个含有n个顶点的无向完全图中,有n(n-1)/2条边。 有向完全图任意两顶点之间都有方向互为相反的两条弧相连 接的有向图。 。在一个含有n个顶点的有向完全图中,有n(m-1)条弧。 v2)
V0 V3 V4 V1 V2 V0 V1 V2 V3 有向边(弧)、弧尾、弧头;无向边(边) 无向图:在图G中,若所有边是无向边 有向图:在图G中,若所有边是有向边 混和图:在图G中,即有无向边也有有向边 完全图: 无向完全图:任意两顶点间都有边的图。 在一个含有n个顶点的无向完全图中,有n(n-1)/2条边。 有向完全图:任意两顶点之间都有方向互为相反的两条弧相连 接的有向图。 在一个含有n个顶点的有向完全图中,有n(n-1)条弧