当前位置:C++技术网 > 资讯 > 数据结构笔记分享:4 图的基本概念和术语

数据结构笔记分享:4 图的基本概念和术语

更新时间:2015-11-12 08:36:25浏览次数:1+次

定义:由顶点集V和连接顶点的弧集E所组成的结构,记作G = ( V, E )。

其中弧的形式为<Vi,Vj>,表示从顶点Vi到Vj之间有一条弧表示 Vi ——> Vj

其中,根据顶点间的关系是否有向引入有向图无向图

有向图的结点关系:弧的形式为<Vi,Vj> 表示 Vi ——> Vj

无向图的结点关系:边的形式为(Vi,Vj)  表示 Vi —— Vj

若G中每条边(弧)对应一个数值——表示关系的程度,则称图G为网络

G1=(V1E1),若满足V1<VE1<E。则G1G子图

<Vi,Vj>E——则称ViVj相邻接Vi邻接到VjVj邻接自Vi

( Vi,Vj )E——则称ViVj相邻接


—— 顶点的邻接点的数目

有向图中:入度,出度。度=入度+出度。

路径 —— 顶点序列Vi1Vi2Vik,满足< VilVi(l+1)>E或者(VilVi(l+1))E)(l=1,2,…,k-1

例,图G1中,1,2,4,1,3,4是条路径

简单路径 —— 中间经过的顶点不重复

例,图G1中,( 1,2,3 ) ( 1,3,4 ) ( 1,3,4,1 ) 都是简单路径

回路 —— 首位相同的路径 ( 1,3,4,1 )

简单回路 —— 简单路径 + 回路

若无向图G中的任意两点间都存在路径 —— 连通图

否则,不连通。包含若干连通分量

若有向图G中的任意两点间可以互相到达 —— 强连通图

若无向图G中的任意两点间有一条边 —— 无向完全图(共n (n-1) / 2条边)

若有向图G中每个顶点岛其余各点均有一条狐 —— 有向完全图(共n (n-1) 条边)

若无向图满足 —— 连通,无回路 ——>

—— 有最少边数的连通图

   —— n-1条边的连通图

   —— 连通的无环图

有向树 —— 有向图中,某个顶点的入度为0,其余顶点的入度为1(有向根)