簡單迴路演算法

『壹』 求無向圖中的所有簡單環路

廣搜生成樹，補回原來的樹邊，每補一條，出現一個基本環路，最後將所有的基本環路排列組合去掉公共邊就得到所有的簡單環路了。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規則(存在量詞推廣規則)等.重點：謂詞與量詞，公式與解釋，謂詞演算．