简单回路算法

‘壹’ 求无向图中的所有简单环路

广搜生成树，补回原来的树边，每补一条，出现一个基本环路，最后将所有的基本环路排列组合去掉公共边就得到所有的简单环路了。NP问题

‘贰’ 证明最长回路问题是NP完全的。

Hamilton回路问题中，两点相连即这两点距离为0，两点不直接相连则令其距离为1，于是问题转化为在TSP问题中，是否存在一条长为0的路径。Hamilton回路存在当且仅当TSP问题中存在长为0的回路。
“问题A可约化为问题B”有一个重要的直观意义：B的时间复杂度高于或者等于A的时间复杂度。也就是说，问题A不比问题B难。这很容易理解。既然问题A能用问题B来解决，倘若B的时间复杂度比A的时间复杂度还低了，那A的算法就可以改进为B的算法，两者的时间复杂度还是相同。正如解一元二次方程比解一元一次方程难，因为解决前者的方法可以用来解决后者。
很显然，约化具有一项重要的性质：约化具有传递性。如果问题A可约化为问题B，问题B可约化为问题C，则问题A一定可约化为问题C。这个道理非常简单，就不必阐述了。具体的可以和我私聊，我和你说说。

‘叁’ 任务：对于给定的n个点和连接这n个点的m条边,用C语言编程计算一笔画回路.

题目很简单，从算法上说，你只要判断每个点与其它的点连接的边数为偶数就可以了，如果满足这个条件，从任意点出发都可以，如果不满足，则不存在一笔画回路

算法如此，代码自己写了

相关数学理论，请google 七桥问题

‘肆’ 求先序线索化二叉树非递归算法

#include "iostream.h"
#include "stdlib.h"
#include "stdio.h"

typedef char ElemType;//定义二叉树结点值的类型为字符型
const int MaxLength=10;//结点个数不超过10个

typedef struct BTNode{
ElemType data;
struct BTNode *lchild,*rchild;
}BTNode,* BiTree;

void CreateBiTree(BiTree &T){//按先序次序输入，构造二叉链表表示的二叉树T，空格表示空树
// if(T) return;
char ch;
ch=getchar(); //不能用cin来输入，在cin中不能识别空格。
if(ch==' ') T=NULL;
else{
if(!(T=(BTNode *)malloc(sizeof(BTNode)))) cout<<"malloc fail!";
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}

void PreOrderTraverse(BiTree T){//先序遍历
if(T){
cout<<T->data<<' ';
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
void InOrderTraverse(BiTree T){//中序遍历
if(T){
InOrderTraverse(T->lchild);
cout<<T->data<<' ';
InOrderTraverse(T->rchild);
}
}
void PostOrderTraverse(BiTree T){//后序遍历
if(T){
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
cout<<T->data<<' ';
}
}
void LevelOrderTraverse(BiTree T){//层序遍历

BiTree Q[MaxLength];
int front=0,rear=0;
BiTree p;
if(T){ //根结点入队
Q[rear]=T;
rear=(rear+1)%MaxLength;
}
while(front!=rear){
p=Q[front]; //队头元素出队
front=(front+1)%MaxLength;
cout<<p->data<<' ';
if(p->lchild){ //左孩子不为空，入队
Q[rear]=p->lchild;
rear=(rear+1)%MaxLength;
}
if(p->rchild){ //右孩子不为空，入队
Q[rear]=p->rchild;
rear=(rear+1)%MaxLength;
}
}

}
//非递归的先序遍历算法
void NRPreOrder(BiTree bt)
{ BiTree stack[MaxLength],p;
int top;
if (bt!=NULL){
top=0;p=bt;
while(p!=NULL||top>0)
{ while(p!=NULL)
{
cout<<p->data;
stack[top]=p;
top++;
p=p->lchild;
}
if (top>0)
{ top--; p=stack[top]; p=p->rchild; }
}
}
}
//非递归的中序遍历算法
void NRInOrder(BiTree bt)
{ BiTree stack[MaxLength],p;
int top;
if (bt!=NULL){
top=0;p=bt;
while(p!=NULL||top>0)
{ while(p!=NULL)
{

stack[top]=p;
top++;
p=p->lchild;
}
if (top>0)
{ top--; p=stack[top];cout<<p->data; p=p->rchild; }
}
}
}
//非递归的后序遍历算法
/*bt是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。
需要判断根结点的左右子树是否均遍历过。
可采用标记法，结点入栈时，配一个标志tag一同入栈
(1：遍历左子树前的现场保护，2：遍历右子树前的现场保护)。
首先将bt和tag(为1)入栈，遍历左子树；
返回后，修改栈顶tag为2，遍历右子树；最后访问根结点。*/

typedef struct
{
BiTree ptr;
int tag;
}stacknode;

void NRPostOrder(BiTree bt)
{
stacknode s[MaxLength],x;
BiTree p=bt;
int top;
if(bt!=NULL){
top=0;p=bt;
do
{
while (p!=NULL) //遍历左子树
{
s[top].ptr = p;
s[top].tag = 1; //标记为左子树
top++;
p=p->lchild;
}

while (top>0 && s[top-1].tag==2)
{
x = s[--top];
p = x.ptr;
cout<<p->data; //tag为R，表示右子树访问完毕，故访问根结点
}

if (top>0)
{
s[top-1].tag =2; //遍历右子树
p=s[top-1].ptr->rchild;
}
}while (top>0);}
}//PostOrderUnrec

int BTDepth(BiTree T){//求二叉树的深度
if(!T) return 0;
else{
int h1=BTDepth(T->lchild);
int h2=BTDepth(T->rchild);
if(h1>h2) return h1+1;
else return h2+1;
}
}

int Leaf(BiTree T){//求二叉树的叶子数
if(!T) return 0;
else if(!T->lchild&&!T->rchild) return 1;
else return(Leaf(T->lchild)+Leaf(T->rchild));
}

int NodeCount(BiTree T){//求二叉树的结点总数
if(!T) return 0;
else return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
}

void main(){
BiTree T;
T=NULL;
int select;
//cout<<"请按先序次序输入各结点的值，以空格表示空树(输入时可连续输入):"<<endl;
// CreateBiTree(T);
while(1){
cout<<"\n\n请选择要执行的操作:\n";
cout<<"1.创建二叉树\n";
cout<<"2.二叉树的递归遍历算法（前、中、后）\n";
cout<<"3.二叉树的层次遍历算法\n";
cout<<"4.求二叉树的深度\n";
cout<<"5.求二叉树的叶子结点\n";
cout<<"6.求二叉树的结点总数\n";
cout<<"7.二叉树的非递归遍历算法（前、中、后）\n"; //此项可选做
cout<<"0.退出\n";
cin>>select;
switch(select){
case 0:return;
case 1:
cout<<"请按先序次序输入各结点的值，以空格表示空树(输入时可连续输入):"<<endl;
CreateBiTree(T);
break;
case 2:
if(!T) cout<<"未建立树，请先建树！";
else{
cout<<"\n先序遍历:\n";
PreOrderTraverse(T);
cout<<"\n中序遍历:\n";
InOrderTraverse(T);
cout<<"\n后序遍历:\n";
PostOrderTraverse(T);
}
break;
case 3:
cout<<"\n层序遍历:\n";
LevelOrderTraverse(T);
break;
case 4:
cout<<"二叉树的深度为:\n";
cout<<BTDepth(T);
break;
case 5:
cout<<"\n叶子节点数:\n";
cout<<Leaf(T);
break;
case 6:
cout<<"总节点数:\n";
cout<<NodeCount(T);
break;
case 7:
if(!T) cout<<"未建立树，请先建树！";
else{
cout<<"\n先序遍历:\n";
NRPreOrder(T);
cout<<"\n中序遍历:\n";
NRInOrder(T);
cout<<"\n后序遍历:\n";
NRPostOrder(T);
}
break;
default:
cout<<"请确认选择项:\n";
}//end switch
}//end while

}

‘伍’ 拓扑排序，不知道哪里错了，总是存在回路啊

拓扑排序
有向无回路图又称为dag。对这种有向无回路图的拓扑排序的结果为该图所有顶点的一个线性序列，满足如果G包含(u,v)，则在序列中u出现在v之前（如果图是有回路的就不可能存在这样的线性序列)。一个图的拓扑排序可以看成是图的所有顶点沿水平线排成的一个序列，使得所有的有向边均从左指向右。因此，拓扑排序不同于通常意义上对于线性表的排序。

有向无回路图经常用于说明事件发生的先后次序，图1给出一个实例说明早晨穿衣的过程。必须先穿某一衣物才能再穿其他衣物(如先穿袜子后穿鞋)，也有一些衣物可以按任意次序穿戴(如袜子和短裤)。图1(a)所示的图中的有向边(u,v)表明衣服u必须先于衣服v穿戴。因此该图的拓扑排序给出了一个穿衣的顺序。每个顶点旁标的是发现时刻与完成时刻。图1(b)说明对该图进行拓扑排序后将沿水平线方向形成一个顶点序列，使得图中所有有向边均从左指向右。

下列简单算法可以对一个有向无回路图进行拓扑排序。

procere Topological_Sort(G);
begin
1.调用DFS(G)计算每个顶点的完成时间f[v];
2.当每个顶点完成后，把它插入链表前端;
3.返回由顶点组成的链表;
end;
图1(b)说明经拓扑排序的结点以与其完成时刻相反的顺序出现。因为深度优先搜索的运行时间为θ(V+E)，每一个v中结点插入链表需占用的时间为θ(1)，因此进行拓扑排序的运行时间θ(V+E)。

图1 早晨穿衣的过程

为了证明算法的正确性，我们运用了下面有关有向无回路图的重要引理。

引理1

有向图G无回路当且仅当对G进行深度优先搜索没有得到反向边。

证明：

→：假设有一条反向边(u,v)，那么在深度优先森林中结点v必为结点u的祖先，因此G中从v到u必存在一通路，这一通路和边(u,v)构成一个回路。

←：假设G中包含一回路C，我们证明对G的深度优先搜索将产生一条反向边。设v是回路C中第一个被发现的结点且边(u,v)是C中的优先边，在时刻d[v]从v到u存在一条由白色结点组成的通路，根据白色路径定理可知在深度优先森林中结点u必是结点v的后裔，因而(u,v)是一条反向边。(证毕)

定理1

Topological_Sort(G)算法可产生有向无回路图G的拓扑排序。

证明:

假设对一已知有问无回路图G=(V,E)运行过程DFS以确定其结点的完成时刻。那么只要证明对任一对不同结点u,v∈V，若G中存在一条从u到v的有向边，则f[v]<f[u]即可。考虑过程DFS(G)所探寻的任何边(u,v)，当探寻到该边时，结点v不可能为灰色，否则v将成为u的祖先，(u,v)将是一条反向边，和引理1矛盾。因此，v必定是白色或黑色结点。若v是白色，它就成为u的后裔，因此f[v]<f[u]。若v是黑色，同样f[v]<f[u]。这样一来对于图中任意边(u,v)，都有f[v]<f[u]，从而定理得证。（证毕）

另一种拓扑排序的算法基于以下思想：首先选择一个无前驱的顶点（即入度为0的顶点，图中至少应有一个这样的顶点，否则肯定存在回路），然后从图中移去该顶点以及由他发出的所有有向边，如果图中还存在无前驱的顶点，则重复上述操作，直到操作无法进行。如果图不为空，说明图中存在回路，无法进行拓扑排序；否则移出的顶点的顺序就是对该图的一个拓扑排序。

下面是该算法的具体实现：

procere Topological_Sort_II(G);
begin
1 for 每个顶点u∈V[G] do d[u]←0; //初始化d[u],d[u]用来记录顶点u的入度

2 for 每个顶点u∈V[G] do
3 for 每个顶点v∈Adj[u] do d[v]←d[v]+1; //统计每个顶点的入度

4 CreateStack(s); //建立一个堆栈s

5 for 每个顶点u∈V[G] do
6 if d[u]=0 then push(u,s); //将度为0的顶点压入堆栈

7 count←0;

8 while (not Empty(s)) do
begin
9 u←top(s); //取出栈顶元素
10 pop(s); //弹出一个栈顶元素
11 count←count+1;
12 R[count]←u; //线性表R用来记录拓扑排序的结果

13 for 每个顶点v∈Adj[u] do //对于每个和u相邻的节点v
begin
14 d[v]←d[v]-1;
15 if d[v]=0 then push(v,s); //如果出现入度为0的顶点将其压入栈
end;
end;

16 if count<>G.size then writeln('Error! The graph has cycle.')
17 else 按次序输出R;
end;
上面的算法中利用d[u]来记录顶点u的入度，第2-3行用来统计所有顶点的入度，第5-6行将入度为0的顶点压入堆栈，第8-15行不断地从栈顶取出顶点，将该顶点输出到拓扑序列中，并将所有与该顶点相邻的顶点的入度减1，如果某个顶点的入度减至0，则压入堆栈，重复该过程直到堆栈空了为止。显而易见该算法的复杂度为O(VE)，因为第2-3行的复杂性就是O(VE)，后面8-15行的复杂性也是O(VE)。这个算法虽然简单，但是没有前面一个算法的效率高。

‘陆’ 图论割集问题

回答楼主,图论大多问题的解决,需要用到遍历算法,判断割集我想不会有其它算法,遍历的算法目前是图论中最基本最重要的算法,当然对一些特殊的图可能会有其它方法.遍历算法的计算复杂度不是很大的,是多项式算法,在计算机上可以实现.当然在选取边和点时应考虑技巧性,这恐怕是个难题,否则会出现组合爆炸,就象货郎担问题一样,比如选择点可以首先考虑选取度数最大的点,选取边一定要选不在回路上的边.这需要你的智慧.
割集分为点割集和边割集,对一个图G=(V,E)来说如果存在一个结点集V的子集,从G中删除这些结点后,它的连通分图的个数增多,则称该子集为点割集,对一个连通图来说,删除这些结点后,连通图变为不连通.点割集一般不是唯一的,含有最小结点个数的点割集称为最小点割集,类似可定义边割集和最小边割集,仅含1个点的点割集称为割点,仅含1个边的边割集称为割边,割边也称为桥.
求一个连通简单图的割集的算法,我想可用遍历的算法,目前常用的是深度优先搜索或者广度优先搜索算法来做,这是图论中最基本的算法,这种算法可求出图的连通分图的个数,以此来判断某子集是否是割集.

‘柒’ 三个电阻并联在电路中，总电阻怎么求

简单的算法是利用公式：R=R1R2/R1+R2。先求两电阻并联的总电阻R12，再把R12看成和R3并联，再利用上面公式计算出三电阻并联的总电阻。例如把2Ω、3Ω，6Ω三电阻并联求总电阻。可先求3Ω、6Ω的总电心算可得2Ω，再和2Ω并联算它们的总电阻得1Ω。总电阻就快速求出来非常方便。。

‘捌’ 已知功率180KW，电压380V，怎么求电流怎么求视在功率怎么求功率因数

180kw的额定电流I=P/1.732UcosΦ=180/1.732/0.38/0.8=180/0.53=340A。

视在功率S=1.732UI=1.732X0.38X340=224KVA；

功率因数cosΦ=P/S=180/250=0.75。负荷低于180KW,功率因数低于0.75，负荷高于180KW,功率因数高于0.75。

视在功率是表示交流电器设备容量的量。等于电压有效值和电流有效值的乘积。它乘以功率因数等于有功功率。单位为伏安、千伏安。

功率因数（Power Factor）的大小与电路的负荷性质有关， 如白炽灯泡、电阻炉等电阻负荷的功率因数为1，一般具有电感性负载的电路功率因数都小于1。功率因数是电力系统的一个重要的技术数据。功率因数是衡量电气设备效率高低的一个系数。

(8)简单回路算法扩展阅读：

无功功率、有功功率、视在功率之间关系

由于感性、容性或非线性负荷的存在，导致系统存在无功功率，从而导致有功功率不等于视在功率，三者之间关系如下：

S^2=P^2+Q^2；S为视在功率，P为有功功率，Q为无功功率。三者的单位分别为VA（或kVA），W（或kW），var（或kvar）。

简单来讲，在上面的公式中，如果kvar的值为零的话，kVA就会与kW相等，那么供电局发出来的1kVA的电就等于用户1kW的消耗，此时成本效益最高，所以功率因数是供电局非常在意的一个系数。

用户如果没有达到理想的功率因数，相对地就是在消耗供电局的资源，所以这也是为什么功率因数是一个法规的限制。就国内而言功率因数规定是必须介于电感性的0.9～1之间，低于0.9时需要接受处罚。

‘玖’ 求 离散数学（第四版）知识框架

离散数学期末复习要点与重点 第1章 集合及其运算 复习要点 1．理解集合、元素、集合的包含、子集、相等，以及全集、空集和幂集等概念，熟练掌握集合的表示方法．具有确定的，可以区分的若干事物的全体称为集合，其中的事物叫元素.．集合的表示方法：列举法和描述法. 注意：集合的表示中元素不能重复出现，集合中的元素无顺序之分． 掌握集合包含(子集)、真子集、集合相等等概念．注意：元素与集合，集合与子集，子集与幂集，�0�2与�0�0(�0�1),空集�0�4与所有集合等的关系.空集�0�4，是惟一的，它是任何集合的子集．集合A的幂集P(A)＝， A的所有子集构成的集合．若�0�5A�0�5＝n，则�0�5P(A)�0�5=2n．2．熟练掌握集合A和B的并A�0�6B，交A�0�5B，补集~A(~A补集总相对于一个全集).差集A－B，对称差�0�3，A�0�3B＝(A－B)�0�6(B－A)，或A�0�3B＝(A�0�6B)－（A�0�5B）等运算，并会用文氏图表示．掌握集合运算律(见教材第9～11页)(运算的性质).3．掌握用集合运算基本规律证明集合恒等式的方法．集合的运算问题：其一是进行集合运算；其二是运算式的化简；其三是恒等式证明．证明方法有二：(1)要证明A＝B，只需证明A�0�1B，又A�0�8B；(2)通过运算律进行等式推导．重点：集合概念，集合的运算，集合恒等式的证明． 第2章 关系与函数 复习要点1．了解有序对和笛卡儿积的概念，掌握笛卡儿积的运算． 有序对就是有顺序二元组，如<x, y>，x, y的位置是确定的，不能随意放置． 注意：有序对<a，b>�0�1<b,a>，以a, b为元素的集合{a, b}={b, a}；有序对(a, a)有意义，而集合{a, a}是单元素集合，应记作{a}． 集合A，B的笛卡儿积A×B是一个集合，规定A×B＝{<x,y>�0�5x�0�2A,y�0�2B}，是有序对的集合.笛卡儿积也可以多个集合合成，A1×A2×…×An． 2．理解关系的概念：二元关系、空关系、全关系、恒等关系.掌握关系的集合表示、关系矩阵和关系图，掌握关系的集合运算和求复合关系、逆关系的方法． 二元关系是一个有序对集合，，记作xRy． 关系的表示方法有三种：集合表示法， 关系矩阵：R�0�1A×B，R的矩阵. 关系图：R是集合上的二元关系，若<ai, bj>�0�2R，由结点ai画有向弧到bj构成的图形．空关系�0�4是唯一、是任何关系的子集的关系；全关系；恒等关系，恒等关系的矩阵MI是单位矩阵．关系的集合运算有并、交、补、差和对称差．复合关系；复合关系矩阵：(按布尔运算)； 有结合律：(R·S)·T＝R·(S·T)，一般不可交换．逆关系；逆关系矩阵满足：；复合关系与逆关系存在：(R·S)－1=S－1·R－1． 3．理解关系的性质(自反性和反自反性、对称性和反对称性、传递性的定义以及矩阵表示或关系图表示)，掌握其判别方法(利用定义、矩阵或图，充分条件)，知道关系闭包的定义和求法．注：(1)关系性质的充分必要条件：① R是自反的�0�4IA�0�1R；②R是反自反的�0�4IA�0�5R＝�0�4；③R是对称的 �0�4R＝R－1；④R是反对称的�0�4R�0�5R－1�0�1IA；⑤R是传递的�0�4R·R�0�1R. (2)IA具有自反性，对称性、反对称性和传递性．EA具有自反性，对称性和传递性．故IA，EA是等价关系．�0�4具有反自反性、对称性、反对称性和传递性．IA也是偏序关系．4．理解等价关系和偏序关系概念，掌握等价类的求法和作偏序集哈斯图的方法．知道极大(小)元，最大(小)元的概念，会求极大(小)元、最大(小)元、最小上界和最大下界． 等价关系和偏序关系是具有不同性质的两个关系. 知道等价关系图的特点和等价类定义，会求等价类． 一个子集的极大(小)元可以有多个，而最大(小)元若有，则惟一.且极元、最元只在该子集内；而上界与下界可以在子集之外．由哈斯图便于确定任一子集的最大(小)元，极大(小)元．5．理解函数概念：函数(映射)，函数相等，复合函数和反函数．理解单射、满射和双射等概念，掌握其判别方法． 设f是集合A到B的二元关系，"a�0�2A，存在惟一b�0�2B，使得<a, b>�0�2f，且Dom(f)=A，f是一个函数(映射)．函数是一种特殊的关系．集合A×B的任何子集都是关系，但不一定是函数．函数要求对于定义域A中每一个元素a，B中有且仅有一个元素与a对应，而关系没有这个限制． 二函数相等是指：定义域相同，对应关系相同，而且定义域内的每个元素的对应值都相同． 函数有：单射——若；满射——f(A)=B或使得y=f(x)；双射——单射且满射． 复合函数 即．复合成立的条件是：．一般，但.反函数——若f：A�0�3B是双射，则有反函数f－1：B�0�3A， ， 重点：关系概念与其性质，等价关系和偏序关系，函数. 第3章 图的基本概念 复习要点 1．理解图的概念：结点、边、有向图，无向图、简单图、完全图、结点的度数、边的重数和平行边等.理解握手定理． 图是一个有序对<V，E>，V是结点集，E是联结结点的边的集合．掌握无向边与无向图，有向边与有向图，混合图，零图，平凡图、自回路(环)，无向平行边，有向平行边等概念．简单图，不含平行边和环(自回路)的图、 在无向图中，与结点v(�0�2V)关联的边数为结点度数(v)；在有向图中，以v(�0�2V)为终点的边的条数为入度－(v)，以v(�0�2V)为起点的边的条数为出度＋(v)，deg(v)=deg+(v) +deg－(v)．无向完全图Kn以其边数；有向完全图以其边数．了解子图、真子图、补图和生成子图的概念．生成子图——设图G＝<V, E>，若E�0�4�0�1E，则图<V, E�0�4>是<V, E>的生成子图． 知道图的同构概念，更应知道图同构的必要条件，用其判断图不同构.重要定理：(1) 握手定理 设G=<V，E>，有；(2) 在有向图D＝<V, E>中，；(3) 奇数度结点的个数为偶数个． 2．了解通路与回路概念：通路(简单通路、基本通路和复杂通路)，回路(简单回路、基本回路和复杂回路)．会求通路和回路的长度．基本通路(回路)必是简单通路(回路)． 了解无向图的连通性，会求无向图的连通分支．了解点割集、边割集、割点、割边等概念．了解有向图的强连通强性；会判别其类型．设图G＝<V，E>，结点与边的交替序列为通路．通路中边的数目就是通路的长度．起点和终点重合的通路为回路．边不重复的通路(回路)是简单通路(回路)；结点不重复的通路(回路)是基本通路(回路). 无向图G中，结点u, v存在通路，u, v是连通的，G中任意结点u, v连通，G是连通图．P(G)表示图G连通分支的个数． 在无向图中，结点集V�0�4�0�0V，使得P(G－V�0�4)>P(G)，而任意V�0�5�0�0V�0�4,有P（G－V�0�5）＝P(G)，V�0�4为点割集. 若V�0�4是单元集，该结点v叫割点；边集E�0�4�0�0E，使得P(G－V�0�4)>P(G)，而任意E�0�5�0�0E�0�4，有P（G－E�0�5）＝P(G)，E�0�4为边割集．若E�0�4是单元集，该边e叫割边(桥)．要知道：强连通单侧连通弱连通，反之不成立．3．了解邻接矩阵和可达矩阵的概念，掌握其构造方法及其应用．重点：图的概念，握手定理，通路、回路以及图的矩阵表示． 第4章 几种特殊图 复习要点1．理解欧拉通路(回路)、欧拉图的概念，掌握欧拉图的判别方法．通过连通图G的每条边一次且仅一次的通路(回路)是欧拉通路(回路)．存在欧拉回路的图是欧拉图. 欧拉回路要求边不能重复，结点可以重复．笔不离开纸，不重复地走完所有的边，走过所有结点，就是所谓的一笔画．欧拉图或通路的判定定理 (1)无向连通图G是欧拉图�0�4G不含奇数度结点(即G的所有结点为偶数度)； (2)非平凡连通图G含有欧拉通路�0�4G最多有两个奇数度的结点； (3)连通有向图D含有有向欧拉回路�0�4D中每个结点的入度＝出度．连通有向图D含有有向欧拉通路�0�4D中除两个结点外，其余每个结点的入度＝出度，且此两点满足deg－(u)－deg＋(v)＝±1．2．理解汉密尔顿通路(回路)、汉密尔顿图的概念，会做简单判断．通过连通图G的每个结点一次，且仅一次的通路(回路)，是汉密尔顿通路(回路)．存在汉密尔顿回路的图是汉密尔顿图. 汉密尔顿图的充分条件和必要条件 (1)在无向简单图G=<V，E>中，�0�5V�0�5�0�63，任意不同结点，则G是汉密尔顿图．(充分条件) (2)有向完全图D＝<V，E>, 若，则图D是汉密尔顿图. (充分条件)(3) 设无向图G=<V，E>，任意V1�0�0V，则W(G－V1)�0�5�0�5V1�0�5(必要条件)若此条件不满足，即存在V1�0�0V，使得P(G－V!)>�0�5V1�0�5,则G一定不是汉密尔顿图(非汉密尔顿图的充分条件)．3．了解平面图概念，平面图、面、边界、面的次数和非平面图．掌握欧拉公式的应用．平面图是指一个图能画在平面上，除结点之外，再没有边与边相交． 面、边界和面的次数等概念．重要结论：(1)平面图．(2)欧拉公式：平面图 面数为r，则(结点数与面数之和＝边数＋2)(3)平面图． 会用定义判定一个图是不是平面图． 4．理解平面图与对偶图的关系、对偶图在图着色中的作用，掌握求对偶图的方法．给定平面图G＝〈V，E〉，它有面F1，F2，…，Fn，若有图G*＝〈V*，E*〉满足下述条件： ⑴对于图G的任一个面Fi，内部有且仅有一个结点vi*∈V*；⑵对于图G的面Fi，Fj的公共边ek，存在且仅存在一条边ek*∈E*，使ek*＝(vi*，vj*)，且ek*和ek相交； ⑶当且仅当ek只是一个面Fi的边界时，vi*存在一个环ek*和ek相交；则图G*是图G的对偶图．若G*是G的对偶图，则G也是G*的对偶图．一个连通平面图的对偶图也必是平面图．5．掌握图论中常用的证明方法．重点：欧拉图和哈密顿图、平面图的基本概念及判别． 第5章 树及其应用 复习要点1．了解树、树叶、分支点、平凡树、生成树和最小生成树等概念，掌握求最小生成树的方法．连通无回路的无向图是树．树的判别可以用图T是树的充要条件(等价定义)．注意：(1) 树T是连通图； (2)树T满足m＝n－1（即边数=顶点数-1）．图G的生成子图是树，该树就是生成树．每边指定一正数，称为权，每边带权的图称为带权图．G的生成树T的所有边的权之和是生成树T的权，记作W(T)．最小生成树是带权最小的生成树．2．了解有向树、根树、有序树、二叉树、二叉完全树、正则二叉树和最优二叉树等概念．了解带权二叉树、最优二叉树的概念，掌握用哈夫曼算法求最优二叉树的方法．有向图删去边的方向为树，该图为有向树． 对非平凡有向树，恰有一个结点的入度为0(该结点为树根)，其余结点的入度为1，该树为根树． 每个结点的出度小于或等于2的根树为二叉树；每个结点的出度等于0或2的根树为二叉完全树；每个结点的出度等于2的根树称为正则二叉树． 有关树的求法：(1)生成树的破圈法和避圈法求法；(2)最小生成树的克鲁斯克尔求法；(3) 最优二叉树的哈夫曼求法重点：树与根树的基本概念，最小生成树与最优二叉树的求法. 第6章 命题逻辑 复习要点 1．理解命题概念，会判别语句是不是命题．理解五个联结词：否定�0�1P、析取�0�3、合取�0�2、条件�0�3、和双条件�0�0及其真值表，会将简单命题符号化．具有确定真假意义的陈述句称为命题．命题必须具备：其一，语句是陈述句；其二，语句有唯一确定的真假意义. 2．了解公式的概念(公式、赋值、成真指派和成假指派)和公式真值表的构造方法．能熟练地作公式真值表．理解永真式和永假式概念，掌握其判别方法．判定命题公式类型的方法：其一是真值表法，其二是等价算法.3．了解公式等价概念，掌握公式的重要等价式和判断两个公式是否等价的有效方法：等价算法、列真值表法和主范式方法． 4．理解析取范式和合取范式、极大项和极小项、主析取范式和主合取范式的概念，熟练掌握它们的求法． 命题公式的范式不惟一，但主范式是惟一的． 命题公式A有n个命题变元，A的主析取范式有k个极小项，有m个极大项，则 于是有(1) A是永真式�0�4k=2n(m=0)； (2) A是永假式�0�4m＝2n(k=0)； 求命题公式A的析取(合取)范式的步骤：见教材第174页．求命题公式A的主析取(合取)范式的步骤：见教材第177和178页． 5．了解C是前提集合{A₁,A₂,…,A_m}的有效结论或由A1, A2, …, Am 逻辑地推出C的概念．要理解并掌握推理理论的规则、重言蕴含式和等价式，掌握命题公式的证明方法：真值表法、直接证法、间接证法．重点：命题与联结词，公式与解释，真值表，公式的类型及判定，主析取(合取)范式，命题演算的推理理论. 第7章 谓词逻辑复习要点1．理解谓词、量词、个体词、个体域，会将简单命题符号化．原子命题分成个体词和谓词，个体词可以是具体事物或抽象的概念，分个体常项和个体变项．谓词用来刻划个体词的性质或之间的关系． 量词分全称量词"，存在量词$. 命题符号化注意：使用全称量词"，特性谓词后用�0�3；使用存在量词$，特性谓词后用�0�2．2．了解原子公式、谓词公式、变元(约束变元和自由变元)与辖域等概念．掌握在有限个体域下消去公式的量词和求公式在给定解释下真值的方法．由原子公式、联结词和量词构成谓词公式．谓词公式具有真值时，才是命题． 在谓词公式"xA或$xA中，x是指导变元，A是量词的辖域．会区分约束变元和自由变元．在非空集合D(个体域)上谓词公式A的一个解释或赋值有3个条件． 在任何解释下，谓词公式A取真值1，A为逻辑有效式(永真式)；公式A取真值0，A为永假式；至少有一个解释使公式A取真值1，A称为可满足式．在有限个体域下，消除量词的规则为：设D＝{a₁, a₂,…, a_n}，则会求谓词公式的真值，量词的辖域，自由变元、约束变元，以及换名规则、代入规则等．掌握谓词演算的等价式和重言蕴含式．并进行谓词公式的等价演算．3．了解前束范式的概念，会求公式的前束范式的方法. 若一个谓词公式F等价地转化成 ，那么就是F的前束范式，其中Q1，Q2，…，Qk只能是"或$，而x1, x2,…, xk是个体变元，B是不含量词的谓词公式．前束范式仍然是谓词公式． 4．了解谓词逻辑推理的四个规则．会给出推理证明． 谓词演算的推理是命题演算推理的推广和扩充，命题演算中基本等价式，重言蕴含式以及P，T，CP规则在谓词演算中仍然使用．谓词逻辑的推理演算引入了US规则(全称量词指定规则)，UG规则(全称量词推广规则)，ES规则(存在量词指定规则)，EG规则(存在量词推广规则)等.重点：谓词与量词，公式与解释，谓词演算．