图论产生过程有两个重要问题：
哥尼斯堡城七桥问题（对应欧拉路，一笔画问题）四色定理（对应图染色问题，任一地图可被染四色）设V是一个非空集合,V的一切二元子集之集记作 P 2 ( V ) P_2(V) P2(V),换言之:
P 2 ( V ) = { A ∣ A ⊆ V 且 ∣ A ∣ = 2 } P_2(V) = \{A|A\subseteq V且|A|=2\} P2(V)={A∣A⊆V且∣A∣=2}
设V是一个非空有限集合, E ⊆ P 2 ( V ) E\subseteq P_2(V) E⊆P2(V),二元组 ( V , E ) (V,E) (V,E)称为一个无向图.B中元素为无向图的顶点,V为顶点集,E称为边集,E的元素称为图的边.如果 { u , v } ∈ E , u , v ∈ V \{u,v\} \in E,u,v\in V {u,v}∈E,u,v∈V,则称u与v邻接. 以V为顶点集,E为边集的无向图 ( V , E ) (V,E) (V,E)常用一个字母G来代替,即G=(V,E).如果 ∣ V ∣ = p , ∣ E ∣ = q |V|=p,|E|=q ∣V∣=p,∣E∣=q则称G为一个 ( p , q ) (p,q) (p,q)图.即G是一个具有p个顶点,q个边的图.(1,0)图称为平凡图. 以后常用u,v,w为顶点命名,x,y,z为边命名.如果x={u,v},则称x为这条边的名字,u和v称为边x的断电,这是还说顶点u,v与边x相互关联,还说x是连接节点u和v的边,且记为x=uv或x=vu.若x,y是两条边,并且只有一个公共端点,则 ∣ x ∩ y ∣ = 1 |x\cap y|=1 ∣x∩y∣=1,则称边x与y邻接.
注意:
G是一个V上的反自反且对称的二元关系E的系统.图的图解:每个点旁边写上名,然后边连线.这时得到的线的交点不是图的顶点.不过图解一般也称为图.我们从现在开始研究的都是无向图。几种特殊的图:
带环图.联结一个顶点和它自身的边称为环,有环的图叫带环图.多重图.无向图定义中,两个点最多一条边联结,如果多于一条边,则称该图为多重图.这些边称为多重边.伪图.允许有环和多重边存在的图称为伪图.完全图.G为无向图,若G中任何两个顶点间都有一个边,则称G为完全图,n个顶点的完全图记作 K n K_n Kn.设G=(V,E)为无向图,如果 E = ∅ E=\empty E=∅,则称G为零图.零图是一个没有边的图,但它确实是一个无向图.
设V是一个非空有限集, A ⊆ ( V × V ) ∖ { ( u , u ) ∣ u ∈ V } A\subseteq (V\times V)\setminus \{(u,u)|u\in V\} A⊆(V×V)∖{(u,u)∣u∈V}.二元组D=(V,A)成为一个有向图.V中的元素称为D的顶点,A中元素(u,v)称为D的从u到v的弧或有向边. 对称弧:如x=(u,v)且y=(v,u)均为A的弧,则称x与y为一对对称弧.
不含对称弧的有向图称为定向图. 对应无向图的一些定义:
环.一个从自己到自己的边称为环.多重弧.两个顶点u,v之间有很多个从u到v的有向弧,则称他们为多重弧.带环有向图.允许有环存在的有向图称为带环有向图.多重有向图.允许有多重弧存在的有向图,称为多重有向图.伪有向图.允许环和多重弧存在的有向图称为伪有向图.点集是原点集非空子集,边集是原边集子集的图. 设G=(V,E)是一个图,图 H = ( V 1 , E 1 ) H=(V_1,E_1) H=(V1,E1)称为G的一个子图,其中 V 1 ⊆ V , E 1 ⊆ E V_1 \subseteq V,E_1\subseteq E V1⊆V,E1⊆E且 V 1 V_1 V1非空.
点集是原点集,边集是原边集子集的图. 设G=(V,E)是一个图,图 H = ( V , F ) , F ⊆ E H=(V,F),F\subseteq E H=(V,F),F⊆E是图G的生成子图.
设 G 1 , G 2 G_1,G_2 G1,G2是G的两个子图.如果 G 1 ≠ G G_1\neq G G1=G则称 G 1 G_1 G1是G的真子图.如果 G 1 G_1 G1是 G 2 G_2 G2的子图,则说 G 2 G_2 G2包含 G 1 G_1 G1. 设G的子图H具有某种性质,若G中不存在 1.与H不同的 2.具有此性质 3.且包含H的 4.真子图 ,则称H是具有此性质的极大子图.
设S是G的顶点集V的非空子集,则称G的以S为日顶点集的极大子图称为由S导出的子图,记作 ⟨ S ⟩ = ( S , P 2 ( S ) ∩ E ) \langle S \rangle = (S,P_2(S)\cap E) ⟨S⟩=(S,P2(S)∩E). 于是,S的两个顶点在 ⟨ S ⟩ \langle S \rangle ⟨S⟩中邻接,当且仅当其在G中邻接.
从图解上看,由 V ∖ v V\setminus v V∖v导出的子图是删除v和与v邻接的所有边,记作G-v.类似的我们可以定义G-x(生成子图,不删除点).如果u,v是G中不邻接两个顶点,图 ( V , E ∪ { u , v } (V,E\cup \{u,v\} (V,E∪{u,v}简记成G+uv.
设G=(V,E),H=(U,F)是两个无向图.如果存在一个一一对应 f : V → U f:V\rightarrow U f:V→U使得 u v ∈ E ⇔ f ( u ) f ( v ) ∈ F uv\in E\Leftrightarrow f(u)f(v) \in F uv∈E⇔f(u)f(v)∈F,则称G与H同构,记作 G ≅ H G\cong H G≅H.
设G=(V,E),H=(U,F)是两个图, V = { v 1 , v 2 , … , v p } , U = { u 1 , u 2 , … , u p } V=\{v_1,v_2,\dots,v_p\},U=\{u_1,u_2,\dots,u_p\} V={v1,v2,…,vp},U={u1,u2,…,up}其中p>2.如果对于每个i都有 G − v i ≅ H − u i G-v_i \cong H-u_i G−vi≅H−ui,则 G ≅ H G\cong H G≅H.
设v是G的一个顶点,G中与v关联的边的数目称为顶点v的度.记作 deg v \deg v degv.
G是一个(p,q)图,则G中各顶点度的和等于2q. ∑ deg v = 2 q \sum \deg v = 2q ∑degv=2q.
任一图中,度为奇数的顶点的数目必定为偶数.
引入记号表示图中最大,最小度: δ ( G ) = min v ∈ V { deg v } Δ ( G ) = max v ∈ V { deg v } \delta(G) = \displaystyle \min_{v\in V}\{\deg v\}\\ \Delta(G) = \displaystyle \max_{v\in V}\{\deg v\} δ(G)=v∈Vmin{degv}Δ(G)=v∈Vmax{degv}
图G称为r度正则图,如果 δ ( G ) = Δ ( G ) = r \delta(G) = \Delta(G) = r δ(G)=Δ(G)=r,即G的每个顶点的度都等于r.3度正则图也叫三次图.一个具有p个顶点的p-1度正则图称为p个顶点的完全图,记作 K p K_p Kp.
每个三次图都有偶数个顶点.
度为0的点称为孤立顶点.0度正则图就是零图.
图的最基本的性质是它是否联通，直观上就是它能不能（裂开）分成不相连接的几部分。
设G是一个图，G的一条通道是G的顶点和边的一个交错序列。 v 0 , x 1 , v 1 , x 2 , … , v n − 1 , x n , v n ; x i = v i − 1 v i v_0,x_1,v_1,x_2,\dots,v_{n-1},x_n,v_n;x_i = v_{i-1}v_{i} v0,x1,v1,x2,…,vn−1,xn,vn;xi=vi−1vi n称为通道的长。这样一个通道常称为 v 0 − v n v_0-v_n v0−vn通道，简记作 v 0 v 1 … v n v_0v_1\dots v_n v0v1…vn。当 v 0 = v n v_0 = v_n v0=vn时，称为闭通道。
注意：通道上点和边都可以重复出现，计算通道长的时候，重复的边按重复的次数算。
设G时图，若G中任两个不同顶点间至少有一条路联结，则称G是一个连通图。
一个不连通的图可以被分为互不相连的及部分，每个部分都是连通的，称为一个连通分支，或支。
图G的极大连通子图称为G的一个支。一个图可以有很多支。
设G是一个图，在V上定义二元关系 ≅ \cong ≅如下： ∀ u , v ∈ V , u ≅ v , if u 与 v 之 间 有 一 条 路 \forall u,v\in V,u\cong v,{\text{if}}\ u与v之间有一条路 ∀u,v∈V,u≅v,if u与v之间有一条路 则 ≅ \cong ≅是V上的等价关系,G的支就是关于 ≅ \cong ≅的每个等价类的导出子图.
设G是一个(p,q)图,对G任何两个不相邻顶点u,v始终有 deg u + deg v ≥ p − 1 \deg u + \deg v \geq p-1 degu+degv≥p−1 则G是连通的.
[证明]假设图不是连通的,那么就至少有两个支,取两个不同支上的点,它们度之和最大时p-2.因此得证.
设G是至少有一个顶点不是孤立顶点的图,如果 ∀ v ∈ V , deg v = 2 k \forall v \in V,\deg v = 2k ∀v∈V,degv=2k,则G中一定有圈.
[证明]取一个最长路 P = v 1 v 2 v 3 … v n P=v_1v_2v_3\dots v_n P=v1v2v3…vn,由于 v 1 v_1 v1度大于2,则一定有两个点与它邻接,那么这两个点之中一定有一个对应在原序列中的 v i , i ≥ 3 v_i,i\geq 3 vi,i≥3,这样 v 1 v i v_1v_i v1vi就没被使用,然后我们构造 P ′ = v 1 v 2 … v i v 1 P' = v_1v_2\dots v_i v_1 P′=v1v2…viv1就是一个圈.
G中两个不同的顶点u,v之间有两个不同的路联结,则G中有圈.
[证明]取一个只在一条路上的边x(u,v),然后删去它,则uv之间存在一条路,然后把x加进去,就构成了圈.
类似于正反关系，补图类似于补集的概念。有时转换研究其补图可能会更简单。
设G=(V,E)是一个图,则图 G c = ( V , P 2 ( V ) ∖ E ) G^c=(V,P_2(V)\setminus E) Gc=(V,P2(V)∖E)称为G的补图.如果G与其补图同构,则称G为自补图.
三个顶点的完全图 K 3 K_3 K3称为三角形.
对任一有6个顶点的图G,G中或 G c G^c Gc中有一个三角形.
[证明]取一个v,则在G或 G c G^c Gc中一定有一个图满足与其邻接的三个顶点 v 1 , v 2 , v 3 v_1,v_2,v_3 v1,v2,v3,如果这三个中有两个邻接,那么就与v构成了三角形.如果两两不邻接,则在这个图的补图中这三个就构成了三角形.
拉姆齐问题:任何六个人的团队中,存在三个互相认识的人或互相不认识的人.
拉姆齐数:求一个与两个数n,m有关的最小正整数r(m,n),使得任何有r(m,n)个顶点的图一定含有一个 K m K_m Km或 K n c K_n^c Knc.数r(m,n)称为拉姆齐数.
G=(V,E)为称为偶图,当且仅当其满足以下条件:
V中有一个2-划分 { V 1 , V 2 } \{V_1,V_2\} {V1,V2},使得G的任一条边的两个端点一个在 V 1 V_1 V1中,另一个在 V 2 V_2 V2中.这个偶图有时记为 ( ( V 1 , V 2 ) , E ) ((V_1,V_2),E) ((V1,V2),E).如果 ∀ u ∈ V 1 , v ∈ V 2 \forall u\in V_1,v\in V_2 ∀u∈V1,v∈V2均有 u v ∈ E uv\in E uv∈E,则称这偶图为完全偶图,记为 K ( m , n ) 或 K m , n K(m,n) 或 K_{m,n} K(m,n)或Km,n,其中 ∣ V 1 ∣ = m , ∣ V 2 ∣ = n |V_1|=m,|V_2|=n ∣V1∣=m,∣V2∣=n.
设G是一个图,uv是G的顶点,联结uv的最短路长度称为uv之间的距离,并记为 d ( u , v ) d(u,v) d(u,v).如果u与v间在G中没有路,则定义 d ( u , v ) = ∞ d(u,v) = \infty d(u,v)=∞.
G为偶图的充分必要条件是它的所有圈都是偶数长.
所有具有p个顶点而没有三角形的图中最多有 ⌊ p 2 / 4 ⌋ \lfloor p^2 / 4 \rfloor ⌊p2/4⌋条边.指下取整.
[证明]构造完全偶图.
迹：边不重复的通道
包含图的所有顶点和所有边的闭迹称为欧拉闭迹，存在一条欧拉闭迹的图称为欧拉图。
图G是欧拉图当且仅当G是连通的且每个顶点的度都是偶数。
[证明]根据定理6.3.3不断构造、删除一个圈，最后因为这些圈有公共点，作为连接部分，把这些圈连接起来。
设G是一个连通图，以下命题等价：
G是一个欧拉图G所有顶点的度都是偶数G的边集能划分成若干互相边不相交的圈。包含图的所有顶点和边的迹称为欧拉迹。欧拉迹不一定是欧拉闭迹。
图G有一条非欧拉闭迹的欧拉迹，当且仅当G是连通的，且奇度顶点的个数刚好为两个。
G是连通图，G有2n个奇度顶点， n ≥ 1 n \geq 1 n≥1，则G全部边可以排成n条开迹，而且至少有n条开迹。
路：点不重复的通道
G是一条生成路称为G的哈密顿路。所谓生成路就是包含所有顶点的路。G的一个包含所有顶点的圈称为G的一个哈密顿圈。具有哈密顿圈的图称为哈密顿图。
G是哈密顿图，S是V的非空子集，则 ω ( G − S ) ≤ ∣ S ∣ \omega(G-S) \leq |S| ω(G−S)≤∣S∣.即导出子图的支数小于等于删除的点集的大小。
[证明]： ω ( G − S ) ≤ ω ( H − S ) , H 为 哈 密 顿 圈 \omega(G-S) \leq \omega(H-S),H为哈密顿圈 ω(G−S)≤ω(H−S),H为哈密顿圈。
G是一个 p , p ≥ 3 p,p\geq 3 p,p≥3顶点的图，如果 δ ( G ) ≥ p 2 \delta(G) \geq {p\over 2} δ(G)≥2p,则G是一个哈密顿图。
G是一个 p , p ≥ 3 p,p\geq 3 p,p≥3顶点的图，如果对G任何两个不邻接顶点uv都有 deg u + deg v ≥ p \deg u + \deg v \geq p degu+degv≥p 则G是一个哈密顿图。
G是一个p顶点图，如果G每一对不邻接顶点u和v均有 deg u + deg v ≥ p − 1 \deg u + \deg v \geq p-1 degu+degv≥p−1 则此时G有哈密顿路。
这个东西课件上都是打星号内容
[主要内容]
a i j = { 1 , v i v j ∈ E 0 , v i v j ∉ E a_{ij} = \begin{cases}1,v_iv_j \in E\\0,v_iv_j \notin E\end{cases} aij={1,vivj∈E0,vivj∈/E.G顶点数是A的阶，G边数是A中1的个数的一半， deg v = ∑ i A v , i \deg v = \sum_i A_{v,i} degv=∑iAv,i.两种编号下的邻接矩阵存在一个置换矩阵P，使得 A 1 = P A 2 P T A_1 = PA_2 P^T A1=PA2PT.设G是(p,q)图，A是邻接矩阵，G中 u i , u j u_i,u_j ui,uj之间长度为l的通道的条数等于 A l A^l Al的第i行第j列的值。G是一个p顶点图,则 G 连 通 ⇔ ( A + I ) p − 1 ≥ 0 G连通\Leftrightarrow (A+I)^{p-1} \geq 0 G连通⇔(A+I)p−1≥0A的特征多项式 P ( λ ) = ∣ λ I − A ∣ = λ p + C 1 λ p − 1 + ⋯ + C p P(\lambda) = |\lambda I - A| = \lambda^p + C_1\lambda^{p-1} +\cdots + C_p P(λ)=∣λI−A∣=λp+C1λp−1+⋯+Cp.中 C 1 = 0 C_1=0 C1=0 − C 2 -C_2 −C2是G的边数 − C 3 -C_3 −C3是G中三角形个数的两倍 G=(V,E)是p个顶点的k-正则图(所有点的度都是k),A是邻接矩阵. k是A的一个特征值若G是连通的,则k的几何重数为1A的任何特征值 ∣ λ ∣ ≤ k |\lambda| \leq k ∣λ∣≤k 常用的存图方式为邻接表.它分顶点域和链域.这个东西课件上都是打星号内容
[主要内容]
G=(V,E)是一个图,f是V到S的一个映射,称 ( V , E , f ) (V,E,f) (V,E,f)是一个顶点带权图,仍记G为 G = ( V , E , f ) , ∀ v ∈ V , f ( v ) 是 v 的 权 G=(V,E,f),\forall v \in V,f(v)是v的权 G=(V,E,f),∀v∈V,f(v)是v的权.类似的g是E到S的映射,则 ( V , E , g ) (V,E,g) (V,E,g)是边带权图,其他定义同上.最短路问题,针对边带权图,g是从E到非负实数集R的映射.H是G的一个子图, g ( H ) g(H) g(H)记作H中所有边权之和.求解过程:Dijkstra算法.连通且无圈的无向图称为无向树，简称树。一个没有圈的无向图称为无向森林，简称森林。注意，图论中没有空图，因此也没有空树。
森林的每个支都是树，森林是若干树组成的图。
只有一个顶点的树称为平凡树，与图中的平凡图定义相同。
G=(V,E)是一个(p,q)图，以下各命题等价。
G是树G任一两个顶点之间有唯一的一条路联结G是连通的且p=q+1G中无圈且p=q+1G中无圈且G中任何两个不邻接顶点之间加一条边得到一个有唯一圈的图G是连通的，并且若 p ≥ 3 p\geq 3 p≥3，则G不是 K p K_p Kp.又若G的任两个不邻接的顶点之间加一条边,则得到一个恰好有唯一一个圈的图.任一非平凡树中至少又两个度为1的顶点.
若去掉G中任意一边之后得到的都是不连通的图,则连通图G称为是极小连通图.
图G是树当且仅当G是极小连通图.
设G=(V,E)是连通图， v ∈ V , e ( v ) = max u ∈ V { d ( v , u ) } v\in V,e(v) = \max_{u\in V}\{d(v,u)\} v∈V,e(v)=maxu∈V{d(v,u)}，称为v在G中的偏心率。数 r ( G ) = min v ∈ V { e ( v ) } r(G) = \min_{v\in V}\{e(v)\} r(G)=minv∈V{e(v)}称为G的半径。满足 e ( v ) = r ( G ) e(v)=r(G) e(v)=r(G)的点v称为G的中心点。G的所有中心点组成的集合称为G的中心，记作 C ( G ) C(G) C(G)。
每颗树的中心或含有一个顶点，或者含有两个邻接的顶点。
[证明]：G删去所有度为1的点得到 G ′ G' G′，新图的所有点的偏心率都减少了1，因此图的中心不变。依次删除直到产生 K 1 , K 2 K_1,K_2 K1,K2，此时便得到结论。
G是一个图，T是G的一个生成图（包含所有顶点），如果T是树，则称T是G的生成树。显然：有生成树必连通。
G有生成树的充要条件是G连通。证明方法：破圈法
G是一个(p,q)图，则 q ≥ p − 1 q \geq p-1 q≥p−1。
G是一个图，F是G的生成子图，若F是一个森林，则F称为G的一个生成森林。
显然：每个图必然会有生成森林。
K p K_p Kp有 p p − 2 p^{p-2} pp−2个生成树， p ≥ 2 p\geq 2 p≥2。此定理证明涉及到树的唯一表示
设V是一个有序集合，T是一个树， s 1 s_1 s1是T中第一个度为1的顶点，与 s 1 s_1 s1邻接的点记作 t 1 t_1 t1。现在从T中去除 s 1 s_1 s1，剩下的图继续做该操作得到 s 2 , t 2 s_2,t_2 s2,t2，持续该操作直到图上仅剩两个顶点。这是唯一确定了一个 p − 2 p-2 p−2元组 ( t 1 , t 2 , t 3 , … , t p − 2 ) (t_1,t_2,t_3,\dots,t_{p-2}) (t1,t2,t3,…,tp−2)，这就是一个树的唯一表示。
G=(V,E)是一个生成树, T 1 , T 2 T_1,T_2 T1,T2是两个不同的生成树,如果 e 1 ∈ E 1 ⇒ e 2 ∈ E 2 e_1\in E_1\Rightarrow e_2\in E_2 e1∈E1⇒e2∈E2,满足 ( T 1 − e 1 ) + e 2 (T_1 - e_1) + e_2 (T1−e1)+e2是G的一个生成树。
[证明]：去掉 e 1 e_1 e1后分成了两个部分,然后找一个 e 2 e_2 e2连接这两部分即可.
设 T 1 , T 2 T_1,T_2 T1,T2是G的生成树,是 T 1 T_1 T1的边,但不是 T 2 T_2 T2的边的条数k称为 T 1 与 T 2 T_1与T_2 T1与T2的距离,记作 d ( T 1 , T 2 ) = k d(T_1,T_2) = k d(T1,T2)=k。性质： d ( T 1 , T 1 ) = 0 , d ( T i , T j ) ≥ 0 , d ( T 1 , T 2 ) = d ( T 2 , T 1 ) d(T_1,T_1) = 0,d(T_i,T_j) \geq 0,d(T_1,T_2) = d(T_2,T_1) d(T1,T1)=0,d(Ti,Tj)≥0,d(T1,T2)=d(T2,T1). d ( T 1 , T 2 ) ≤ d ( T 1 , T 3 ) + d ( T 3 , T 2 ) d(T_1,T_2) \leq d(T_1,T_3) + d(T_3,T_2) d(T1,T2)≤d(T1,T3)+d(T3,T2).
若 d ( T 1 , T 2 ) > 0 d(T_1,T_2)>0 d(T1,T2)>0,则 T 1 T_1 T1中有一条边 e 1 e_1 e1不在 T 2 T_2 T2中,同理 T 2 T_2 T2中也有一个 e 2 e_2 e2.于是 T 2 = ( T 1 − e 1 ) + e 2 T_2 = (T_1 - e_1) + e_2 T2=(T1−e1)+e2 称为从 T 1 T_1 T1到 T 2 T_2 T2的一个基本(树)变换.
设 T 0 , T T_0,T T0,T是距离为k的G的两个生成树,则经过k次基本树变换就可以满足两生成树之间的转换.
这个问题需要研究边带权图,求解权最小的生成树.接下来的问题都是为解决这个最小生成树问题而展开的.
设T是连通图G的生成树,G的不是T的边称为T的弦.
如果e是T的一条弦,则 T + e T+e T+e有唯一的圈,这个圈被称为是基本圈.
前置: G = ( V , E , ω ) , ω ( x ) > 0 , ∀ x ∈ E G=(V,E,\omega),\omega(x) > 0,\forall x\in E G=(V,E,ω),ω(x)>0,∀x∈E是一个边带权图.T是一个最小生成树,e是T的一条弦.加入e后构成的圈的点集为U.则有 ω ( u ) ≤ ω ( e ) , ∀ u ∈ U \omega(u) \leq \omega(e),\forall u \in U ω(u)≤ω(e),∀u∈U.
G = ( V , E , ω ) , ω ( x ) > 0 , ∀ x ∈ E G=(V,E,\omega),\omega(x) > 0,\forall x\in E G=(V,E,ω),ω(x)>0,∀x∈E是一个边带权图. { ( V 1 , E 1 ) , … , ( V k , E k ) } \{(V_1,E_1),\dots,(V_k,E_k)\} {(V1,E1),…,(Vk,Ek)}是G的生成森林, k ≥ 1 , F = ∪ E i k\geq 1,F=\cup E_i k≥1,F=∪Ei.如果e是 E ∖ F E\setminus F E∖F中权值最小的边,且连接两个树.则存在一个包含 F ∪ { e } F\cup \{e\} F∪{e}的生成树T,使得T的权不大于包含F的生成树的权.[证明]:反证法.
输入 G = ( V , E , w ) G=(V,E,w) G=(V,E,w),输出 T = ( U , F ) T = (U,F) T=(U,F).
开始; U 空集; F 空集; 将E按照w的大小关系排列称为一个序列Q; 对于每个顶点v,将其加到U中; 当|U| > 1时,做: 开始; 从Q中选权值最小的边{u,v}; 从Q中删除这条边; 如果u和v分别在U的两个子集U1,U2中: 开始; 用U1并U2代替U1和U2; 把{u,v}加到F中; 结束; 结束; 结束;G = ( V , E , ω ) , ω ( x ) > 0 , ∀ x ∈ E G=(V,E,\omega),\omega(x) > 0,\forall x\in E G=(V,E,ω),ω(x)>0,∀x∈E是一个边带权图.U是V的一个真子集.取满足以下性质的一条边 { u , v } \{u,v\} {u,v}
u ∈ U , v ∉ U u\in U,v\notin U u∈U,v∈/U ∀ u , v 满 足 条 件 1 , w ( u , v ) 是 最 小 的 \forall u,v满足条件1,w(u,v)是最小的 ∀u,v满足条件1,w(u,v)是最小的则G中一定存在一个最小生成树,它包含上述的这条边.
设v是图G的一个顶点，若G-v的支数大于G的支数，则称v是G的一个割点。
设x是G的一条边，若G-x的支数大于G的支数，则称x是G的一个割边（桥）。
每个非平凡（不是(1,0)图）的连通图至少有两个顶点不是割点。证明用生成树的1度顶点来证明。
设 G = ( V , E ) G=(V,E) G=(V,E)是图， S ⊆ E S\subseteq E S⊆E.如果 G − S G-S G−S的支数大于G的支数,而去掉S的任一真子集的边得到的图不满足该性质,则S是G的一个割集.
设S是G的割集,则G-S恰好有两个支.
G是一个有k个支的图，S是G的割集，则G-S恰好有k+1个支。
不连通图G的每个割集一定是G某个支的割集。
设T是连通图G的任一生成树，G的任何一个割集都一定包含有T中的边。
连通图G的每个圈与G的任一割集有偶数条公共边。
设T是连通图G的一个生成树，e是T的一条弦，C是由T+e确定的一个基本圈。则e包含在“C上除e外的每条边确定的T的基本割集”中，但不包含在其他割集中。
[相对树的基本割集系统]T是G的一个生成树，x是T里面的边。T-x由两个支，于是V被分成两部分。由这两部分确定的割集称为由边x确定的基本割集。
T的每条边确定的割集称为G的相对T的基本割集。所有这些割集之集称为G的相对T的基本割集系统。
[基本割集定理]T是G的生成树，x是T的边，S为由x确定的相对T的一个基本割集，则x必在由S的每条弦确定的基本圈上，而不再任一基本圈上。
设G=(V,E)是一个无向图。V的子集S，如果G-S是不连通的，则S称为分离图G。图G的顶点连通度 κ ( G ) \kappa(G) κ(G)是为了产生一个不连通图或平凡图（平凡图针对的目标是完全图，完全图只能删除到 K 1 K_1 K1才行）所需要从G中去掉的最少顶点数目。
顶点连通度又被称为图的连通度。
图G的边连通度 λ ( G ) \lambda(G) λ(G)是为了从G产生不连通或平凡图所需从G中去掉的最小边数。
κ ( G ) ≤ λ ( G ) ≤ δ ( G ) , 顶 点 连 通 度 ≤ 边 连 通 度 ≤ 最 小 度 \kappa(G) \leq \lambda(G) \leq \delta(G),顶点连通度\leq 边连通度\leq 最小度 κ(G)≤λ(G)≤δ(G),顶点连通度≤边连通度≤最小度
对于任何整数 0 < a ≤ b ≤ c 0<a\leq b\leq c 0<a≤b≤c存在一个图G使得 κ ( G ) = a , λ ( G ) = b , δ ( G ) = c \kappa(G) = a,\lambda(G)=b,\delta(G)=c κ(G)=a,λ(G)=b,δ(G)=c [构造方法]：
a = b = c a=b=c a=b=c,构造 G = K a + 1 G=K_{a+1} G=Ka+1. a = b < c a = b < c a=b<c,构造:两个 K c + 1 K_{c+1} Kc+1,中间用a条互不相交的边连接. a < b = c a < b = c a<b=c,构造:两个 K b − a + 1 , 叫 G 1 , G 2 K_{b-a+1},叫G_1,G_2 Kb−a+1,叫G1,G2,一个 K a K_a Ka,对 K a K_a Ka的每个点与 G 1 , G 2 G_1,G_2 G1,G2每个点都连一条边. a < b < c a<b<c a<b<c,构造:两个 K c + 1 , 分 别 叫 G 1 , G 2 K_{c+1},分别叫G_1,G_2 Kc+1,分别叫G1,G2,从 G 1 G_1 G1选a个点,第一个点向 G 2 G_2 G2连 b − a + 1 b-a+1 b−a+1条另一端点不同的边;剩下的 a − 1 a-1 a−1个点向 G 2 G_2 G2连接 a − 1 a-1 a−1条互不相交的边.设 G = ( V , E ) G=(V,E) G=(V,E),且 λ ( G ) > 0 \lambda(G) > 0 λ(G)>0.则存在V的二划分 A , V ∖ A A,V\setminus A A,V∖A,使得G中联结A与 V ∖ A V\setminus A V∖A中一个顶点的边的总数为 λ ( G ) \lambda(G) λ(G).
G=(V,E)，有p个顶点且 δ ( G ) ≥ ⌊ p 2 ⌋ ( [ p 2 ] ) \delta(G) \geq \lfloor {p\over 2}\rfloor([{p\over 2}]) δ(G)≥⌊2p⌋([2p])，则 λ ( G ) = δ ( G ) \lambda(G) = \delta(G) λ(G)=δ(G)。
G=(p,q)=(V,E)。则：
if q < p − 1 , κ ( G ) = 0 {\text{if}}\ q < p-1,\kappa(G) = 0 if q<p−1,κ(G)=0 if q ≥ p − 1 , κ ( G ) ≤ ⌊ 2 q p ⌋ \text{if}\ q \geq p-1,\kappa(G)\leq \lfloor {2q\over p}\rfloor if q≥p−1,κ(G)≤⌊p2q⌋G是一个图，如果 κ ( G ) ≥ n \kappa(G)\geq n κ(G)≥n，则称G是n-顶点连通的，简称n-连通；如果 λ ( G ) ≥ n \lambda(G) \geq n λ(G)≥n，则称G是n-边连通的。
注意：这个n可以小于你的顶点连通度、边连通度。
G是一个p顶点的图，且 p ≥ 3 p\geq 3 p≥3。则G是2-连通的，当且仅当G的任两个不同顶点都在G的同一个圈上。
设G是一个图，则其n-边连通的充要条件是：不存在V的真子集A，使得G中联结A和 V ∖ A V\setminus A V∖A的边的总数小于n。
[选择性断更这一节]
这个东西课件上都是打星号内容
[主要内容]
两条不邻接的边称为是相互独立的。
E的子集Y，如果Y中边两两独立，则Y是G的一个匹配。
Y是最大匹配等价于任一匹配 Y ′ , ∣ Y ′ ∣ ≤ ∣ Y ∣ Y',|Y'| \leq |Y| Y′,∣Y′∣≤∣Y∣。
偶图的完全匹配是指一个 Y ⊆ E Y\subseteq E Y⊆E，且 ∀ x ∈ Y \forall x\in Y ∀x∈Y,都是联结偶图两个子集的边.并且 ∣ Y ∣ = min { ∣ V 1 ∣ , ∣ V 2 ∣ } |Y| = \min\{|V_1|,|V_2|\} ∣Y∣=min{∣V1∣,∣V2∣}.称Y是偶图G的完全匹配.
m个姑娘,n个小伙子.m个姑娘都能嫁给自己认识的小伙子,这个问题有解的充要条件是对于任意 k ∈ [ 1 , m ] k\in [1,m] k∈[1,m]任意k个姑娘认识的小伙子总数不小于k.
霍尔原理.设X是一个有限集,系统 T : A 1 , A 2 , A 3 , … , A n T:A_1,A_2,A_3,\dots,A_n T:A1,A2,A3,…,An是X的一些子集构成的,则T有相异代表系的充要条件是对于 ∀ I ⊆ { 1 , 2 , 3 , 4 , … , n } \forall I \subseteq \{1,2,3,4,\dots,n\} ∀I⊆{1,2,3,4,…,n}都有 ∣ ∪ i ∈ I A i ∣ ≥ ∣ I ∣ , ( H a l l 条 件 ) |\cup_{i\in I}A_i| \geq |I|,(Hall条件) ∣∪i∈IAi∣≥∣I∣,(Hall条件).这个可以看作是上面问题的形式化拓展.
G是一个偶图, ∣ V 1 ∣ ≤ ∣ V 2 ∣ |V_1|\leq |V_2| ∣V1∣≤∣V2∣,令 ϕ : V 1 → 2 V 2 \phi:V_1 \rightarrow 2^{V_2} ϕ:V1→2V2,且对应关系如下 v i ∈ V 1 , u i ∈ V 2 v_i\in V_1,u_i \in V_2 vi∈V1,ui∈V2: ϕ ( v i ) = { u j ∣ u j ∈ V 2 且 v i u j ∈ E } \phi(v_i) = \{u_j|u_j\in V_2且v_iu_j\in E\} ϕ(vi)={uj∣uj∈V2且viuj∈E}
G = ( V 1 ∪ V 2 , E ) G = (V_1\cup V_2,E) G=(V1∪V2,E)为偶图, ∣ V 1 ∣ ≤ ∣ V 2 ∣ |V_1| \leq |V_2| ∣V1∣≤∣V2∣,则G有完全匹配的充要条件是对于 V 1 V_1 V1的任一子集S, ∣ ϕ ( S ) ∣ ≥ ∣ S ∣ |\phi(S)| \geq |S| ∣ϕ(S)∣≥∣S∣,其中 ϕ ( S ) = { u ∣ u ∈ V 2 , 且 ∃ v ∈ S , 使 得 v u ∈ E } \phi(S)=\{u|u\in V_2,且\exists v \in S,使得vu\in E\} ϕ(S)={u∣u∈V2,且∃v∈S,使得vu∈E}.
Y是G的一个匹配,如果 2 ∣ Y ∣ = ∣ V ∣ 2|Y| = |V| 2∣Y∣=∣V∣,则称Y是G的一个完美匹配.
r-正则偶图G一定有一个完美匹配,其中 r ≥ 1 r\geq 1 r≥1.
设 T : A 1 , A 2 , … , A n T:A_1,A_2,\dots,A_n T:A1,A2,…,An为有限集X的子集构成的系统,系统T的集系统S是T的子序列构成的系统.如果S有相异代表系,则称子系统S的相异代表系为系统T的部分相异代表系.
设 T : A 1 , A 2 , … , A n T:A_1,A_2,\dots,A_n T:A1,A2,…,An为有限集X的子集构成的系统,则T有一个有t个不同元素组成的T的部分相异代表系的充要条件是 ∀ A ⊆ { 1 , 2 , … , n } \forall A \subseteq \{1,2,\dots,n\} ∀A⊆{1,2,…,n}使得 ∣ ∪ i ∈ A A i ∣ ≥ ∣ A ∣ − ( n − t ) |\cup_{i\in A}A_i| \geq |A| - (n-t) ∣∪i∈AAi∣≥∣A∣−(n−t).
设 T : A 1 , A 2 , … , A n T:A_1,A_2,\dots,A_n T:A1,A2,…,An为有限集X的子集构成的系统,则T的部分相异代表系所含元素的最大值t等于 min B ⊆ { 1 , 2 , … , n } { ∣ ∪ i ∈ B A i ∣ + ( n − ∣ A ∣ ) } \min_{B\subseteq \{1,2,\dots,n\}}\{|\cup_{i\in B}A_i| + (n-|A|)\} B⊆{1,2,…,n}min{∣∪i∈BAi∣+(n−∣A∣)}
G是一个偶图且 ∣ V 1 ∣ ≤ ∣ V 2 ∣ |V_1|\leq |V_2| ∣V1∣≤∣V2∣,G的最大匹配中边数记作M(G).则 M ( G ) = min A ⊆ V 1 { ∣ ∪ v ∈ A ϕ ( A ) ∣ + ( ∣ V 1 ∣ − ∣ A ∣ ) } = min A ⊆ V 1 { ∣ A ∣ + ∣ ϕ ( V 1 ∖ A ) ∣ } \begin{aligned} M(G) = &\min_{A\subseteq V_1}\{|\cup_{v\in A}\phi(A)|+(|V_1| - |A|)\}\\ = & \min_{A\subseteq V_1}\{|A| + |\phi(V_1\setminus A)|\} \end{aligned} M(G)==A⊆V1min{∣∪v∈Aϕ(A)∣+(∣V1∣−∣A∣)}A⊆V1min{∣A∣+∣ϕ(V1∖A)∣}
由门格尔定理能推出霍尔定理
平面图：其图解可以画在一个平面上，而且存在一种画法使得仅可能在顶点相交，边内部都不相交，就称为平面图。
G称为被嵌入平（曲）面S内，如果G的图解已经画在S上，而且任何两条边除端点外都不相交。已嵌入平面内的图称为平面图。如果一个图可以嵌入平面，则称此图是可平面的。
平面图G把平面分成了若干个区域，这些区域都是单连通的（可以收缩到一个点），称之为G的面。其中无界的连通区域称为G的外部面，其余单连通区域称为G的内部面。
一个平面图可以没有内部面，但不能没有外部面。
如果有p个顶点q条边的平面连通图G，有f个面，则 p − q + f = 2 p-q+f=2 p−q+f=2 证明：使用归纳法，对面的个数进行归纳。
去掉一个边x，打通了两个面，此时G-x=(p,q-1)p - (q-1) + (f-1) = 2由归纳假设可知正确p - q + f = 2因此得到这个也是正确的如果有p个顶点q条边的平面图G，有f个面，k个支，则 p − q + f = k + 1 p-q+f=k + 1 p−q+f=k+1 证明：对每个支列式子，然后加起来。
如果平面连通图G由p个顶点q条边，而且每个面都是由长度为n的圈围成的，则 p − q + f = 2 2 q = n f ⇒ f = 2 q n ⇒ q = n ( p − 2 ) / ( n − 2 ) p - q + f = 2\\ 2q = nf \Rightarrow f = {2q\over n} \Rightarrow \\ q = n(p-2)/(n-2) p−q+f=22q=nf⇒f=n2q⇒q=n(p−2)/(n−2)
最大可平面图是一个可平面图。对此可平面图中不能再加入边而不破坏图的可平面性。
简称：加了新边就一定不是可平面图。
G=(p,q)是最大可平面图，则G的每个面都是三角形，且 q = 3 p − 6 q=3p-6 q=3p−6.
G是一个可平面连通图，G的每个面都是一个长为4的圈围成的，G=(p,q)，则 q = 2 p − 4 q=2p-4 q=2p−4
若G是任一有p顶点q个边的可平面图 p ≥ 3 p \geq 3 p≥3，则 q ≤ 3 p − 6 q \leq 3p - 6 q≤3p−6；若G是2-（顶点）连通图且G中没有三角形，则 q ≤ 2 p − 4 q \leq 2p - 4 q≤2p−4.
K 5 , K 3 , 3 K_5,K_{3,3} K5,K3,3都不是可平面图
每个平面图G的顶点度的最小值不超过5,即 δ ( G ) ≤ 5 \delta(G) \leq 5 δ(G)≤5.
前言:1968年,Grinberg发现平面图是哈密顿图的一个必要条件.
G = ( V , E ) = ( p , q ) G=(V,E)=(p,q) G=(V,E)=(p,q)是一个平面哈密顿图(字面意思,平面图+哈密顿图),C是G的哈密顿圈.令 f i f_i fi为C内部由i条边围成的面的个数, g i g_i gi是C的外部由i条边围成的面的个数.
1 f 3 + 2 f 4 + ⋯ = ∑ i = 1 p ( i − 2 ) f p = p − 2 1f_3 + 2f_4 + \dots = \sum_{i=1}^{p} (i-2)f_p = p-2 1f3+2f4+⋯=∑i=1p(i−2)fp=p−2 1 g 3 + 2 g 4 + ⋯ = ∑ i = 1 p ( i − 2 ) g p = p − 2 1g_3 + 2g_4 + \dots = \sum_{i=1}^{p} (i-2)g_p = p-2 1g3+2g4+⋯=∑i=1p(i−2)gp=p−2 1 ( f 3 − g 3 ) + 2 ( f 4 − g 4 ) + ⋯ = ∑ i = 1 p ( i − 2 ) ( f p − g p ) = 0 1(f_3-g_3) + 2(f_4-g_4) + \dots = \sum_{i=1}^{p} (i-2)(f_p-g_p) = 0 1(f3−g3)+2(f4−g4)+⋯=∑i=1p(i−2)(fp−gp)=0如果不满足这个条件就不是平面哈密顿图,也就是非哈密顿平面图.
x = u v x=uv x=uv是 G = ( V , E ) G=(V,E) G=(V,E)的一条边，又w不是G的顶点，则当用 u w , w v uw,wv uw,wv代替边x的时候，就称x被细分。如果G的某些边被细分，产生的图称为G的细分图。
两个图称为同胚的，如果它们都可以从一个图通过一系列边细分得到。
一个图是可平面的充要条件是它没有同胚于 K 5 , K 3 , 3 K_5,K_{3,3} K5,K3,3的子图。[这个充分性证明比较复杂,课本也无]
一个图G的一个初等收缩由等同两个邻接的顶点uv得到，即从G中去掉uv，然后再加上一个顶点w，使得w邻接于所有邻接于u或v的顶点。一个图G可收缩到图H，如果H可以从G经一系列的初等收缩得到。
说人话：用一个新的点w代替两个邻接的顶点uv
一个图是可平面的当且仅当它没有一个可以收缩到 K 5 , K 3 , 3 K_5,K_{3,3} K5,K3,3的子图。
G=(V,E)是一个平面图，由G按照以下方法构造一个图 G ∗ G^* G∗，称为G的对偶图。
G的每个面f对应地由 G ∗ G^* G∗地一个顶点 f ∗ f^* f∗。对G地每条边e对应地有 G ∗ G^* G∗的一条边 e ∗ e^* e∗. G ∗ G^* G∗的两个顶点 f ∗ , g ∗ f^*,g^* f∗,g∗由边 e ∗ e^* e∗联结,等价于G中的f和g以公共边e连接.如果某条边x仅在G的一个面中出现而不是两个面的公共边,则这个面在 G ∗ G^* G∗中增加一个自环.图的一种(顶点)着色是指对图的每个顶点指定一种颜色,使得没有两个邻接的顶点有同一种颜色.G的一个n-着色是用n种颜色对G着色.
G=(V,E)已着色,则着同一个颜色的那些顶点之集称为G的一个色组.同一色组内各顶点互不邻接.这样的顶点集合称为G的一个顶点独立集.如果G有一个n-着色,则G的顶点集V被这个着色划分称n个色组.
图G的色数是使G为n-着色的数n的最小值.G的色数记作 χ ( G ) \chi(G) χ(G).如果 χ ( G ) ≤ n \chi(G) \leq n χ(G)≤n则称G是n-可着色的.若 χ ( G ) = n \chi(G) = n χ(G)=n,则称G是n色的.
一个图是可双色的当且仅当它没有奇数长度的圈.
G一定是 Δ ( G ) + 1 \Delta(G)+1 Δ(G)+1-可着色的.其中 Δ ( G ) \Delta(G) Δ(G)是顶点度最大值.
G 1.是连通图 2.且不是完全图 3.也没有奇数长度的圈 则G是 Δ ( G ) \Delta(G) Δ(G)-可着色的.
每一个平面图G都是6-可着色的.证明:归纳于顶点数.
每一个平面图都是5-可着色的.证明:归纳于顶点数.
每个平面图都是4-可着色的.这个由计算机证明过.
[断更]
