离散数学:图论

图论

  1. 图论
    1. 图的基本概念 (7-1)
    2. 路与回路 (7-2)
    3. 图的矩阵表示 (7-3)
    4. 欧拉图与汉密尔顿图 (7-4)
    5. 平面图 (7-5)
    6. 树与生成树 (7-7)
    7. 根树及其应用 (7-8)

主要知识点

Part 1 基本概念

  • 图的基本概念:
    • 图 无向图 有向图
    • 邻边 邻点 孤立点 平凡图 零图
    • 结点度数与边数的关系 最大度数 最小度数
    • 平行边 自回路 简单图 多重图
  • 完全图、偶图
  • 子图、生成子图
  • 补图
  • 图的同构

Part 2 连通图

  • 路 迹 通路 圈
  • 连通图 连通分支
  • 点割集 割点 边割集 割边(桥)
  • 强连通图 单侧连通图 弱连通图
  • 强分图 单侧分图 弱分图
  • 图的矩阵表示:邻接矩阵、可达矩阵、关联 矩阵。

Part 3 特殊图

  • 欧拉路、欧拉图的概念和判定定理。
  • 汉密尔顿路、汉密尔顿图的概念以及有关的必
    要条件和充分条件。
  • 平面图的概念, 面的次数, 欧拉公式, K3,3、K5是非平面图、
  • 图同胚的概念、Kuratowski定理。
  • 平面图的对偶图的概念及求法。

Part 4 树

  • 无向树的六个等价定义,生成树,最小生成树,求最小生成树的Kruskal算法。
  • 有向树,根树,m叉树,完全m叉树,最优树及其求法,前缀码。

基础概念

  • 图是一个三元组 $\langle V(G),E(G),\varphi_G \rangle$
    • $V(G)$ 是一个非空结点集合
    • $E(G)$ 边集合
    • $\varphi_G$ 从边集合到结点无序偶(有序偶)集合上的函数
  • 简记为 $G=\langle V,E \rangle$
  • 有序偶 $\langle v_i,v_j \rangle$ 表示有向边,构成有向图
  • 无序偶 $\langle v_i,v_j \rangle$ 表示无向边,构成无向图
  • 邻接点,一条边两端的结点
  • 邻接边,关联同一个结点的两条边
  • 回路/环,关联于同一个结点的一条边
  • 孤立结点,不与任何结点邻接
  • 零图,仅由孤立节点构成
  • 平凡图,仅由一个孤立结点构成
  • 结点的度数,与该结点关联的边的数量,记作 $deg(v)$
  • 最大度,$\Delta(G)$,最小度, $\delta(G)$

握手定理:结点度数总和是边的两倍

度数为奇数的结点必定是偶数个。

  • 有向图中:入度和出度
  • 入度之和等于出度之和
  • 平行边,连接于同一对结点的两条边(有向图中要考虑顺序)
  • 多重图,含有平行边的任何一个图
  • 简单图,不含有平行边和环的图
  • 完全图,每一对结点之间都有边相连
    • $n$ 个结点的无向完全图记作 $K_n$
    • 在无向图完全图中,边的个数为 $\frac{1}{2} n(n-1)$ (一个点与 $n-1$ 个点邻接,求和后除以二去重就是结果)
    • 有向图完全图和无向图一样,只不过为每条边赋予了方向,不需要结点之间有两条方向相反的边
  • 偶图,可以将结点分为两集合 $V_1,V_2$ ,并且交集为空集 $V_1 \cap V_2 = \varnothing$
  • 子图,点、边均为原来的子集
  • 生成子图,包含所有结点,边为原来的子集
  • 补图,一个图 $G$ 添加上若干边后可以构成完全图,则这些边的集合以及图上所有的点构成的图称为 $G$ 的补图,记作 $\overline{G}$
  • 相对补图,原图的边 – 子图的边 再加上所有结点
  • 同构:记作$G \simeq G^{‘}$
    • 充要条件:两个图的点和边存在一一对应且保持关联关系
    • 充分:找双射
    • 必要:结点相同、边相同、度数相同的点相同

连通图

  • 交替序列 $v_{0}e_{1}v_{1}e_{2} \cdots e_{n}v_{n}$ 称为联结 $v_0$ 到 $v_n$ 的路
  • :所有边均不相同(所有边只经过一次)
  • 通路:所有结点均不相同(所有结点只经过一次)
  • :一条闭的通路(除 $v_0=v_n$ 外,其他结点各不相同)

简单图中路可以由结点序列确定(边是唯一的),有向图中结点数大于 1 的路可以由边序列表示(起点终点唯一)

如果 $v_i$ 到 $v_j$ 之间存在一条路,则一定存在一条不多于 $n-1$ 条边的路(因为 $n$ 条边就会出现平行边或者是可以通过其他边到达)。

如果 $u$ 和 $v$ 之间存在一条路,则称结点 $u$ $v$ 是连通的。

  • 连通分支
    • 连通分支(图) 是一个子图
    • 结点之间存在一条路称为连通
    • 连通分支中的结点都是连通的,记作 $G(V_1), G(V_2),\cdots$
    • 连通分支数记作 $W(G)$ ,表示连通分支的数量。
  • 连通图,只有一个连通分支
  • 删除
    • 删边:只删边
    • 删点:删掉点以及关联的边
  • 点割集:一个无向连通图删除一个结点的集合 $V_1$ 后不再连通,则这个点集称为点割集
    • 删掉点割集中的所有的点则不连通
    • 删掉一部分或者是不删则仍然连通
    • 点割集中只有一个点,则称为割点
    • 点连通度(连通度):$k(G)=min \lbrace |V_1| \enspace | V_1 是 G 的点割集 \rbrace $ 表示生成一个不连通图需要删去的最少节点数。
      • 不连通图的连通度为 0
      • 存在割点为 1
      • 完全图 $K_p$ 删去任意 $m \enspace (m<p-1)$ 个结点后仍然是连通的,删掉 $p-1$ 是一个平凡图,因此对于完全图 $K_p$ ,定义 $k(K_p)=p-1$
  • 边割集 类比点割集
    • 只有一条边称为割边 (或者)
    • 边连通度 $\lambda (G)=min \lbrace |E_1| \enspace | E_1 是 G 的点割集 \rbrace $
      • 不连通图 $\lambda (G)=0$
  • 对于任意一个图 $G$: $k(G) \leq \lambda(G) \leq \delta(G) $

割点的充要条件: $v$ 是割点,则存在两个点 $u$ $w$ 使得两点之间的所有路都经过 $v$
可达性:在有向图中存在从 $u$ 到 $v$ 的路称为从 $u$ 到 $v$ 可达

  • 可达性自反 传递,但是不一定对称
  • 最短路的长度称为 $u$ 到 $v$ 的距离
  • 图中任意两点的最长路称为直径
  • 弱连通 省略有向图的方向,图是连通的
  • 单侧连通 至少有一个节点到另一个节点是可达的
  • 强连通 任意两个结点之间是连通的
    • 至少包含一个回路并且包含每个节点一次
    • 强分图 具有强连通性质的最大子图
      • 每个节点位于且仅位于一个强分图中
    • 单侧分图 具有单侧连通性质最大子图
    • 弱分图 具有弱连通性质的最大子图
  • 邻接矩阵
    • 计算长度为 $l$ 的路
  • 可达矩阵
    • $B_n=A+A^2+\dots +A^n$ 然后将不为0的位置替换为1
    • 改为布尔矩阵进行运算
    • 使用 warshall 算法

特殊图

欧拉图 -> 边

欧拉路: 存在一个路,经过图中每个边有且仅有一次
欧拉回路:存在一个回路,经过图中每个边有且仅有一次
欧拉图: 具有欧拉回路

在无向图判断是否存在

  • 具有一条欧拉路,当且仅当 $G$ 是连通的并且有零个或两个奇数度数的结点
  • 具有一条欧拉回路,当并且仅当 $G$ 是连通的并且所有的结点度数为偶数

汉密尔顿图 -> 点

汉密尔顿路:存在一条路经过每个结点恰好一次
汉密尔顿回路:存在一条回路经过每个结点恰好一次
汉密尔顿图: 具有汉密尔顿回路

判断是否为汉密尔顿图(汉密尔顿回路)的必要条件(只能证明不是,但是不能证明一定是):
一个图有汉密尔顿汇率,则对于结点集 $V$ 的每个非空子集 $S$ 均有 $W(G-S) \leq |S|$ 成立。 $G-S$ 表示删去一些点后的子图,$W(G-S)$ 则表示连通分支数。
也就是说,删除任意的结点后的图,其中的连通分支数要小于等于删去结点的数量。如果大于删去结点的数量,则说明一定不是汉密尔顿图。
彼得森图满足这个条件但是并不是一个汉密尔顿图

汉密尔顿路充分条件(不是汉密尔顿图;只能证明一定存在,但反之不能证明不存在)
对于一个结点数为 $n$ 的图, 图中的每一对结点,其度数之和大于等于 $n-1$ ,则图中存在一条汉密尔顿路

平面图

平面图:图中的任何两条边除了顶点之外没有任何交点
:边所包围的一个不包含结点、边的区域称为一个面,在图形之外,还有一个无限面
面的次数:围成面得回路的边的个数,记作 $deg(r)$(结点的度数也是 $deg$)

在一个有限平面图里,面的次数之和等于边的两倍(算了两次)
欧拉定理必要条件):一个连通的平面图,有 $v$ 个结点 $e$ 个边 $r$ 个面,则 $v-e+r=2$ 成立

$G$ 是有 $v$ 个结点, $e$ 条边的简单平面图,若 $v \geq 3$,则 $e \geq 3v-6$

$K_{3,3} K_5$ 不是平面图(用欧拉定理证明)

同胚:如果两个图同构,或者是在反复插入删除度数为2的结点后同构,则称两图在 2 度结点内同构,也就是同胚
Kuratowski定理:一个图是平面图,当且仅当他不包含与 $K_{3,3} K_5$ 同胚的子图,

,连通且无回路的无向图,度数不为1的结点为内点或分枝点
森林,无回路的无向图,每个联通分图是树

树的等价定义

  1. 无回路的连通图
  2. 无回路且 $e=v-1$
  3. 连通且 $e=v-1$
  4. 无回路,但增加一条边得到有且仅有一条回路
  5. 连通,但是删去任意一边不连通
  6. 每一对结点之间有且仅有一条路

任意一棵树至少有两片树叶

生成树,图的子图是一颗树,则树为图的生成树

  • 生成树的边叫做树枝
  • 不在生成树中的边称为
  • 弦的集合为生成树的
    连通图至少有一颗生成树

:$m-n+1$ 称为连通图的秩,$n$ 是节点数,$m$ 是边数,这个公式也就是生成生成树要删去的边的数量($m-(n-1)=m-n+1$)

Kruskal算法
贪心算法,选最小边权

根树及其应用

有向树:有向图忽略方向是一棵树
根数:恰有一个结点入度为零,其余结点入度都为1
:出度为0
分枝点、内点:出度不为0
递归定义:每个结点都可以看做原来树的某子树的根。

m叉树:所有点的出度小于等于 m
完全m叉树:所有点的出度恰好等于 m
正则m叉树:树叶均在同一层

m叉改二叉:P331

定理: 完全m叉树,树叶为 $t$,分枝点数为 $i$,则 $(m-1)i=t-1$

通路长度:从根到结点的通路的边数,记作 $L(w)$

  • 分枝点称为内部通路
  • 树叶为外部通路
    完全二叉树有 $n$ 个分枝点,内部通路长度总和为 $I$,外部通路长度总和为 E,则 $E=I+2n$

带权二叉树叶子结点带权

最优树P332
最优树的子节点可以合并到父节点,同样是最优树

前缀码:互不为前缀

任意一棵二叉树的树叶对应一个前缀码
任何一个前缀码对应一个二叉树

  • 左为0,右为1

构造最优二叉树

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇