图论及其应用

<b>推论2.2：每棵非平凡树至少有两个1度顶点</b>

<b>定理2.3：e是G的割边当且仅当e不包含在G的一个圈中</b>

<b>定理2.4：一个连通图是树当且仅当它的每条边都是割边</b>

<b>定理2.5：设T是图G的生成树，并且e是G的不在T中的一条边，则T+e包含唯一的圈</b><br>

边割：删去边割图连通分支会变多

余树：生成树的补

<b>推论2.7：每个非平凡的无环连通图，至少有两个不是割点的顶点</b>

用τ(G)记G的生成树的棵数

半Euler图：一个图包含Euler迹，但不包含Euler环游

Euler图：一个图包含Euler环游

Fleury算法

半Hamilton图：具有Hamilton路但不含Hamilton圈的图

Hamilton图：具有Hamilton圈的图

<div><b>推论4.3：设无向图G=(V,E)是半Hamilton图，那么对于任意∅≠S⊂V，均有ω(G-S)≤|S|+1</b></div>

<b>引理4.6：c(G)是唯一确定的</b>

<b>推论4.7：设G是v≥3的简单图。若c(G)是完全图，则G是Hamilton图&nbsp;</b>

M-可扩路：是指其起点和终点都是M非饱和顶点的M-交错路

<b>推论6.2：若G是k正则偶图（k＞0），则G有完美对集</b>

最小覆盖：G没有覆盖K'，使得|K' |&lt;|K|

o(G)表示G的奇分支个数

<b>推论6.4：每个没有割边的3正则图都有完美对集</b>

独立集：设S是V的一个子集，若S中任意两个顶点在G中均不相邻，则S是G的一个独立集

覆盖：V的子集K，使得G的每条边都至少有一个端点属于K

独立数：G的最大独立集的顶点数称为G的独立数，记为α(G)

覆盖数：G的最小覆盖的顶点数称为G的覆盖数，记为β(G)

<b>定理8.1：设S⊆V，则S是G的独立集当且仅当V\S是G的覆盖。</b>

边覆盖：G的一个边覆盖是指E的一个子集L，使得G的每个顶点都是L中某条边的端点

边独立集：即对集

<div>边独立数和边覆盖数：最大对集的边数称为边独立数，记作α′G;</div><div>最小边覆盖的边数称为边覆盖数，记作β′(G)</div>

<b>定理8.2(Gallai)：若δ&gt;0,则α'+β'=υ</b>

<div>&nbsp;设J是平面上的一条Jordan曲线，平面的剩下部分被分成两个不相交的开集，称为J的内部和外部，分别记为int J和ext J，并且用Int J和Ext J表示它们的闭包</div>

Int J∩Ext J=J

<b>Jordan曲线定理：连接int J的点和ext J的点的任何连线，必在某点和J相交</b><br>

用F(G)和ϕ(G)表示平图G中面的集合和面的个数

每个平图恰有一个无界的面，称为外部面

用b(f)表示平图G中面f的周界

面f的度：dG(f)是指和f关联的边的条数(即b(f)中边的条数，其中割边被计算两次)

若e是平图G的环，则e* 是G*的割边，反之亦然

当G是连通图，则G**≅G

同构的图的不同平面嵌入的对偶图可能不同构

υ(G* )=ϕ(G)<br>ε(G* )=ε(G)<br>d_(G* ) (f* )=d_G (f) &nbsp; 对所有f∈F(G)成立 &nbsp;<br>

<b>推论10.7.1：给定的连通平面图的所有平面嵌入有相同的面数</b>

<b>推论10.7.2：若G是υ≥3的简单平面图，则ε≤3υ-6</b>

<b>推论10.7.3：<span>若</span><span lang="EN-US">G</span><span>是简单平面图，则</span></b><!--[if gte msEquation 12]><m:oMath><span<br> lang=EN-US style='font-size:14.0pt;font-family:"Cambria Math","serif";<br> mso-fareast-font-family:宋体;mso-fareast-theme-font:minor-fareast;mso-bidi-font-family:<br> "Times New Roman";mso-bidi-theme-font:minor-bidi;mso-ansi-language:EN-US;<br> mso-fareast-language:ZH-CN;mso-bidi-language:AR-SA'><m:r><m:rPr><m:scr m:val="roman"></m:scr><m:sty<br> m:val="p"/></m:rPr>δ≤5</m:r></span></m:oMath><![endif]--><!--[if !msEquation]--><b><span lang="EN-US"><!--[if gte vml 1]><v:shapetype<br> id="_x0000_t75" coordsize="21600,21600" o:spt="75" o:preferrelative="t"<br> path="m@4@5l@4@11@9@11@9@5xe" filled="f" stroked="f"><br> <v:stroke joinstyle="miter"></v:stroke><br> <v:formulas><br> <v:f eqn="if lineDrawn pixelLineWidth 0"></v:f><br> <v:f eqn="sum @0 1 0"></v:f><br> <v:f eqn="sum 0 0 @1"></v:f><br> <v:f eqn="prod @2 1 2"></v:f><br> <v:f eqn="prod @3 21600 pixelWidth"></v:f><br> <v:f eqn="prod @3 21600 pixelHeight"></v:f><br> <v:f eqn="sum @0 0 1"></v:f><br> <v:f eqn="prod @6 1 2"></v:f><br> <v:f eqn="prod @7 21600 pixelWidth"></v:f><br> <v:f eqn="sum @8 21600 0"></v:f><br> <v:f eqn="prod @7 21600 pixelHeight"></v:f><br> <v:f eqn="sum @10 21600 0"></v:f><br> </v:formulas><br> <v:path o:extrusionok="f" gradientshapeok="t" o:connecttype="rect"></v:path><br> <o:lock v:ext="edit" aspectratio="t"></o:lock><br></v:shapetype><v:shape id="_x0000_i1025" type="#_x0000_t75" style='width:33.6pt;<br> height:16.2pt'><br> <v:imagedata src="file:///C:\Users\huangyq\AppData\Local\Temp\msohtmlclip1\01\clip_image001.png"<br> o:title="" chromakey="white"/><br></v:shape><![endif]--><!--[if !vml]--><!--[endif]--></span>δ≤5</b><!--[endif]-->

<b>推论10.7.4：K_5 是非平面图</b>

设C是图G的一个圈

一个图是非平面图当且仅当它的同态图也是非平面图

若能用k种颜色给G进行正常面着色，就称G是k面可着色的。

若G是k面可着色的，但不是(k−1)面可着色的，就称G的面色数为k，记作χ∗(G)=k。

最大度：∆(G)

最小度：δ(G)

有向图

度数为偶数（奇数）的点称为偶点（奇点）

<b>推论1.1：任何图中奇度数顶点的个数是偶数</b>

度序列可图化

每列之和为2：每条边关联两个顶点

每行元素之和为该顶点的度数

所有元素之和为边数两倍

无向图的邻接矩阵是对称的

有向图的邻接矩阵中的值为该两点间边的权值

途径W：从v0到vk的一条途径

迹：在途径W中，若边互相不同称为迹

路（径）：在迹W中，点也互相不通，则称W为路

称u,v是连通的，是指u,v之间存在通路

连通图：G中任意两个顶点都是连通的

连通分支ω(G)<span lang="EN-US"><!--[endif]--></span><!--[endif]-->

<b>定理1.3：一个无向图G是偶图当且仅当G中无长度为奇数的圈（奇圈）</b>

（点）连通度：G所具有的k顶点割中最小的k，记做κ(G)<br><span lang="EN-US"><!--[endif]--></span><!--[endif]-->

边连通度：G的所有k边割中最小的k，记做κ' (G)

<b>推论3.2.1：若G是2连通图，则G的任意两个顶点都位于同一个圈上</b>

<b>推论3.2.2：若G是υ≥3的块，则G的任意两条边都位于同一个圈上。</b>

有向迹：途径中边不重复出现

弱连通：图D的基图为连通图（不考虑方向）

单向连通：若D中任意两个顶点要么u→v，要么v→u

强连通：对任意两个顶点互相可达

有向Hamilton圈：该圈经过有向图每一个顶点

显然：在正常着色中，χ'≥Δ&nbsp;

着色正常：任意两个相邻顶点都分配到不同的颜色

<div>若χ(G)=k，则称G是k色的</div>

k临界图是指k色的临界图。每个k色图有k临界子图

<b>推论9.1.1：每个k色图至少有k个度不小于k-1的顶点</b>

<b>推论9.1.2：对任意图G，有χ≤Δ+1</b>

<b>推论9.2：每个临界图都是块</b>

称函数c是N的容量函数，它在弧a上的值称为a的容量

称X中的顶点是N的发点，Y中的顶点是N的收点

既不是发点又不是收点的顶点称为中间点；所有中间点的集合记为I

f流出S的合成流量：f^+ (S)-f^- (S)

f流入S的合成流量：f^- (S)-f^+ (S)

val f=f^+ (X)-f^- (X)

<b>推论11.2：设f是流而K是割，适合val f=cap K。则f是最大流而K是最小割</b>