宝安网站建设-信科网络,网页模板源码,湖北自适应网站建设价格,网站多语言解决方案图论各章考点 一、图与网络的基本概念二、树三、连通性四、路径算法五、匹配六、行遍性问题七、平面图 一、图与网络的基本概念
生成子图#xff1a;生成子图 G ’ G’ G’中顶点个数V’必须和原图G中V的数量相同#xff0c;而 E ’ ∈ E E’∈E E’∈E即可。顶点集导出子图… 图论各章考点 一、图与网络的基本概念二、树三、连通性四、路径算法五、匹配六、行遍性问题七、平面图 一、图与网络的基本概念
生成子图生成子图 G ’ G’ G’中顶点个数V’必须和原图G中V的数量相同而 E ’ ∈ E E’∈E E’∈E即可。顶点集导出子图 V 1 ⊆ V V1⊆V V1⊆V以 V 1 V1 V1为顶点集两个端点都在 V V V中的边为边集的 G G G的子图。边集导出子图 E 1 ⊆ E E1⊆E E1⊆E以 E 1 E1 E1为边集 E 1 E1 E1的端点集为顶点集的图 G G G的子图。简单图既无环又无重边的图为简单图完备图任二顶点相邻的简单图,称为完备图,记为 K n K_n Kn其中n 为顶点的数目二部图一个图是偶图二部图当且当它不包含奇圈握手定理图 G ( V , E ) G (V, E) G(V,E)中所有顶点的度的和等于边数m的2倍同构顶点集之间存在一一对应关系边也有一一对应的关系,则称图 G G G与 H H H同构有向图的同构对应边的方向要相同。必要条件 (1) 顶点数相同(2) 边数相同(3) 关联边数相同的顶点个数相同。
二、树
树无圈连通图称为树树充要条件 G G G无环且任何两个顶点之间有唯一的路径树充要条件 G G G连通,且 e ( G ) V ( G ) − 1 e(G)V(G)-1 e(G)V(G)−1树充要条件 G G G连通且对 G G G的任一边 e , G − e e,G-e e,G−e不连通生成树 G G G的边数最少的连通生成子图
三、连通性
点连通度设 G G G连通, V ⊂ V ( G ) , G [ V − V ] V⊂V(G), G[V-V] V⊂V(G),G[V−V]不连通,则称 V V V为 G G G的点断集。最小点断集中顶点的个数称为 G G G的连通度记为 K ( G ) K(G) K(G)若 G G G无点断集,则规定 K ( G ) n − 1 K(G)n-1 K(G)n−1 平凡图、不连通图 0 平凡图、不连通图0 平凡图、不连通图0边连通度设 G G G连通, E ⊂ E ( G ) E⊂E(G) E⊂E(G), G − E G-E G−E(从 G G G中删除 E E E中的边)不连通,则称 E E E是 G G G的边断集。最小边断集所含的边数称为 G G G的边连通度记为 K ‘ ( G ) K‘(G) K‘(G)当 ∣ E ′ ∣ 1 |E|1 ∣E′∣1时,称E中的边 e e e为割边 平凡图、不连通图 0 平凡图、不连通图0 平凡图、不连通图0k连通图若一个图的连通度至少为 k k k则称该图是 k k k连通的。于是非平凡连通图均是 1 1 1连通的图 G G G是2连通的当且仅当 G G G连通、无割点且至少含有 3 3 3个点。点连通度、边连通度、最小度 K ( G ) K ′ ( G ) δ G K(G)K(G)δG K(G)K′(G)δG割边设e是图G的一条边若 ω ( G − e ) ω ( G ) ω(G-e)ω(G) ω(G−e)ω(G), 则称 e e e为 G G G的割边。 e e e是图 G G G的割边当且仅当 e e e不在 G G G的任何圈中。割点 v v v是 G G G的割点当且仅当 V ( G − v ) V(G-v) V(G−v)可划分为两个非空顶点子集 V 1 V_1 V1与 V 2 V_2 V2使 x ∈ V 1 y ∈ V 2 x∈V_1y∈V_2 x∈V1y∈V2点v都在每一条 ( x , y ) (x, y) (x,y) 路上。割集 [ S , S ′ ] [S, S] [S,S′]表示一个端点在 S S S,另一个端点在 S S S的全体边组成的集合设 G G G连通,若 [ S , S ’ ] [S,S’] [S,S’]只把 G G G断成两个分支,则称 [ S , S ′ ] [S, S] [S,S′]为 G G G的一个割集。树和图设 v v v是树的顶点则 v v v是 G G G的割点当且仅当度 d ( v ) 2 d(v)2 d(v)2
习题15去掉 e ( u , v ) e (u, v) e(u,v) 在 G − e G-e G−e中 u u u所在的分支仅有一个奇度顶点与握手定理矛盾
习题16反证法 e ( u , v ) e (u, v) e(u,v) G − e G-e G−e中 u u u所在的分支 G 1 G_1 G1 G 1 G_1 G1为二部图因为二部图所有子图均为二部图则 Σ G 1 k ∣ X 1 ∣ k ∣ Y 1 ∣ − 1 k ΣG_1k|X_1|k|Y_1|-1k ΣG1k∣X1∣k∣Y1∣−1k ∣ X 1 ∣ − ∣ Y 1 ∣ 1 k 2 |X_1|-|Y_1|1k2 ∣X1∣−∣Y1∣1k2不成立
四、路径算法
Floyd复杂度 O n 3 On^3 On3
五、匹配
边独立集匹配如果 M M M是图 G G G的边子集(不含环且 M M M中的任意两条边没有共同顶点则称 M M M是 G G G的一个匹配最大匹配如果 M M M是图 G G G的包含边数最多的匹配称 M M M是 G G G的一个最大匹配。特别是若最大匹配饱和了 G G G的所有顶点称它为 G G G的一个完美匹配理想匹配二部图理想匹配若 G G G是 k ( k 0 ) k (k0) k(k0)正则偶图则 G G G存在完美匹配贝尔热定理 G G G的匹配 M M M是最大匹配当且仅当 G G G不包含M可扩路Hall定理二分图存在完美匹配当且仅当 ∀ S ⊆ A \forall S\subseteq A ∀S⊆A都有 ∣ N ( S ) ∣ ⩾ ∣ S ∣ |N(S)|\geqslant |S| ∣N(S)∣⩾∣S∣哥尼定理在偶图中最大匹配的边数等于最小覆盖的顶点数托特定理图 G G G有完美匹配当且仅当对V的任意非空真子集S, 有 奇分支数目 ) ∣ o ( G − S ) ∣ ⩽ ∣ S ∣ 奇分支数目)|o(G-S)|\leqslant |S| 奇分支数目)∣o(G−S)∣⩽∣S∣
六、行遍性问题
欧拉巡回经过 G G G的每边正好一次的巡回称为欧拉巡回欧拉图存在欧拉巡回的图称为欧拉图或E图欧拉图的充要条件连通、无奇度顶点欧拉道路的充要条件连通、最多只有两个奇度顶点哈米尔顿路径经过图 G G G每个顶点正好一次的路径简称 H H H路径。哈米尔顿图经过 G G G的每个顶点正好一次的圈为H圈。含H圈的图称为哈米尔顿图或 H H H图。H图的必要条件 其 ∀ S ⊂ V S ≠ ∅ ω ( G − S ) ≤ ∣ S ∣ 其 \forall S \subset V S \neq \varnothing \\ \omega ( G - S ) \leq | S | 其∀S⊂VS∅ω(G−S)≤∣S∣
七、平面图
平面图一个图若能在曲面 S S S上画出,使任两边在非顶点处不相交,则称此图可以在曲面 S S S上嵌人。可嵌入平面的图称为可嵌平面图,否则称为非平面图。可嵌平面图 G G G嵌人平面形成的图,称为 G G G的平面嵌入。欧拉公式设 G ( n , m ) G(n, m) G(n,m)是连通平面图 ϕ \phi ϕ是G的面数 n − m ϕ 2 n - m \phi 2 n−mϕ2平面图推论 G G G是 v 3 v3 v3的简单平面图 ε ≤ 3 v − 6 \varepsilon \leq 3 v - 6 ε≤3v−6 δ ( G ) ≤ 5 \delta ( G ) \leq 5 δ(G)≤5库拉托夫斯基定理图 G G G是非可平面的当且仅当它含有 K 5 K_5 K5或 K 3 , 3 K_{3,3} K3,3细分的子图
