大学离散数学《图论基础》案例教学课件

图论基础：从生活场景到数学抽象图的定义·基本术语·矩阵表示2026课程导览01从生活走进图的世界真实场景引出图02图的基本概念与术语定义与核心术语03图的矩阵表示邻接矩阵与关联矩阵04案例综合与拓展巩固与应用01从生活走进图的世界图无处不在，先看见它，再定义它六个人的朋友圈如何定义图对象本身每人画成圆点对象之间的连接好友之间连上线段连接是否带方向关注与被关注可有方向现实可抽象为点和线课程选修、直达航班等，只要关心是否关联先见生活中的图再严格定义门槛自然降低交通线路里的图结构朋友圈与交通线路场景不同，抽象后的结构相同。五座城市之间开行若干直达班车，有的可直达，有的需换乘。

城市

直达线路

需换乘画法城市画成圆点有直达班车的两城之间连一条线关键取舍不关心实际距离，不关心道路弯曲形状线长短、点大小都不重要只看哪些城市间有直达线路及是否区分往返方向场景五座城市之间开行若干直达班车有的可直达，有的需换乘忽略具体含义、只保留对象与关系，就是图论建模的核心思想。从具体场景到图形抽象01案例观察两个案例，一个共性友谊关系中的个人、交通网络中的城市→都只是抽象点。好友之间、直达城市之间是否存在联系→才是真正被关注的内容。02抽象提炼剥离场景，得到定义抽象点统称为顶点。连接两点、表示某种关系的线段统称为边。图=一群顶点+若干条边组成的数学结构。03关键铺垫方向有无，决定类型关系只有"有/没有"两种状态→不带箭头的线段。关系本身有方向（单向关注、单行道）→边上加箭头。这一分类意识，正是引出无向图与有向图的关键铺垫。02图的基本概念与术语概念是图论的语言，术语是表达的基石图作为顶点与边的二元组定义·无向图G=(V,E)非空顶点集合V与边集合E无向图

G

由两部分组成——非空顶点集合V

与边集合E，记作G=(V,E)。无序点对边不分方向同一对象·互为端点连接

u

与

v

的边不区分方向，与连接v与u的边是同一对象；每条边连接的两个顶点互称端点。简单图至多一条边·端点不同排除平行边与环任意两点间至多一条边，且每条边的两个端点不同——排除平行边与环。入门阶段讨论的图通常均为简单图。邻接与关联这对基础概念“邻接看点与点，关联看点与边”“这两组概念是全文基石：顶点的度、邻接矩阵、关联矩阵，本质上都是把“谁和谁相邻”“谁和哪条边关联”用不同语言重新描述。”小明与小红是好友→小明与小红相邻；连接他们的那条边→同时与小明、小红两人相关联。邻接点与点两个顶点被同一条边连接，互为邻接点：描述点与点的关系关联点与边一个顶点是某条边的端点：描述点与边的关系顶点的度与握手定理图论用最简单的“点”与“边”，刻画社交网络与交通线路背后的结构规律。直觉的场景，严谨的结论——生活经验不断印证数学定理，数学则给直觉以精确的表达。度的定义关联边数交通图城市的度=直达线路数友谊图人的度=好友人数握手定理度数和=2|E|所有顶点度数之和=边数

×2每条边连接两个端点，求和时恰好被计数两次聚会中所有人握手次数总和，必为总握手次数的两倍推论奇数度为偶数个度数为奇数的顶点个数必为偶数三类常见特殊图完全图每对顶点之间恰有一条边任意两个对象都有关系所有成员彼此相识社交网络二分图顶点分成两部分，每条边都连接不同部分课程与选课学生工人与可胜任工序匹配正则图每个顶点度数完全相同结构均匀对称度数统一为同一常数规则网络路径与连通的基本观念“路径丈量距离，连通定义整体。”01路径顶点与边交替相接的序列；长度按经过的边数计。02连通任意两顶点之间都存在路径，网络中没有孤立局部，成员间可经关系传递建立联系。03连通分量不连通图拆出的极大连通子图；例如交通图中某座不通车的城市自成独立分量。路径丈量距离，连通定义整体。03图的矩阵表示把图装进矩阵，让计算机也能读懂用矩阵记录邻接关系矩阵邻接矩阵图形直观，但计算与存储不便。邻接矩阵用一张数字表格完整编码图的结构。构造规则n

个顶点→n行n列方阵，行列对应各顶点第

i

个顶点与第

j

个顶点相邻→记

1，否则记

0学习小组示例六人编号，好友记

1、非好友记

0，得到

6×6

邻接表。每一行如实回答：这个人有哪些好友无向图邻接矩阵的对称性对称性来源对角线对称行和即度度为1的个数握手定理印证边数两倍无向图邻接矩阵的对称性：三大性质对称性来源：i与j相邻⇔j与i相邻，因此第i行第j列与第j行第i列总是相同——关于主对角线对称，这是无向图的数学签名。行和即度：沿任一行（或列）数1的个数，得到对应顶点的度；图形语言中的度，可直接从矩阵行中读出。与握手定理印证：每条边对应两个对称位置的1，全表共有

边数两倍

个1；图形语言与矩阵语言彼此呼应。边与顶点的关联矩阵交通图直达线路编号为列，城市编号为行问题→对策

问题邻接矩阵只回答顶点之间是否相连，无法直接看出“某条边连着哪两个顶点”。

对策关联矩阵按

顶点

×

边

组织：n

个顶点、m

条边构成

n行m列

矩阵，行对应顶点，列对应边。关联矩阵的构造规则3条第

i

个顶点是第

j

条边的端点→第

i

行第

j

列记

1否则记

0无向图每条边恰有两个端点→每列恰有

两个1两种矩阵各司其职邻接矩阵回答“谁和谁相连”，关联矩阵回答“谁出现在哪条边上”。同一个图，图形、邻接矩阵、关联矩阵三种描述答案完全一致，只是载体不同。学会在表示之间自由转换，正是离散数学训练的核心能力之一。邻接矩阵回答“谁和谁相连”方阵，适合快速判断两点是否相邻、计算顶点的度关联矩阵回答“谁出现在哪条边上”一般不是方阵，列数与边数一致，边的身份被单独列出04案例综合与拓展从案例中来，到应用中去校园活动分组的二分图建模某学院学生报名参加三个课外项目组，需理清学生与项目的对应关系。建模思路两类顶点学生、项目各为一类顶点，边表示“参加”关系天然二分每条边都跨两类顶点，天然构成二分图直观洞察画图后可直接看出：热门项目、多项目学生矩阵表示0/1编码行=学生，列=项目；1

表示参加，0

表示未参加列和=项目人数列中

1的个数=该项目人数行和=参加项目数行中

1的个数=该生参加的项目数俱乐部成员结构的矩阵化分析分三步完成从图到表的转化。图解

三步完成

从图到表的转化01第一步·画图求度画出关系图，找出每个顶点的度度数最高者即人脉最广的人›02第二步·握手定理核对五人的度数之和

=边数的2倍›03第三步·写出两种矩阵邻接矩阵：看出谁是核心连接点关联矩阵：逐条确认每条友谊关系涉及哪两位成员对比两种矩阵，成员结构信息被完全保留。邻接矩阵看出谁是核心连接点——矩阵某行中“1”最多的顶点，即连接关系最密集的人。关联矩阵逐条确认每条友谊关系涉及哪两位成员——行对应成员、列对应友谊关系。识别图中的特殊结构判定对象：任意网络是否属于完全图、二分图或正则图。图形看结构，矩阵看数字，两条路径指向同一个答案图形判断完全图每一对顶点之间都有边二分图顶点可分成两组，所有边都横跨两组正则图所有顶点的度数相等矩阵判断→完全图邻接矩阵对角线全为

0、其余位置全为

1→正则图每一行

1

的个数相同图论基础的学习地图回顾“基础术语是图论的基本词汇，掌握它，复杂算法自然顺畅。”“基础术语是图论的基本词汇，掌握它，复杂算法自然顺畅。”本讲知识链定义图