离散数学-图论基础市公开课一等奖省赛课获奖PPT课件.pptx

该【离散数学-图论基础市公开课一等奖省赛课获奖PPT课件 】是由【liaoyumen】上传分享，文档一共【114】页，该文档可以免费在线阅读，需要了解更多关于【离散数学-图论基础市公开课一等奖省赛课获奖PPT课件 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。第七章 图论基础 Graphs
第1页
10 二月 2025
第一节 图基本概念
一个图G定义为一个三元组：G=<V, E, Φ>
V —— 非空有限集合，V中元素称为结点 (node)或顶点(vertex)
E —— 有限集合（能够为空），E中元素称为边(edge)
Φ —— 从E到V有序对或无序正确关联映射(associative mapping)
v1
v2
v3
(a)
v1
v2
v3
(b)
v1
v2
v3
(c)
第2页
10 二月 2025
图基本概念
图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终止点
v1
v2
v3
(a)
v1
v2
v3
(b)
v1
v2
v3
(c)
第3页
10 二月 2025
图基本概念
若va和vb与边（弧）e相联结，则称va和vb是e端结点va和vb是邻接结点，记作：va adj vb (adjoin)也称e关联va和vb，或称va和vb关联e
若va和vb不与任何边（弧）相联结，则称va和vb是非邻接结点，记作：va nadj vb
关联同一个结点两条边（弧），称为邻接边（弧）
关联同一个结点及其本身边，称为环(cycle)，环方向没有意义
v1
v2
v3
(a)
v1
v2
v3
(b)
v1
v2
v3
(c)
第4页
10 二月 2025
图基本概念
若将图G中每条边（弧）都看作联结两个结点则G简记为：<V, E>
每条边都是弧图，称为有向图(directed graph)（如图b）每条边都是无向边图，称为无向图(undirected graph) （如图a） 有些边是弧，有些边是无向边图，称为混合图（如图c）
v1
v2
v3
(a)
v1
v2
v3
(b)
v1
v2
v3
(c)
第5页
10 二月 2025
图基本概念
若图G中任意两个结点之间不多于一条无向边（或不多于一条同向弧），且任何结点无环，则称G为简单图（如图c）
若图G中某两个结点之间多于一条无向边（或多于一条同向弧），则称G为多重图（如图a, b） 两个结点间多条边（同向弧）称为平行边（弧），平行边（弧）条数，称为重数
v1
v2
v3
(a)
v1
v2
v3
(b)
v1
v2
v3
(c)
第6页
10 二月 2025
图基本概念
在多重图表示中，可在边（弧）上标注正整数，以表示平行边（弧）重数
把重数作为分配给边（弧）上数，称为权(weight)将权概念普通化，使其不一定是正整数，则得到加权图概念：
给每条边（弧）都赋予权图，叫做加权图(weighted graph)记作G=<V, E, W>，W是各边权之和
v1
v2
v3
(a)
v1
v2
v3
(b)
v1
v2
v3
(c)
1
1
1
1
1
1
2
2
1
1
第7页
10 二月 2025
图基本概念
在无向图G=<V, E>中，V中每个结点都与其余全部结点邻接，即 (va)(vb)(va, vb  V  [va, vb]  E)，如图(a)则称该图为无向完全图(complete graph)，记作K|V|若|V|=n，则|E|= C = n(n-1)/2
v1
v2
v3
(a)
v1
v2
v3
(b)
2
n
第8页
10 二月 2025
图基本概念
在有向图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)
v1
v2
v3
(a)
v1
v2
v3
(b)
2
n
第9页
10 二月 2025
图基本概念
在图G=<V, E>中，若有一个结点不与其它任何结点邻接则该结点称为孤立结点，如图(a)中v4
仅有孤立结点图，称为零图，零图 E = ，如图(b)
仅有一个孤立结点图，称为平凡图(trivial graph)，如图(c)
v1
v2
v3
(a)
v1
v2
v3
(b)
v1
(c)
v4
第10页