图论第九章-第一讲

第一章：图论基本概念

1.定义

平凡图/非平凡图 简单图/复合图 空图 n阶图 连通图/非连通图

完全图

nK



1

2nnn

mK



偶图

,mnK

完全偶图

,mnmKmn

K正则图

图和补图，自补图  自补图判定方法

定点的度

dv

最小度

最大度

握手定理

2dvm

图的度序列与图序列，图序列判定方法（注意为简单图）

图的频序列

2.图运算

删点/删边 图并/图交/图差/图对称差 图联 积图/合成图

111122,uadjvuvuadjv或

超立方体

3.连通性

途径迹路

 图G不连通，其补图连通

 一个图是偶图当且仅当它不包含奇圈

4.最短路算法（b t A T）

5.矩阵描述

邻接矩阵及其性质，图的特征多项式

关联矩阵

6.极图？？

L补图 完全L部图 完全L几乎等部图

托兰定理

第二章：树

1.定义

树：连通的无圈图 森林

树的中心和树的形心？ 入<=sqrt(2m(n-1)/n)生成树 根树 出度 入度 树根 树叶 分支点 m元根树 完全m元根树

2.性质

 每棵非平凡树至少有两片树叶

 图G是树当且仅当G中任意两点都被唯一的路连接

 T是(n,m)树，则m = n – 1 

具有k个分支的森林有n-k条边

 每个n阶连通图边数至少为n-1（树是连通图中边的下界）每个连通图至少包含

一棵生成树

3.计算

生成树计数

递推计数法：

GGeGe



关联矩阵计数法：去一点后，每个非奇异阵对应一棵生成树

最小生成树（边赋权）

避圈法

破圈法

完全m元树：

11mit

第三章：图的连通性

1. 割边、割点和块（性质使用反证法）

割边：

wGewG

边e为割边当且仅当e不在任何圈中

割点：

wGvwG

v是无环连通图G的一个顶点，v是G的割点当且仅当V(G-e)可以被划分为两个子

集，v在两个子集内点互连的路上

块：没有割点的连通子图

学必求其心得，业必贵于专精

1．双曲线定义

平面内与两个定点F1，F2的距离的差的绝对值等于常数(小于｜F1F2|)的点的轨迹叫做双曲线．这两个定点叫做双曲线的焦点,两焦点间的距离叫做双曲线的焦距．

集合P＝｛M｜｜｜MF1|－｜MF2｜|＝2a｝，|F1F2｜＝2c，其中a，c为常数且a〉0，c〉0。

(1）当2a<｜F1F2｜时，P点的轨迹是双曲线;

(2）当2a＝|F1F2｜时，P点的轨迹是两条射线；

(3）当2a〉|F1F2｜时,P点不存在．

2．双曲线的标准方程和几何性质

标准方程

错误!－错误!＝1（a〉0，b〉0) y2a2－错误!＝1(a〉0，b〉0) 学必求其心得，业必贵于专精 图形

性质 范围 x≥a或x≤－a，y∈R x∈R，y≤－a或y≥a

对称性 对称轴：坐标轴 对称中心:原点

顶点 A1（－a,0)，A2(a，0） A1（0，－a)，A2（0，a)

渐近线 y＝±错误!x y＝±错误!x

离心率 e＝错误!，e∈(1,＋∞）,其中c＝错误!

实虚轴 线段A1A2叫做双曲线的实轴，它的长|A1A2|＝2a；线段B1B2叫做双曲线的虚轴，它的长|B1B2|＝2b;a叫做双曲线的实半轴长，b叫做双曲线的虚半轴长

a、b、c的关c2＝a2＋b2 (c>a>0，c>b〉0） 学必求其心得，业必贵于专精 系

【知识拓展】

巧设双曲线方程

（1)与双曲线错误!－错误!＝1（a>0，b〉0)有共同渐近线的方程可表示为错误!－错误!＝t（t≠0)．

（2)过已知两个点的双曲线方程可设为错误!＋错误!＝1(mn〈0)．

【思考辨析】

判断下列结论是否正确（请在括号中打“√"或“×”）

(1）平面内到点F1（0，4)，F2（0，－4）距离之差的绝对值等于8的点的轨迹是双曲线．( × ）

(2）方程错误!－错误!＝1（mn〉0）表示焦点在x轴上的双曲线．（ × ）

(3)双曲线方程错误!－错误!＝λ(m〉0，n>0,λ≠0)的渐近线方程是错误!－错误!＝0,即错误!±错误!＝0.( √ ）

第6章 图论

一、内容提要

1. 图的定义

定义1.(图的定义一)

图G = (V, E)是一个系统，其中

(1)V是一个有限集合；V中的每一元素vV都称为图G的一个结点；V称为图G的结点集；

(2)E是一个有限集合；E中的每一元素eE都称为图G的一条边；E称为图G的边集。

定义2. (图的定义二)

图G = (V, E)是一个系统，其中

(1)V 是一有限集合；V中的每一元素vV都称为图G的一个结点；V称为图G的结点集；

(2)EVV是一有限集合，一个V上的关系；E中的每一元素(u,v)E都称为图G的一条边 (这里u, vV)；E称为图G的边集。

定义3. (图的定义三)

图G= (V,, E)是一个系统，其中

(1)V 是一有限集合；V中的每一元素vV都称为图G的一个结点；V称为图G的结点集；

(2)是一有限集合；中的每一元素都称为图G中的一个标号；称为图G的标号集；

(3)E VV是一有限集合，一个三元关系；E中的每一元素(u, ,v)E都称为图G的一条边或弧,此边起自u而终于v ；称u是此边的起点，称是此边的标号，称v是此边的终点 ，起点和终点统称为边的端点(这里u, vV , )；E称为图G的边集。

定义4. (图的定义四)

图G=(V,E, )是一个系统，其中

(1)V 是一有限集合； V中的每一元素vV都称为图G的一个结点； V称为图G的结点集；

(2)E是一个有限集合； E中的每一元素eE都称为图G的一条边； E称为图G的边集。

(3)是边到结点集的一个关联函数，即

:E2V (无向图) 或 :E VV (有向图) 。

一般来说，它将E中的每条边eE与结点集V中的一个二元子集{u,v}2V (或{u,v}V)相关联或与结点集V上的一个二元组(u,v)VV相关联，即

1 子图

子图(subgraph) H  G  V(H)  V(G) , E(H)  E(G) 。

真子图 H  G。

母图（super graph）。

生成子图（spanning subg.）  H  G 且V(H) = V(G) 。

生成母图。

基础简单图 （underlying simple g.）。

导出子图（induced subg.）G[V’], (非空V’ V )

 以V’为顶点集，以G中两端都在V’上的边全体为边集构成的G的子图。

边导出子图 G[E’] 非空E’  E

 以E’为边集，以E’中所有边的端点为顶点集的的子图。

G[{c, d, e}]G[{f, c]}

例。

eabcdfghG=(V, E)xwvyuG[{u,w,x,y}]G[{u,w,x}]

以上两种子图，其实，对应于取子图的两种基本运算。下面是取子图的另两种基本运算：

G - V’  去掉V’及与V’相关联的一切边所得的剩余子图。

 即 G[V \ V’]

G - E’  从中去掉E’ 后所得的生成子图

例。G - {b, d, g}, ( = G[E \ {b, d, g}] )

G - {b, c, d, g}, (  G[E \ {b, c, d, g}] )

G - {a, e, f, g}. (  G[E \ {a, e, f, g}] )

注意 G[E \ E’] 与G - E’ 虽有相同的边集，但两者不一定相等 ： 后者一定是生成子图，而前者则不然。

上述四种运算是最基本取子图运算，今后老要遇到，一定要认真掌握好。关于子图的一些定义还有：

G + E’  往G上加新边集E’ 所得的（G的母）图。