资源描述：
《7图与网络分析》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、图8-5五个药品Z间会发牛•化学反应的关系示意图武汉8.1图与网络的基本知识8.1.1图与网络的基本概念8」」」图的定义白然界和人类社会中，大量的事物以及事物之间的关系，常可以用图形來描述。例如:图8・4所示的我国北京、上海等十个城市间的交通图反映了这十个城市间铁路分布情况。这里用点代表城M，用点和点之间的连线代表这两个城M之间有直通铁路。图8-4十个城市间铁路分布图又如某单•位储存五种化学药品，其中，某些药品是不能放在同一库厉里的，为了反映这种情况，可以用点九、巾、勺、勺、冬分别代表这五种药品，若药品引和药品V/是不能存放在同一库房的，则在片和少Z间连一条线，如图8・5所示。如
2、果问题归结为寻求存放这种寸匕年］化学药品的最少库房个数，则该问题就是染色问题。事实上，至少需要三个库房来存放这些药品，即片和冬、勺和勺、均各存放在一个库房里。前面的两个例了涉及到的对象Z间的关系具冇“对称性"，就是说，如果卬与乙冇这种关系，那么同时乙与甲也冇这种关系。例如，如果屮药品不能和乙药品放在一起，那么，乙药品当然也不能和甲药品放在一起。在实际生活中，有许多关系不具有这种对称性。例如，有甲、乙、丙、丁、戊五个球队，各队Z间的比赛情况如表「1所示。五个球队Z间的胜负关系显然是一种非对称关系，如果球队甲胜了球队乙，可以用一•条带箭头的联线表示，BP加一＞陀,于是,表的关系可以表
3、示成图8・6所示。郑州表8・1五个球队的比赛情况农屮乙丙T甲X胜负胜乙负X胜丙胜负X胜T负负X图8・6五个球队比赛的胜负连线图从以上分析可以看出，我们常将所研究——对象看成一个点，用连线（带箭头或不带箭头）表示对象之间的某种特定的关系，这时连线的长短曲宜无关紧要，重要的是两点之间有无线和连。为了区别起见，把两点Z间不带箭头的连线称为边，带箭头的连线称为弧。由此，我们便抽象出图的概念。Vip图是描述对彖之间某种特处关系的工具，用数字语言描述如下：定义&1一个图是rh—个非空集合r,以及由？中元素的无序（或有序）对组成的集合e（或/）所组成。7中冗素的无序点对构成的集合称为边集合&由
4、点集合/和边集合E构成的无向图（简称图）记为G=（7,E）,一条连接点匕七，v,.,v7EV的边％，记为矿［片七或勺=氏必］。/中元素的有序点对构成的集合称为弧集合儿由点集合7和弧集合力构成的有向图，记为D=（V,A）（或G=（7,/））,—条方向是从％指向亏的弧记为勺=（匕小）。图8・7是一个无向图。该图可以表示为：C=（K£）V={仏卩2，叫宀}£={e,,e2,e3,e4,e5,e6,e7}其中弓=[讥],^=[vPv2],e3=[v2,v3],e4=[v3,v4],e5=[vPv4],e6=[vpv3],e7=[v4,v4]图8・8是一个有向图。该图nJ以表示为：d=（v
5、,A）V={片，叫，儿，匕*5，吃*7},A={4，02卫3，。4,•…,Qi}其中q=（片*2），02=（%，%），。3=（勺*2），。4=（%*4），。5=（"2必），。6=（勺也），5=（卩4，*），逊二仏川3），。9=仏，勺），。10=仏，*），川7）若图G中，某个边的两个端点相同，则称e>是环（如图8・7中S）,若两个点之间有多于一条的边，成为多重边（如图8・7中勺，e2）o一个无环多重边的图称为简单图，但允许冇多重边的图称为多重图。图G或D中的点数记为n=Vf边（弧）数记为加，m=E（加二国），在不会引起混乱的情况下，分别简记为/;、加，其中点数"称为G（或Q
6、）的阶，若刃是有限的，则称为冇限阶。今后，我们只对冇限阶的图进行讨论。8.1.1.2图中有关点、边关系的术语（1）端点当匂=［片’匕［时，与边勺相连的顶点*、与分别叫做勺的端点。（2）边与顶相关联当=［V/，Vy时，勺与齐、与称为边顶相关联。（3）邻顶当eij=_vi>vi~时，*、V/之间叫做邻顶。（4）邻边与同一顶点关联的边叫做邻边。（5）环只与一个顶点关联的边叫做环e,=vy。（6）平行边具有相同的两个端点的边称为平行边。（7）邻域图G中点丹的邻域定义为G中与岭相邻接的点的集合，记为：Ng（v/）={v7
7、［v/,vJg£'}（8）次以点齐为端点的边的数H称为点齐在G中
8、的次，记为："gG）或〃（匕）。如果有环，则按两条边记，即:=+（8-1）其中：4（%）是与丹相关联的非环边数，/（匕）是与匕相关联的环数。（9）次序列若炉他°2，.・匕}，则相对于每个点都有一个次，则可以得到一个序列（爪］）,d®2）,…）。（10）定理8.1对于图G=（7,E），其中V=n,E=m，则有：工〃何=2m（8-2）veV证明：每条边都有两个端点，在计算顶点的次时，每个端点都要计算对应边次，故共有2加次o通俗地讲，就是线有两头，共有2刃个线头的意思。(11)
