离散数学-图论基础.pptxVIP

第七章图论基础

Graphs

08十一月2024第一节图的基本概念一个图G定义为一个三元组：G=V,E,ΦV——非空有限集合，V中的元素称为结点(node)或

顶点(vertex)E——有限集合（可以为空），E中的元素称为边(edge)Φ——从E到V的有序对或无序对的关联映射(associativemapping)v1v2v3(a)v1v2v3(b)v1v2v3(c)

08十一月2024图的基本概念图G=V,E,Φ中的每条边都与图中的无序对或有序对联系若边e?E与无序对结点[va,vb]相联系，即Φ(e)=[va,vb]

（va,vb?V）则称e是无向边（或边、棱）若边e?E与有序对结点va,vb相联系，即Φ(e)=va,vb

（va,vb?V）则称e是有向边（或弧）

va是e的起始结点，vb是e的终结点v1v2v3(a)v1v2v3(b)v1v2v3(c)

08十一月2024图的基本概念若va和vb与边（弧）e相联结，则称va和vb是e的端结点

va和vb是邻接结点，记作：vaadjvb(adjoin)

也称e关联va和vb，或称va和vb关联e若va和vb不与任何边（弧）相联结，则称va和vb是非邻接结点，记作：vanadjvb关联同一个结点的两条边（弧），称为邻接边（弧）关联同一个结点及其自身的边，称为环(cycle)，环的方向没有意义v1v2v3(a)v1v2v3(b)v1v2v3(c)

08十一月2024图的基本概念若将图G中的每条边（弧）都看作联结两个结点

则G简记为：V,E每条边都是弧的图，称为有向图(directedgraph)（如图b）

每条边都是无向边的图，称为无向图(undirectedgraph)

（如图a）

有些边是弧，有些边是无向边的图，称为混合图（如图c）v1v2v3(a)v1v2v3(b)v1v2v3(c)

08十一月2024图的基本概念若图G中的任意两个结点之间不多于一条无向边（或不多于一条同向弧），且任何结点无环，则称G为简单图（如图c）若图G中某两个结点之间多于一条无向边（或多于一条同向弧），则称G为多重图（如图a,b）

两个结点间的多条边（同向弧）称为平行边（弧），

平行边（弧）的条数，称为重数v1v2v3(a)v1v2v3(b)v1v2v3(c)

08十一月2024图的基本概念在多重图的表示中，可在边（弧）上标注正整数，以表示平行边（弧）的重数把重数作为分配给边（弧）上的数，称为权(weight)

将权的概念一般化，使其不一定是正整数，则得到加权图的概念：给每条边（弧）都赋予权的图，叫做加权图(weightedgraph)

记作G=V,E,W，W是各边权之和v1v2v3(a)v1v2v3(b)v1v2v3(c)1111112211

08十一月2024图的基本概念在无向图G=V,E中，V中的每个结点都与其余的所有结点邻接，即 (?va)(?vb)(va,vb?V?[va,vb]?E)，如图(a)

则称该图为无向完全图(completegraph)，记作K|V|

若|V|=n，则|E|=C=n(n-1)/2v1v2v3(a)v1v2v3(b)2n

08十一月2024图的基本概念在有向图G=V,E中，V中的任意两个结点间都有方向相反的两条弧，即

(?va)(?vb)(va,vb?V?va,vb?E∧vb,va?E)，如图(a)

则称该图为有向完全图，记作K|V|

若|V|=n，则|E|=P=n(n-1)v1v2v3(a)v1v2v3(b)2n

08十一月2024图的基本概念在图G=V,E中，若有一个结点不与其他任何结点邻接

则该结点称为孤立结点，如图(a)中的v4仅有孤立结点的图，称为零图，零图的E=?，如图(b)仅有一个孤立结点的图，称为平凡图(trivialgraph)，如图(c)v1v2v3(a)v1v2v3(b)v1(c)v4

08十一月2024问题问题1：是否存在这种情况：25个人中，由于意见不同，每个人恰好与其他5个人意见一致？问题2：是否存在这种情况：2个或以上的人群中，至少有2个人在此人群中的朋友数一样多？

08十一月2024结点的次数二、结点的次数定义：在有向图G=V,E中，对任意结点v?V以v为起始结点的弧的条数，称为出度(out-degree)

（引出次数），记为d+(v)以v为终结点的弧的条数，称为入度(in-degree)

（引入次数），记为d-(v)v的出度和入度的和，称为v的度数(degree)

（次数），记为d(v)=d+(v)+d-(v)v1v