当前位置：文档之家 › 离散数学第七章第五节详解

离散数学第七章第五节详解

  • 格式：ppt
  • 大小：265.50 KB
  • 文档页数：13

下载文档原格式

  / 13

合集下载

离散数学第七章计数

离散数学第七章计数

离散数学第七章计数离散数学7.1基本计数原理1.加法原理2.乘法原理离散数学加法原理加法原理又称为和计数原理，也称和规则，存在三种表述形式，其本质是说，整体等于其部分之和。

①若集合某是不相交非空子集S1,S2,…,Sm的并，则|某|=m|Si1i|②若E1,E2,…,Em是彼此互斥事件，并且E1发生有e1种方式，E2发生有e2种方式，…,Em发生有em种方式，则E1或E2或…或Em发生有e1+e2+…+em种方式。

应该指出的是，事件E1和E2互斥是说，E1和E2发生但两者不能同时发生。

离散数学③如果选择事物O1有n1种方法，选择事物O2有n2种方法，…,选择事物Om有nm种方法，并且选择诸事物方法不重叠，则选取O1或O2或…或Om有n1+n2+…+nm种方法。

离散数学加法原理例7.1.1一个学生想选修一门数学课或一门生物学课，但不能同时选修两门课。

如果该生对5门数学课和3门生物学课具有选课条件，试问该生有多少方式来选修课程？离散数学乘法原理乘法原理又称有序计数原理，也称积规则，类似加法原理，也有三种表述形式。

①若S1,S2,…,Sm是非空集合，则笛卡尔m积S1S2…Sm的元素个数是|Si|i1②若事件E1,E2,…,Em发生分别有e1,e2,…,em种方式，并且诸事件是独立的，则事件E1或E2或··m依次发生有e1e2…em·或E种方式。

离散数学乘法原理③如果选取事物O1,O2,…,Om分别有n1,n2,…,nm种方法，并且选取诸事物方法不重叠，则事物O1与O2与…与Om依次选取有n1n2…nm种方法。

离散数学乘法原理例7.1.2一个学生要选修两门课，第一门课在上午4小时内任选1小时，第二门课在下午3小时内也可任选1小时，试问该生有多少种可能的时间安排？离散数学乘法原理例7.1.3计数因特网地址。

在由计算机的物理网络互连而构成的因特网中，每台计算机的网络连接被分配一个因特网地址。

离散数学左孝凌答案

离散数学左孝凌答案

离散数学左孝凌第七章答案【篇一：离散数学（左孝凌）课后习题解答（详细）】1.下列句子中，哪些是命题？哪些不是命题？如果是命题，指出它的真值。

⑴中国有四大发明。

⑵计算机有空吗⑶不存在最大素数。

⑷ 21+3 V5。

（5）老王是山东人或河北人。

⑹2与3都是偶数。

⑺小李在宿舍里。

⑻这朵玫瑰花多美丽呀！⑼请勿随地吐痰！⑽圆的面积等于半径的平方乘以。

何只有6是偶数，3才能是2的倍数。

⑫雪是黑色的当且仅当太阳从东方升起。

㈣如果天下大雨，他就乘班车上班。

解：⑴⑶⑷⑸⑹⑺⑽⑪㈣㈣是命题，其中（1）（3）⑽㈣是真命题，⑷⑹⑫是假命题，⑸⑺㈣的真值目前无法确定；⑵⑻⑼不是命题。

2.将下列复合命题分成若干原子命题。

⑴李辛与李末是兄弟。

⑵因为天气冷，所以我穿了羽绒服。

⑶天正在下雨或湿度很高。

⑷刘英与李进上山。

⑸王强与刘威都学过法语。

⑹如果你不看电影，那么我也不看电影。

⑺我既不看电视也不外出，我在睡觉。

⑻除非天下大雨，否则他不乘班车上班。

解：⑴本命题为原子命题；⑵p：天气冷；q：我穿羽绒服；⑶p：天在下雨；q：湿度很高；⑷p：刘英上山；q：李进上山；⑸p：王强学过法语；q：刘威学过法语;⑹p：你看电影；q：我看电影；⑺p：我看电视；q：我外出；r：我睡觉；⑻p：天下大雨；q：他乘班车上班。

3.将下列命题符号化。

⑴他一面吃饭，一面听音乐。

⑵3是素数或2是素数。

⑶若地球上没有树木，则人类不能生存。

⑷8是偶数的充分必要条件是8能被3整除。

⑸停机的原因在于语法错误或程序错误。

⑹四边形abcd是平行四边形当且仅当它的对边平行。

⑺如果a和b是偶数，则a+b是偶数。

解：⑴p：他吃饭；q：他听音乐；原命题符号化为：p人q⑵p：3是素数；q：2是素数；原命题符号化为：pv q⑶p：地球上有树木；q：人类能生存；原命题符号化为：？p-?q⑷p：8是偶数；q：8能被3整除；原命题符号化为：p?q⑸p：停机；q：语法错误；r：程序错误；原命题符号化为：qv r—p⑹p：四边形abcd是平行四边形；q：四边形abcd的对边平行；原命题符号化为：p?q。

离散数学第7章

离散数学第7章

1 v2e4v4e3v3e2v2
初级回路(圈)
2 v2e5v5e6v4e3v3e2v2
初级回路(圈)
3 v2e4v4e3v3e2v2e5v5e6v4e3v3e2v2 复杂回路
…………
5、图中最短的回路。 如图：
6、性质。
定理：在一个
n
阶图中，若从顶点vi
到
v
存在
j
通路(vi vj ) ，则从 vi 到 vj 存在长度小于等于
n 1的通路。
推论：在一个
n
阶图中，若从顶点vi
到
v
存在
j
通路(vi vj ) ，则从 vi 到 vj 存在长度小于等于
n 1的初级通路。
6、性质。
定理：在一个 n 阶图中，若vi 到自身存在回路， 则从 vi 到自身存在长度小于等于n 的回路。 推论：在一个 n 阶图中，若vi 到自身存在一个 简单回路，则从vi到自身存在长度小于等于 n
如例1的(1)中，
v1
v5
e1与 v1, v2 关联的次数均为1， e1
e6
e2 与 v2 关联的次数为2， e2 v2 e4 e5
v4
边 e1, e4, e5, e6都是相邻的， v5 为孤立点，v4 为悬挂点，
e3 v3
e6 为悬挂边，e2 为环，e4, e5 为平行边，重数2，
G 为多重图。
孤立点——无边关联的点。
环——一条边关联的两个顶点重合，称此边
为环 (即两顶点重合的边)。
3、相关概念。 (2) 悬挂点——只有一条边与其关联的点，所
对应的边叫悬挂边。 (3) 平行边——关联于同一对顶点的若干条边
称为平行边。平行边的条数称为重数。 多重图——含有平行边的图。 简单图——不含平行边和环的图。

离散数学7-树

离散数学7-树

(b)
(a)
V5
2
1
V7
8
9
V2
V4
2
3
V8
5
V1
V1
V4
V5
1
3
V7
V6
8
V4
2
V8
5
6
V1
1
V5
6
V7
V6
8
3
V8
5
6
V7
9
V3
(e)
V3
(f)
(g)
22
V2
V3
(h)
五.应用举例——求最小生成树
例3 用管梅谷算法求下图的最小生成树。
23
五.应用举例——求最小生成树
例3 用管梅谷算法求下图的最小生成树。
成圈。
首先证明T无简单回路。对n作归纳证明。
(i) n=1时,m=n-1=0,显然无简单回路；
(ii)假设顶点数为n-1时无简单回路，现考察顶点数是n的情况：此时至少有一
个顶点v其次数d(v)=1。因为若n个顶点的次数都大于等于2，则不少于n条边，但这与
m=n-1矛盾。
删去v及其关联边得到新图T’，根据归纳假设T’无简单回路，再加回v及其关联
边又得到图T，则T也无简单回路。
再由图的连通性可知，加入任何一边后就会形成圈，且只有一个圈，否则原图
中会含圈。
9
二. 基本定理——证明
证明(4):(3)(4)，即证一个无圈图若加入任一边就形成圈，
则该图连通，且其任何一边都是桥。
若图不连通,则存在两个顶点vi和vj，在vi和vj之间没有路，若
加边(vi,vj)不会产生简单回路，但这与假设矛盾。由于T无简单回

离散数学课后习题答案第七章

离散数学课后习题答案第七章

第七章 特 殊 图 类习题7.11．解 因 m=n-1,这里m=6,所以n=6+1=7.2．解 不正确。

与平凡图构成的非连通图中有4个结点3条边，但是它不是树。

3K 3．证明 必要性。

因为G 中有n 个结点，边数m=n-1，又因为G 是连通的，由本节定理1可知，G 为树，因而G 中无回路。

再证充分性。

因为G 中无回路，又因为边数m=n-1，由本节定理1，可知G 为树，所以G 是连通的。

4．解 因 m=n-r,这里n=15,r=3,所以m=15-3=12，即G 有12条边。

5．解6个结点的所有不同构的树如图7-1所示。

图7-16．证明 由定理1，在任意的树中，边数),(m n 1−=n m；所以，由握手定理得)1(22)(1−==∑=n m v d ni i①⑴若T 没有树叶，则由于T 是连通图，所以T 中任一结点均有，从而2)(≥i v d n v d ni i2)(1≥∑= ②则①与②矛盾。

⑵若树T 仅有1片树叶，则其余1−n个结点的度数不小于2，于是121)1(2)(1−=+−≥∑=n n v d ni i③从而①、③相矛盾。

综合⑴，⑵得知T 中至少有两片树叶。

7．解 图7-2⑴中共有两棵非同构的生成树（如图7-3⑴，⑵）。

图7-2⑵中共有3棵非同构的生成树（如图7-3⑶，⑷，⑸）。

⑵⑴⑶⑷ ⑸图7-38．解 在图7-4中共有8棵生成树，如图7-5⑴～⑻所示，第i 生成树用表示。

，，，)8,,2,1( =iT i 7)(8=T W 8)()(61==T W T W 6)()(52==T W T W )()(73==T W T W 9)(4=T W 。

其中T 2，T 5是图中的最小生成树。

9．解 最小生成树T 如图7-7所示，W （T ）=18。

a bc da b cda ba bcdabc d⑴⑵⑶⑷⑸⑹⑺ ⑻图7-5图7-4图7-6图7-7习题7.21．解 不一定是。

如图7-8就不是根树.2．解 五个结点可形成3棵非同构的无向树，如图7-9⑴，⑵，⑶所示。

第7章 图论 [离散数学离散数学(第四版)清华出版社]

第7章 图论 [离散数学离散数学(第四版)清华出版社]

6/27/2013 6:02 PM
第四部分：图论（授课教师：向胜军）
21
例：
a j i h c g d
1(a)
无 向 图
b
f
e

2(b)
7(j) 8(g) 9(d) 10(i)
6(e)
3(c) 4(h)
5(f)
6/27/2013 6:02 PM
第四部分：图论（授课教师：向胜军）
22
例：
1(b)
有向图
第四部分：图论（授课教师：向胜军）
6
[定义] 相邻和关联
在无向图G中，若e=(a, b)∈E，则称a与 b彼此相邻(adjacent)，或边e关联 (incident) 或联结(connect) a, b。a, b称为边e的端点或 结束顶点(endpoint)。 在有向图D中，若e=<a, b>∈E，即箭头 由a到b，称a邻接到b，或a关联或联结b。a 称为e的始点(initial vertex)，b称为e的终点 (terminal/end vertex)。
证明思路：将图中顶点的度分类，再利用定理1。
6/27/2013 6:02 PM 第四部分：图论（授课教师：向胜军） 9
[定理3] 设有向图D=<V, E>有n个顶点，m 条边，则G中所有顶点的入度之和等于所 有顶点的出度之和，也等于m。
即：
d ( v i ) d ( v i ) m.
i 1 i 1
n
n
证明思路：利用数学归纳法。
6/27/2013 6:02 PM
第四部分：图论（授课教师：向胜军）
10
一些特殊的简单图：
(1) 无向完全图Kn(Complete Graphs)

离散数学(第二版)第7章格和布尔代数和

第七章 格和布尔代数
离散数学(第二版)第7章格和布尔代 数和
第七章 格和布尔代数
7.1 格 与 子 格
本章将讨论另外两种代数系统——格与布尔代数， 它 们与群、 环、 域的基本不同之处是： 格与布尔代数的基集 都是一个偏序集。 这一序关系的建立及其与代数运算之间 的关系是介绍的要点。 格是具有两个二元运算的代数系统， 它是一个特殊的偏序集， 而布尔代数则是一个 特殊的格。
于是， 我们有下列对偶原理。
第七章 格和布尔代数
定理7.1.2 如果命题P在任意格〈L， 〉上成立， 则
将L中符号∨， ∧，
∧， ∨，
P*在任意格〈L， 〉上也成立， 这里P*称为P的对偶式。
在上述对偶原理中， “如果命题P在任意格〈L， 〉
上成立”的含义是指当命题P中的变量取值于L中， 且上确
界运算为∨， 下确界运算为∧， 则P对于它们也成立。
第七章 格和布尔代数
再设a=a∧b， 则a∨b=(a∧b)∨b=b(由吸收律)， 即
a∨b=b。
最后， 设b＝a∨b， 则由a a∨b可得a b。
因此， (1)中3个命题的等价性得证。
(2) 因为 a a∨b， a a∨c, 故a (a∨b)∧(a∨c)。 又
因为
b∧c b a∨b b∧c c a∨c
条件是b a, 则〈L, 也是偏序集。 我们把偏序集〈L, 和〈L, 称为是相互对偶的。 并且它们所对应的哈
斯图是互为颠倒的。 关于格我们有同样的性质。 定理7.1.1 若〈L, 是一个格， 则〈L, 也是一
个格, 且它的并、 交运算∨r, ∧r对任意a, b∈L满足 a∨rb=a∧b，a∧rb=a∨b
证明 先证幂等性成立。 由吸收律知 a∧a＝a∧(a∨(a∧b))＝a a∨a＝a∨(a∧(a∨b))＝a

离散数学第七章课后答案

离散数学习题答案习题二及答案：（P38）5、求下列公式的主析取范式，并求成真赋值： （2）()()p q q r ⌝→∧∧解：原式()p q q r ⇔∨∧∧q r ⇔∧()p p q r ⇔⌝∨∧∧()()p q r p q r ⇔⌝∧∧∨∧∧37m m ⇔∨，此即公式的主析取范式， 所以成真赋值为011，111。

6、求下列公式的主合取范式，并求成假赋值： （2）()()p q p r ∧∨⌝∨解：原式()()p p r p q r ⇔∨⌝∨∧⌝∨∨()p q r ⇔⌝∨∨4M ⇔，此即公式的主合取范式， 所以成假赋值为100。

7、求下列公式的主析取范式，再用主析取范式求主合取范式： （1）()p q r ∧∨解：原式()(()())p q r r p p q q r ⇔∧∧⌝∨∨⌝∨∧⌝∨∧()()()()()()p q r p q r p q r p q r p q r p q r ⇔∧∧⌝∨∧∧∨⌝∧⌝∧∨⌝∧∧∨∧⌝∧∨∧∧ ()()()()()p q r p q r p q r p q r p q r ⇔⌝∧⌝∧∨⌝∧∧∨∧⌝∧∨∧∧⌝∨∧∧ 13567m m m m m ⇔∨∨∨∨，此即主析取范式。

主析取范式中没出现的极小项为0m ，2m ，4m ，所以主合取范式中含有三个极大项0M ，2M ，4M ，故原式的主合取范式024M M M ⇔∧∧。

9、用真值表法求下面公式的主析取范式： （1）()()p q p r ∨∨⌝∧ 解：公式的真值表如下：由真值表可以看出成真赋值的情况有7种，此7种成真赋值所对应的极小项的析取即为主析取范式，故主析取范式1234567m m m m m m m ⇔∨∨∨∨∨∨习题三及答案：（P52-54）11、填充下面推理证明中没有写出的推理规则。

前提：,,,p q q r r s p ⌝∨⌝∨→结论：s证明：① p 前提引入②p q⌝∨前提引入③ q ①②析取三段论④q r⌝∨前提引入⑤ r ③④析取三段论⑥r s→前提引入⑦ s ⑤⑥假言推理15、在自然推理系统P中用附加前提法证明下面推理：（2）前提：()(),()∨→∧∨→p q r s s t u结论：p u→证明：用附加前提证明法。

《离散数学》课件-第七章 图的基本概念

• 〔u，v〕∈E1〔f(u)，f(v)〕∈E2 • (或<u，v>∈E1 <f(u)，f(v)>∈E2) • 且重数相同，则称G1同构于G2，记为
• G1 G2。
• 显然，两图的同构是相互的，即G1同构 于G2，G2同构于G1。
• 由同构的定义可知，不仅结点之间要具 有一一对应关系，而且要求这种对应关 系保持结点间的邻接关系。对于有向图 的同构还要求保持边的方向。
V={a,b,c,d},E={e1,e2,e3,e4,e5,e6}
e1=(a,b), e2=(a,c), e3=(b,d), e4=(b,c), e5=(d,c), e6=(a,d).
它的图形如下图(a)或(b)所示:
a
a
b
d
b
d
c
c
(a)
(b)
如果有些边是有向边，另一些边是无向边， 图G称为混合图。
第七章 图的基本概念
– 7.1 无向图及有向图 – 7.2 通路、回路、图的连通性 – 7.3 图的矩阵表示 – 7.4 最短路径及关健路径
7.1 无向图和有向图
• 什么是图?可用一句话概括，即：图是用 点和线来刻划离散事物集合中的每对事 物间以某种方式相联系的数学模型。
Konigsberg(哥尼斯堡)七桥问题
为偶数.
定理7.2 在任何有向图中,所有结点的入度之 和必等于它们的出度之和.
证明:因为有向图中的每一条有向边都恰好对应 一个出度和一个入度.故所有结点的出度之 和恰好等于有向边的总数.同样地, 所有结 点的入度之和恰好也等于有向边的总数.因 此它们相等.
设V={v1,…,vn}为G的顶点集，则称{d(v1),…d(vn)} 为G的度数序列。
• 如果G2无孤立结点，且由E2所唯一确定，即 以E2为边集，以E2中边关联的结点全体为顶 点集，则称G2是边集E2的导出子图。

离散数学第七章图的基本概念


4.无向图的连通性
若无向图G中任何两顶点都连通,则称G是连通图.
对于任意的无向图G.设V1,V2,…,Vk是顶点之间连通关系的 等价类,则称他们的导出子图为G的连通分支.用p(G)表示G 的连通分支数.
V1 e1
e2 e3
V3
e4 V2
V4
a
de
h
i
b
c
f
g
5.有向图的连通性
若略去有向图D中各边的键头,所得无向图是无向连通图,则 称D是弱连通图(或称D是连通图).
(2) mij d (vi )(i 1,2,..., n)
j 1
mn
nm
n
(3) mij mij d(vi ) 2m
j1 i1
i1 j1
i 1
m
(4) mij 0 vi是孤立点 j 1
(5)若第j列与第k列相同, 则说明e j与ek为平行边.
2.有向图的关联矩阵
设有向图D=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em} 1, vi为ej的始点
e1,e2,e3},{e1,e2,
e2
e4},{e9}等边割集 ,e9是桥.
e3 V4
e5 e6
V5 e4
V6
e9
V7
7.3 图的矩阵表示
1.无向图的关联矩阵
设无向图G=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em}
令mij为顶点vi与ej的关联次数, 则称(mij)n×m为G的关联矩阵.记为M(G)
若Γ 满足:vi-1,vi为ei的端点(若G为有向图,vi-1是ei的始 点,vi是ei的终点)i=1,2,…,k,则称Γ 为G中通路,v0,vk分 别称为通路的始点和终点,Γ 中边的数目k称为通路长度.
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
5
2、欧拉公式（2）
推论1 设G是有v个结点、e条边的连通简单平面图，且v3，则 e3v-6
证：设G的面数为r,当v=3,e=2时，公式成立。当e3时，因G为 简单图，每面的次数不小于3。根据定理1可知，2e3r,即 r2e/3。再应用欧拉公式得：
v-e+2e/32 即 e3v-6。
推论1给出了结点数大于等于3的连通简单平面图应满足的 必要条件，所以可用来判断某些图不是平面图。
将平面图G的一个边不交叉的图画在一个平面上，称为图G 的一个平面表示，也叫做相应于G的地图。
定义2 平面图G的某个平面表示将G所在的平面划分成若干区 域，每个区域叫图G的一个面；包围每个面的边称为该面的 边界；边界上边的条数叫该面的次数，面r的次数记作deg(r)。
面积为无限的面叫无限面，或外部面；面积为有限的面叫 有限面，或内部面。
第7-5讲 平面图
1. 平面图的概念 2. 欧拉公式 3. 库拉托夫斯基定理 4. 课堂练习 5. 第7-5讲 作业
1
1、平面图的概念（1）
定义1 能画在一个平面上且任何两边除端点外互不相交的图称 为平面图。 例：判断下面各图是否为平面图。
(1) (2) (3)是平面图，(4)不是平面图。
2
1、平面图的概念（2）
图(1)有6条边， 4个面，每面次 数皆为3。
图(2)有6条边，有3个面， 各面次数之和为12。
4
2、欧拉公式（1）
定理2 设G是连通平面图，有v个结点，e条边，r个面，则 v-e+r=2 (欧拉公式)
证：对边数用归纳法证明。
若G为平凡图，则v=1,e=0,r=1,公式成立。 若G仅有一条边，则v=2,e=1,r=1,公式成立；或v=1,e=1,r=2,公式仍然成 立。 设G有k条边时公式成立。当G有k+1条边时，设其结点数为v，面数为r， 可分两种情况讨论： (1)如G中有度数为1的结点，删除该结点及其关联的一条边得图G’。显然， G’也是连通平面图，设G’的结点数、边数和面数依次为v’、e’=k、r’，按归 纳假设应满足欧拉公式，即 v’-e’+r’=2，亦即(v-1)-(e-1)+r=2，从而有v-e+r=2。 (2)如G中没有度数为1的结点，则在有限面的边界中删除一条边得图G’。 G’也是连通平面图且边数等于k，按归纳假设应满足欧拉公式，即 v’-e’+r’=2，亦即v-(e-1)+(r-1)=2，从而有v-e+r=2。 综上所述，当边数为k+1时公式成立。定理得证。
deg(r1)=3 deg(r2)=5 deg(r3)=4
图(1)有4个面。
图(2)有3个面。
3
1、平面图的概念（3）
定理1 有限平面图各面次数之和等于边数的2倍。
证：因一条边或是两个面的公共边，或在一个面中作为该面 的边界被计算过两次，所以各面次数之和等于边数的两倍。
deg(r1)=3 deg(r2)=5 deg(r3)=4
2=v-e+r v-e+e/2=v-e/2 即 e2v-4。
推论2给出了各面次数大于等于4的连通平面图应满足的必 要条件，所以可用来判断某些图不是平面图。
例如，应用推论1可知K3，3不 是平面图 。因K3，3是连通平面 图，每个面由四条边围成，v=6, 2v-4=8，而e=9，不满足推论给 出的条件。
12
第7-5讲 作业
P317 3，5
13Leabharlann 93、库拉托夫斯基定理（3）
定理3 （Kuratowski定理）一个图是平面图，当且仅当它不 包含与K3,3或K5在二度结点内同构的子图。 用Kuratowski定理来判断某图是平面图的例子： 证明Petersen图是非平面图。
10
4、课堂练习(1)
练习1 应用欧拉公式证明Petersen图是非平面图。
插入或删除2度结点示意图
8
3、库拉托夫斯基定理（2）
欧拉公式可用来判断某些图不是平面图。但不能用来判断 某图是平面图。波兰数学家给出了一个判断平面图的充分必 要条件。 定理3 （Kuratowski定理）一个图是平面图，当且仅当它不
包含与K3,3或K5在二度结点内同构的子图。
（定理3的证明非常复杂，从略）
11
4、课堂练习(2)
练习2 设G是一个连通平面图，且至少有3个结点。则G必 有一个结点u，使得deg(u)5
证：设G=<V,E>，|V|=v，|E|=e。 假定G的每个结点的度数皆大于6，由握手定理可得2e6v，
所以，e3v>3v-6。这与推论1矛盾。故G至少有一个结点u， 使得deg(u)5。
解：Petersen图中，v=10，e=15，从 图上可以看出，每个面由五边围成， 根据定理7-5.1，有限平面图各面次 数之和等于边数的两倍。 如果Petersen图是平面图，则 2e=5r 所以 r=2e/5=6 但是 v-e+r=10-15+6=12 这说明Petersen图不满足欧拉公式， 故它不是平面图。
7
3、库拉托夫斯基定理（1）
欧拉公式可用来判断某些图不是平面图。但不能用来判断 某图是平面图。波兰数学家Kuratowski给出了一个判断平面 图的充分必要条件。为此，先介绍“在二度结点内同构”的 概念。 定义3 给定图G1、G2，如果它们同构，或通过反复插入或删除
度数为2的之后结点它们同构,则称G1与G2在二度结点内同 构。
例如，应用推论1可知K5不是平面图 (以前从直观上得到过这一结论)。因K5是 连通简单平面图，v=5, 3v-6=9，而e=10， 不满足推论给出的条件。
6
2、欧拉公式（3）
推论2 设G是v个结点、e条边的连通平面图，且G的各面的次数 大于等于4，则e2v-4
证：由所设，G的各面边界边数的总和大于等于4r,这里r为G的 面数。因每边为两个面的边界或作为一个面的边界时按两条边 计算，所以2e4r，即re/2。再应用欧拉公式得：