正己烷的碳链, 分子式及分子模型
CH3CH2CH2CH2CH2CH3
2) C7H16的构造异构体
正庚烷
题 求单环环烷烃的分子通式CxHy. 解 G e 是树:
4(x − 2) + 3·2 + 1·y = 2m; m = [(x 2) + 2 + y] − 1. 解得 y = 2x. 答 单环环烷烃分子通式 CnH2n.
n
=
2k
+
C
2k,而边数
m
=
(4C
2 k
+
32k)/2,
代入欧拉公
式,
得面数
r
=
C
2 k
+
k
+
2,
其中有一个是外部面.
4 维超立方图是第一类的.
例11(1)
4边着色?
9.(4分)图9中所示的图叫做托特图. 用最少颜色给托特图的面着色. 在表
4 示每个面的空白处填数字表示所着颜色. 有两个面已经分别着了第1, 第2
平面图非哈密顿性的判断
格林堡定理 设 G 是无环的平面图, 将 G 嵌入平面. 如果 G 存在一条哈密顿回路 C, 那么
ni=2 (i 2)(fi gi) = 0,
这里 数.
fi
和
gi
分别是在
C
内部和外部的次数为
i
的面的个
5 个 4 次面, 2 个 5 次面. 2(f4 g4) + 3(f5 g5) = 2(4 1) + 3(2 0) = 0.
单环环烷烃分子通式为 CnH2n, 例如 环已烷 C6H12
第十七章 平面图及图的着色
§17.1 平面图的基本概念 §17.2 欧拉公式 §17.3 平面图的判断 §17.4 平面图的对偶图 §17.5 图中顶点的着色 §17.6 地图的着色与平面图的点着色 §17.7 边着色
例 广义彼得松图 P9, 4 是可平面图( ).
(b) , 哈密顿的有 无, 半哈密顿的有
(a. )
(a)
(b)
(c)
†两个粉红点互不可达
例 下面各图中, 图 (a) (b) 是强连通的, 图
密顿的, 图
是半(c哈) 密顿的.
_(b是) 哈
(a)
(b)
(c)
例 下面各图中, 图(a), (b), (c)是强连通的, 图(b)是哈密顿 的, 图(c)是半哈密顿的.
=
2
时
G
是
一共有 6 个.
例 画出下图的直边图解, 使交叉的边对最少.
交叉数 = 2
例 下面三个图是同构的(). 分别用最少颜色给它们的边 着色.
(a) P9, 4
(b) P9, 2
(c)
3
2
2
3
1
2
3
1
颜 色 的 标 涂示
色

1
13
1 23
旁
1
标
2
1
3
数
21
字
3
21 3
画
2
V
V
2
1
V
3
凯 莱 英
([ ].1 8 5 7)
题 求烷烃(饱和碳氢化合物)的分子通式CxHy.
解 化合物分子结构图: 无环, 连通, 无平行边(单键). 烷烃的是树: m = (x + y) − 1, 4 x + 1 y = 2m; 解得 y = 2x + 2. 答 烷烃分子通式CnH2n+2.
9
1 个 9 次面, 3 个 8 次面, 其余 5 次面.
第十八章 支配集, 覆盖集, 独立集与匹配
§16.1支配集, 点覆盖集, 点独立集 §16.2边覆盖集与匹配 §16.3二部图中的匹配
例1(a) 下图 有 1个最小支配集, 有 个7最大匹配.
例1(b) 下图 有 10个最小边覆盖.
(a)P8, 2
(b) P8, 3
(c)
(d)
第十五章 欧拉图与哈密顿图
§15.1 欧拉图 §15.2 哈密顿图 §15.3 带权图与货郎担问题
例 对下图加最少的边, ①使之成为简单欧拉图, ②使之成 为简单哈密顿图.
例 对下图加最少的边, 使之成为简单欧拉图.
例 下面各图中, 是强连通的有 (b,)单连通的有 (a)
例1(c) 下图 有 3个最小点覆盖, 有 个4极小点覆盖.
† 点独立集与点覆盖互为补集, 独立数与点覆盖数互
为“补数” 0 + 0 = n.
例2(a) 下图有 6 个完美匹配.
例2(b) 下图有 8 个最小支配集.
例2(c) 下图有 2 个最大独立集.
例 下图的支配数 0 = 2, 点独立数 0 = , 点6覆盖数0
m 27 l n 2 5 18 2 80 26.6
l2
52
3
例 画出所有正则的极大平面图.
解 由握手定理, k 正则图满足 kn = 2m. 而 n (n 3) 阶简单 极大平面图有 m = 3n 6条边, 从而 (6 k)n = 12 (n 3). 可 见 n 是 12 的因子: 3, 4, 6, 12.
(a)
(b)
(c)
第十六章 树
§16.1 无向树及其性质 §16.2 生成树
例下图 G 有 21 个生成树, 其中不同构的有 3 个.
题 求证连通图删除一个边割集后恰有两个连通分支.
证 假如 G – B 有2个分支, 含顶点集 V1, V2, 而 V3 是其 余顶点集. G 中有一条边 e 联结 V3 与 V1 V2, 因 e 不 在 G – B, 所以 e 在 B 中. G (B {e}) = G B + {e} 是 不连通的, 这与 B 是边割集矛盾.
横
23
截
线
例 分别用最少颜色给下面两个图着色.
(a)
(b)
例 某校有 9 个学生: a, b, c, d, e, f, g, h, i, j, 修读 8 门课程:

1: a, b, c, d 5: a, h, j

2: a, c, d, e 6: h, i, j

3: b, d, f, g 7: g, h, j
数 0 = 3, 这意味着一天至多安排 1
3 场考试.
2
8
5
3 4
6 7
例 图(a)与图(b)同构( ). 图(a)是自对偶图( ).
(a)
(b)
以课程为顶点, 若两门课程有公共学生, 则在它们之间连边. 得图 G.
1
图的每一种着色, 把顶点(小
组)集合划分为若干个类(色
组), 同类小组相互间没有公
现他们要选出图书采购员. 要求每个人都与某位采购 员有至少一个科目的共同爱好. 应该选谁, 才能使采购员人 数最少?
然后他们将围绕圆桌聚餐, 要求每个人与身边的人至 少有一个科目的共同爱好, 有几种排位方案?
解 作二部图 G1 = V, U, E1, V = {a, b, c, d, e, f, g, h}, U = {语, 数, 英, 理, 化, 史, 地, 生}, E1 = {(v, u)| v V, u U, v 爱好 u}.

4: c, f, g, h 8: e, I
每门课程考试要安排一整天. 有相同学生的课程考试不能
同时进行. 考试至少需要安排几天? 一天内最多安排几场?
解 以课程为顶点, 有公共学生的课程之间连边. 得图 G.
图的每一种着色, 把顶点(课程)按 1
颜色分为若干个类(色组), 同色课
程可以安排在同一天考试.
n = 46, m = 69 找出偶圈的生成并
边色数 ' = 3
例G(3) 求Grinberg46图的最小面着色.
4 3
21
14
2
1
4
2 3
31 31
2
32
4
2
3
1
12
3
面色数 * = 4
n = 46, m = 69
例 求Grinberg42图的最小边着色. n = 42, m = 63
= .5
p(G V) = 6 > |V| = 5.
不是哈密顿图.
点覆盖数 >点独立数就一定不是哈密顿图
极大平面图不都是哈密顿的.
n = 11, m = 27 3 个 8 度, 2 个 6 度, 6 个 3 度.
4 个最小支配集, 1 个最小点覆盖.
例 某村有 8 个青年: a, b, c, d, e, f, g, h, 分别爱好{语}, {语, 数}, {英, 物}, {语, 化,生}, {数, 英, 史}, {物, 化, 地}; {史, 地}, {史, 地, 生}.
甲烷Leabharlann 乙烷丙烷丁烷
异丁烷
构造由碳链确定
已烷
(1)已烷(C6H14 )的构造异构体的碳链及分子式
CH3CH2CH2CH2CH2CH3
碳 链 是 阶 树

CH3CH2C| H2CH3 CH3
CH3CH2C| HCH2CH3 CH3
C| H3 CH3C| CH2CH3
CH3
6
CH3C|HCH| CH3 H3C CH3
第十四章 图的基本概念
§14.1 图 §14.2 通路与回路 §14.3 图的连通性 §14.4 图的矩阵表示 §14.5 图的运算 * 补充 离心率, 直径, 半径, 周长, 围长等
例 图G中u 到 v 有 7 条路径, 有很多条简单通路. G 中有 10 个圈, 3 个点割集, 15 个边割集.