货源网站,网站开发和网络工程哪个好,中信建设有限责任公司工程资质,那里建设网站好六、图
6.1 图的基本概念
图的定义
图#xff1a;图G由顶点集V和边集E组成#xff0c;记为G (V, E)#xff0c;其中V(G)表示图G中顶点的有限非空集#xff1b;E(G) 表示图G中顶点之间的关系#xff08;边#xff09;集合。若V {v1, v2, … , vn}#xff0c;则用|V|…六、图
6.1 图的基本概念
图的定义
图图G由顶点集V和边集E组成记为G (V, E)其中V(G)表示图G中顶点的有限非空集E(G) 表示图G中顶点之间的关系边集合。若V {v1, v2, … , vn}则用|V|表示图G中顶点的个 数也称图G的阶用|E|表示图G中边的条数。
注意线性表可以是空表树可以是空树但图不可以是空即V一定是非空集无向图若E是无向边简称边的有限集合时则图G为无向图。边是顶点的无序对记为(v, w)或(w, v)因为(v, w) (w, v)其 中v、w是顶点。可以说顶点w和顶点v互为邻接点。边(v, w) 依附于顶点w和v或者说边(v, w)和顶点v、w相关联
有向图若E是有向边也称弧的有限集合时则图G为有向图。 弧是顶点的有序对记为v,w其中v、w是顶点v称为弧尾w称为弧头v,w称为从顶点v到顶点w的弧也称 v邻接到w或w邻接自v。v,w ≠w,v 简单图——① 不存在重复边 ② 不存在顶点到自身的边 数据结构课程只探讨 “简单图”
多重图——图G中某两个结点之间的边数多于一条又允许顶点通过同一条边和自己关联
顶点的度、入度、出度
无向图顶点v的度是指依附于该顶点的边的条数记为TD(v)。 在具有n个顶点、e条边的无向图中 即无向图的全部顶点的度的和等于边数的2倍
有向图入度是以顶点v为终点的有向边的数目记为ID(v) 出度是以顶点v为起点的有向边的数目记为OD(v)。 顶点v的度等于其入度和出度之和即TD(v) ID(v) OD(v)。 在具有n个顶点、e条边的有向图中即入度和出度的数量相等且等于e
顶点的关系描述
路径——顶点vp到顶点vq之间的一条路径是指顶点序列 回路——第一个顶点和最后一个顶点相同的路径称为回路或环简单路径——在路径序列中顶点不重复出现的路径称为简单路径。 简单回路——除第一个顶点和最后一个顶点外其余顶点不重复出现的回路称为简单回路。路径长度——路径上边的数目点到点的距离——从顶点u出发到顶点v的最短路径若存在则此路径的长度称为从u到v的距离。 若从u到v根本不存在路径则记该距离为无穷∞。无向图中若从顶点v到顶点w有路径存在则称v和w是连通的有向图中若从顶点v到顶点w和从顶点w到顶点v之间都有路径则称这两个顶点是强连通的
图G中任意两个顶点都是连通的则称图G为连通图否则称为非连通图。 若图中任何一对顶点都是强连通的则称此图为强连通图。
研究图的局部—子图、生成子图
设有两个图G (V, E)和G ′ (V ′ , E ′ )若V ′ 是V的子集且 E ′ 是 E的子集则称G ′ 是G的子图 若有满足V(G ′ ) V(G)的子图G ′ 则称其为G的生成子图
有向图的子图和生成子图也是一样的
无向图中的极大连通子图称为连通分量 子图必须连通且包含尽可能多的顶点和边 有向图中的极大强连通子图称为有向图的强连通分量 子图必须强连通同时 保留尽可能多的边生成树连通图的生成树是包含图中全部顶点的一个极小连通子图。 若图中顶点数为n则它的生成树含有 n-1 条边。对生成树而言若砍去它的一条边则会变成非连通 图若加上一条边则会形成一个回路。(因此边要尽可能的少但要保持连通)
生成森林在非连通图中连通分量的生成树构成了非连通图的生成森林
边的权、带权图/网
边的权——在一个图中每条边都可以标上具有某种含义的数值该数值称为该边的权值。带权图/网——边上带有权值的图称为带权图也称网。带权路径长度——当图是带权图时一条路径上所有边的权值之和称为该路径的带权路径长度
特殊形态的图
无向完全图——无向图中任意两个顶点之间都存在边 若无向图的顶点数|V|n则
有向完全图——有向图中任意两个顶点 之间都存在方向相反的两条弧 若有向图的顶点数|V|n则稀疏图边数很少的图称为稀疏图 反之称为稠密图 树——不存在回路且连通的无向图 n个顶点的树必有n-1条边。 常见考点n个顶点的图若 |E|n-1则一定有回路有向树——一个顶点的入度为0、其余顶点的 入度均为1的有向图称为有向树
