图的基本概念以及几种特殊的图

文章目录图的定义无向图 与 有向图无向图有向图简单图 与 多重图度顶点的度、入度、出度顶点-顶点的关系描述连通图 与 强连通图子图 生成子图连通分量生成树、生成森林权边的权、带权图/网几种特殊的图总结图的定义图 GGraph 由两个集合组成顶点集VVertex 和边集EEdge。记作G(V,E)。其中V(G)表示图G中顶点的有限非空集E(G)表示图G中顶点之间的关系边集合。若V{V1,V2,…,Vn},则用|V|表示图G中顶点的个数也称图G的阶。E{(u,v) | u∈Vv∈V}则|E|表示图G中边的条数。【注】线性表可以是空表树可以是空树但图不可以是空即V一定是非空集。无向图 与 有向图无向图若图G ( V , E ) G(V,E)G(V,E)中边集E EE的元素为无向边简称边则称G GG为无向图。无向边是顶点的无序对记为( v , w ) (v,w)(v,w)或( w , v ) (w,v)(w,v)满足( v , w ) ( w , v ) \boldsymbol{(v,w)(w,v)}(v,w)(w,v)【无顺序要求】邻接点边( v , w ) (v,w)(v,w)连接的两个顶点v vv、w ww互为邻接点关联边( v , w ) (v,w)(v,w)依附于顶点v vv和w ww也称边与这两个顶点相关联G 2 ( V 2 , E 2 ) G_2(V_2,E_2)G2​(V2​,E2​)顶点集V 2 { A , B , C , D , E } V_2\{A,B,C,D,E\}V2​{A,B,C,D,E}边集E 2 { ( A , B ) , ( B , D ) , ( B , E ) , ( C , D ) , ( C , E ) , ( D , E ) } E_2\{(A,B),(B,D),(B,E),(C,D),(C,E),(D,E)\}E2​{(A,B),(B,D),(B,E),(C,D),(C,E),(D,E)}有向图若图G ( V , E ) G(V,E)G(V,E)中边集E EE的元素为有向边弧则称G GG为有向图。弧是顶点的有序对记为⟨ v , w ⟩ \langle v,w \rangle⟨v,w⟩⟨ v , w ⟩ ≠ ⟨ w , v ⟩ \boldsymbol{\langle v,w \rangle \neq \langle w,v \rangle}⟨v,w⟩⟨w,v⟩⟨ v , w ⟩ \langle v,w \rangle⟨v,w⟩v vv为弧尾起点无箭头指w ww为弧头终点箭头所指称为从v vv到w ww的弧邻接描述v vv邻接到w www ww邻接自v vvG 1 ( V 1 , E 1 ) G_1(V_1,E_1)G1​(V1​,E1​)顶点集V 1 { A , B , C , D , E } V_1\{A,B,C,D,E\}V1​{A,B,C,D,E}边集E 1 { ⟨ A , B ⟩ , ⟨ A , C ⟩ , ⟨ A , D ⟩ , ⟨ A , E ⟩ , ⟨ B , A ⟩ , ⟨ B , C ⟩ , ⟨ B , E ⟩ , ⟨ C , D ⟩ } E_1\{\langle A,B \rangle,\langle A,C \rangle,\langle A,D \rangle,\langle A,E \rangle,\langle B,A \rangle,\langle B,C \rangle,\langle B,E \rangle,\langle C,D \rangle\}E1​{⟨A,B⟩,⟨A,C⟩,⟨A,D⟩,⟨A,E⟩,⟨B,A⟩,⟨B,C⟩,⟨B,E⟩,⟨C,D⟩}简单图 与 多重图度顶点的度、入度、出度无向图有向图顶点-顶点的关系描述路径顶点v p v_pvp​到 顶点v q v_qvq​的一条路径是指顶点序列v p , v i 1 , v i 2 , … , v i m , v q v_p,v_{i_1},v_{i_2},\dots,v_{i_m},v_qvp​,vi1​​,vi2​​,…,vim​​,vq​回路环起点顶点与终点顶点相同的路径。简单路径路径序列中顶点不重复出现。简单回路除起点、终点相同之外其余顶点均不重复的回路。路径长度路径上边的数量。点到点距离u uu到v vv的最短路径长度若无路径或路径不存在则距离记为无穷∞ \infty∞。无向图连通无向图中顶点v vv到w ww存在路径则这两顶点连通。【无向图方向无限制】有向图强连通有向图中v vv到w ww、同时w ww到v vv都存在路径则这两顶点强连通。【有向图的路径也是有向的】连通图 与 强连通图连通图无向图强连通图有向图子图 生成子图子图V ′ ⊆ V , E ′ ⊆ E V \subseteq V,\ E \subseteq EV′⊆V,E′⊆E。生成子图顶点集合和原图完全一样边是原图边子集。顶点不能丢边可以少连通分量连通分量是极大连通子图子图必须连通且包含尽可能多的顶点和边生成树、生成森林生成树连通图的生成树包含图中全部顶点的一个极小连通子图边尽可能的少但要保持连通。顶点数为n nn则其生成树恰好n − 1 n-1n−1条边。砍掉生成树任意一条边图变为非连通。给生成树任意加一条边必然产生回路。生成森林在非连通图中连通分量的生成树构成了非连通图的生成森林。权边的权、带权图/网几种特殊的图总结