网站外包制作,网站建设属于软件开发吗,网上哪里有辅导高考生做难题的网站,网站建设个人网银欧拉图与哈密尔顿图
Euler图
定义 经过G的每条边的迹被称为欧拉迹 迹的边#xff0c;每个边只出现一次#xff0c;但是点不一定#xff0c;可以多次 能够闭合的迹被称为闭迹 存在欧拉闭迹的图称为欧拉图欧拉闭迹又称为欧拉回路
欧拉图等价性质 图G的每个点的度都是偶数 …
欧拉图与哈密尔顿图
Euler图
定义 经过G的每条边的迹被称为欧拉迹 迹的边每个边只出现一次但是点不一定可以多次 能够闭合的迹被称为闭迹 存在欧拉闭迹的图称为欧拉图欧拉闭迹又称为欧拉回路
欧拉图等价性质 图G的每个点的度都是偶数 证明令C为G中的一条欧拉回路G中任一个给定的点在C中每出现一次恰好关联两条边因为G的每条边在C仅出现一次所以该点的度为该店在C中出现的次数的两倍是偶数 推论连通图G有欧拉迹当且仅当G最多有两个奇点 证明显然G有欧拉闭迹时当且仅有0个奇点。而若G有欧拉非闭迹并设点u和v分别是C的奇点和终点记在C中添加一条连接u和v的边e后所得到的图为Ce显然Ce是一条欧拉闭迹则由已知结论可知Ce有0个奇点所以C有两个奇点。反之设G是恰有两个奇点u和v的连通图在u和v之间添加新边e得图Ge则Ge没有奇点由已知结论Ge有欧拉闭迹所以G有欧拉迹综上结论成立 图G的边集能划分为边不重的圈的并 由上一个性质来证明该性质当G的边数为1时G只能是自环结论显然成立。假设G的边数大于1从任意一点出发寻找一条通路直到某一个顶点再次遇到假设为v则v到v的通路构成一个圈。从G中移除得到的圈则得到的每个连通分支是一个满足条件边数较少的圈。可以想象一个大圈被拧巴成那种麻花成了几个小圈
一笔画
多少笔画完取决于有多少对奇点 若G有2k个奇度顶点则存在k条边不重的迹Q1,Q2...Qk使得E(G)E(Q1)∪E(Q2)∪...∪E(Qk) 证明只就连通图进行证明对2k个奇点两两配对且不相邻添加k条新的边从而G‘变成了欧拉图G’存在欧拉回路C在C中删除刚才新加的边得k个边不重的迹Qi从而得证
一些性质(例题) 若G是非平凡的欧拉图则G的每个块也是欧拉图 证明设B是G的任意一个块C是G的一个欧拉回路从B的某一点v出发沿着C前进由块的定义知欧拉回路C只有经过G的割点才能离开B也只有经过同一割点才能回到B中我们将C中不属于B的那些边去掉得到一个回路该回路经过了B的每条边因此该回路是B的欧拉回路所以B是欧拉图。 若G和H是欧拉图则GxH是欧拉图 首先GxH是积图的意思(x,y)新图中相连必须一个坐标相等另外一个相连证明要从度数偶数连通图来入手 度数偶数对于任意u∈V(G)v∈V(H)必有 如此便能得到积图度数为偶数 其次GxH必为连通图对任意顶点(u1,v1)∈V(GxH)(u2,v2)∈V(GxH)它们之间必存在一条通路由于G是欧拉图则G必为连通图因此在G中存在一条连接u1和u2的路(u1,x1,x2,...xp,u2)同理在H中存在一条连接v1和v2的路(v1,y1,y2,...,yq,v2)所以GxH中存在一条连接(u1,v1)和(u2,v2)的路(u1,v1)(x1,v1)...(xp,v1)(u2,v1)(u2,y1)(u2,y2)...(u2,yq)(u2,v2) 综上GxH是每个顶点度数为偶数的连通图所以GxH是欧拉图 G是非平凡的欧拉图且v∈V(G)G的每条以v为起点的迹都能扩展成G的欧拉回路当且仅当G-v为森林 扩展的意思是从迹的终点继续走下去延伸森林就是无圈图 必要性若不然G-v包含圈C考虑G1G-E(C)的包含顶点v的连通分支H由于G是欧拉图则G的每个顶点度数为偶数圈C的每个顶点度数为偶数所以G1的每个顶点的度数都是偶数从而H是顶点度数都是偶数的连通图H是欧拉图。设T为H的欧拉回路则T可以看做是图G的以v为起点与终点的一条迹。这里可以证明T与C不相交且图G与v关联的边都在T中。假设T与C相交即有公共边则在G-E(C)时就会将其删掉则不可能再H中构成回路所以T与C不相交同时圈C是由G-v得到所以与v相关联的边一定不在圈C上然后与v关联的边一定出现在v所在的连通分支上不出现在其他连通分支上这显然所以一定在T中。此时与v关联的边都在T中无法继续走下去所以无法扩展所以矛盾所以G-v一定不包含圈所以G-v是森林 一句话反证点v除了在圈中不和剩余部分相连所以矛盾 充分性若不然则设Q(v,w)是G的一条不能扩展为G的欧拉回路的最长的迹。首先vw即Q是一条闭迹否则v和w是G-Q仅有的两个奇度点从而G-Q中存在以w为奇点v为终点的迹P因此迹Q可以通过P继续扩展所以Q必须是闭迹。其次Q包含与v关联的所有边否则Q还可以延长。所以G-v包含包含G-Q的所有边且G-Q的每个顶点的度数都是偶数。所以G-Q的非平凡连通分支是欧拉图所以存在圈所以G-v中也存在圈这和充要条件G-v是森林矛盾故充分性证闭。 一句话反证最长的迹时闭迹推导出G-v也是度数为偶数的图存在圈
Fleury算法
描画一条边不重复的迹割边在没有其他选择时才会被描画 目的找欧拉图的欧拉回路 对于半欧拉图的欧拉迹也可以因为它和欧拉图也就差了一条边填上这条边就可以用fleury算法寻找欧拉回路删掉添的边就成了欧拉迹 算法过程 每次在当前轨迹的终点选择边从当前可选边的非割边中任意选一条边然后继续走下去若只有割边那就只能选割边往下走了
中国邮递员问题
问题描述
从某点出发每条边至少走一遍回到该点总路程最小不一定是欧拉回路因为有的路是重复走的欧拉回路中每条路都是只走一次的 该问题的图论模型在一个连通的具有非负权的赋权图G中找一条包含每条边(允许重复)且边权之和最小的闭途径称之为最优环游 若图G是欧拉图则直接找出G的欧拉回路即可若图G是一般图其解法为添加重复边使G成为欧拉图G‘并使添加的重复边的边权之和最小再求G’的欧拉回路
定理假定G‘是在图G中添加一些重复边得到的欧拉图则G’具有最小权值的充要条件是1G的每一条边最多被添加一次2对于G‘的每个圈来说新添加的边的总权值不超过该圈总权值的一半
必要性若G中某条边在G’中被添加的次数超过1则去掉其中两条重复边将得到一个总权值更小且以G为子图的欧拉图。所以每条边最多被添加一次。假定G‘中存在某个圈使得新添加的边的总权值大于该圈权值的一半设该圈为C那么在G’中将C上新添加的边全部去掉然后将原来的每条边都添加一次这样就能够得到总权值更小的以G为子图的欧拉图所以2需要满足充分性要证明满足两个条件的任意两个图都有相同的总权值。设Y1与Y2分别表示G1与G2中添加的边的集合令Y是Y1和Y2的非公共部分。G[Y]的每个顶点的度数必为偶数(可证明这里不证明)由此G[Y]的每个分支都是欧拉图可以做圈分解对于每个圈其添加的权值都相等(可证明这里不证明)。由此可证得G1和G2有相同的权值。这里两个可证明而不证明的地方因为证明内容太长所以就暂时不写了考到的可能性比较低
非欧拉图求最优环游方法
用每条边最多添加一次的方式去任意添加一些重复边是图G称为一个欧拉多重图G‘考察G’的圈若存在圈C其中重复边的总权值大于该圈权值的一半则再圈C上交换重复边和不重复边得到一个新的欧拉多重图。重复这个过程直到满足不大于一半用Fleury算法来求G‘的欧拉回路
最优环游例题解决 如果一个赋权图G中只有两个奇度顶点u和v设计一个求其最优欧拉环游的算法 在u和v之间求出一条最短路P在最短路P上给每条边添加一条平行边得到G的欧拉多重图G’在欧拉多重图G‘中用Fleury算法求出一条欧拉回路
E图与H图
线图L(G)
V(L(G))E(G)(e1,e2)∈E(L(G))当且仅当e1与e2相邻 n次迭线图 线图的线图n-1次迭代
线图的性质
线图L(G)的顶点数等于G的边数若euv是G的边则e作为L(G)的顶点度数为 若G有n个点m条边则线图L(G)的边数为 证明对于G中任一顶点v关联于该顶点的d(v)条边在L(G)中产生的边数为d(v)(d(v)-1)/2两两相邻的顶点求和便是该结果 一个图同构与它的线图当且仅当它是圈 若图G1和G2有同构的线图则除了一个是K3另一个是K1,3外G1和G2同构
n次细分图
- 只将G的每条边都插入n个2度顶点迭代n次符号Sn
定理1若G是E图则L(G)既是E图又是H图2若G是H图则L(G)是H图
1因为G是E图所以每个点的度数是偶数然后线图的每个点度数都是偶数连通所以线图是E图。沿着欧拉图的欧拉回路走一圈就是线图的H图2不会不管了···
一个图G是E图的充要条件是L3(G)为H图
若G是具有n个点m条边的非平凡连通图且不是一条路则k≥n-3时图Lk(G)是H图
TSP问题
问题描述完全图恰好遍历每个点返回且最终总路程最短
图论模型在赋权完全图G中求具有最小权的哈密尔顿圈即最优圈
边交换技术
权重小的边去替换权重大的边选出的边是要交叉的得到的结果是近似最优解可以通过几个不同的初始圈开始通过边交换技术得到几个近似的最优解然后选其中最好的
最优圈的下界
方法在G中任意删掉一点得图G1在图G1中求出一棵最小生成树T在v的关连边中选出两条权值最小者e1和e2若C是G的最优圈则W(C)≥W(T)W(e1)W(e2)关于那个例题三角不等式的还是比较好理解的通过最小生成树的欧拉图来构建H圈那个ppt上说的是从第三个点开始删点这个很不好理解视频上说是沿着T1的欧拉圈来构建H图是通过每遍历一个新的点就加进路径这样例如v1,v2,v3,v4,v5,v6,v1就是H圈结合三角不等式一定比最小生成树的欧拉圈权值要小即最小生成树权值的两倍
度极大的非哈密尔顿图
概念 度极大非H图 非H图度不弱于其他非H图度弱是度序列排序后比较第i个大小 Cm,n图 - - 可以展开有必要说1≤mn/2 理解其生成规则左边m个孤立点中间一个Km完全图右边一个Kn-2m的完全图中间分别和左右做联运算即每个点都与左右两边的点连接 - Cmn的度序列是什么样的呢 (m,...m,(m个),n-m-1...n-m-1(n-2m个),n-1...n-1(m个))挺好理解的 Cmn图不是H图 如果删去中间m个顶点删去它们会得到m1个连通分支这不符合H图的性质3所以其不是H图 Cmn图对于任意两个不相邻的顶点添加一条边则会成为H图 故Cmn图是极大的非H图 定理(Chvatal) 若G是n≥3的非H简单图则G度弱与某个Cmn图 用度序列判定定理的逆否命题来证明即可Cmn图族中每个图都是某个n阶非简单图的极图如果n阶简单图G度优于所有的Cmn图族则G一定是H图 定理的条件是必要条件而非充分条件 比如5阶圈C5度弱于C2,5但它还是H图 即非H图一定度弱于Cmn图族中的某个度优于所有Cmn图族一定是H图。 除此之外别无它意所以用该定理来判断H图时写出G(n)的度序列再写出所有的Cmn图族度序列如果度优于所有则它是H图否则不能判断 推论G为n阶简单图若n≥3且满足下面条件则其一定为H图 则可以得到非H图的边数上限满足边数如此的非H图只有C1,n和C2,5证明若不然由Chvatal定理G一定度弱于Cm,n计算Cmn他是小于等于上面的一串的所以|E|也小于那一串和条件中大于那一串矛盾只是充分条件非充要 哈密尔顿图
定义
经过图G中每个点的路称为哈密尔顿路H路经过图G中每个点的圈称为哈密尔顿圈H圈存在哈密尔顿圈的图称为哈密尔顿图H图
性质
性质1如果二部图G是哈密尔顿图则它的二部划分(X,Y)满足|X||Y| 性质2若G1和G2是H图则G1xG2是H图 证明G1的H圈为u1u2...upu1G2的H圈为v1v2...vqv1分为奇数和偶数来讨论 - 奇数与偶数的区别在于遍历到每个点的顺序不一样因为要从(u1,v1)点出发你需要最终到达(up,v1)或者(u1,vq)才可不然的话是构不成圈的而因为奇偶的问题到这从(u1,v1)到达(up,v1)和(u1,vq)的路线不同所以需要分类来讨论这里都是偶数为行奇数为列来排列点 - 性质3定理若G是H图则对于V的每个非空真子集S均有ω(G-S)≤|S| 证明设C的H圈。对V的任意非空子集S易知ω(C-S)≤|S|(这是圈嘛)。C是G的生成子图生成子图肯定没有原图结构牢靠一些所以ω(G-s)≤ω(C-S)所以得证这只是必要条件不是充分条件即H图都具有这个性质但是满足该条件不一定是H图彼得森图不是H图但满足定理可以用于判断某图不是H图对这个定理可以将S设为一点x则ω(G-x)≤|x|1则ω(G-x)1则说明哈密尔顿图没有割点 性质4若连通图不是2-连通的则G不是H图 证明若连通图不是2-连通的所以其一定是1连通的所以存在割点假设割点为v所以ω(G-v)2|v|1所以该图不是H图所以H简单图中一定不存在割点 性质5若图G包含H路则对V(G)的每个真子集S有ω(G-S)≤|S|1 证明这个和性质3很像证明是一样的从一条路上删去一个点最多两个连通分支删去k个则最多有K1个连通分支 性质6若图G是H图且不是圈则G至少包含2个度不小与3的顶点 - 证明因为连通图G不是圈则图G至少包含一个度数大于3的顶点否则图G是圈。若图G只包含一个度数大于等于3的顶点则其结构必为几个块相交于一点因此该点为割点所以该图不是H图矛盾所以得证
H图的判定 充分条件1Dirac定理。对于n≥3的简单图G如果G中有δ(G)≥n/2那么G是H图 充分条件 证明反证若不然设G是一个满足定理条件的极大非H简单图显然G不能是完全图否则G是H图所以在G中任意取两个不相邻顶点u和v考虑Guv由G的极大性Guv是H图有与G是非H图Guv的每个H圈必然包含边uv所以在G中存在起点为u终点为v的H路P。设P为v1v2...vnv1uvnv令S{vi|uvi1∈E(G)}T{vj|vjv∈E(G)}对于S和T显然vn不在S∪T中|S∪T|n同时S∩T∅否则设vi∈S∩T由vi∈T可得vnvi∈E则v1vi1也∈E则v1vi1vivn...v1则为圈且H圈所以矛盾所以S∩T∅所以d(u)d(v)|S||T||S∪T|n这与条件矛盾所以得证感觉只要会用就行 充分条件2Ore定理对于n≥3的简单图G如果G中任意两个不相邻的顶点u与v有d(u)d(v)≥n则G是H图充分条件 Ore定理比Dirac更紧证明与Dirac完全类似下界不能再变化 充分条件3若G1和G2是同一个点集V的两个闭图则GG1∩G2是闭图 定义若对d(u)d(v)≥n的任意一对点和v都是相邻的则称G是闭图证明对任意的w∈V有dG(w)≤dG1(w)dG(w)≤dG2(w)所以由dG(u)dG(v)≥n可得dG1(u)dG1(v)≥ndG2(u)dG2(v)≥n由G1和G2是闭图u和v在G1和G2中都邻接所以u和v在G1和G2中都相邻故u和v在G中也相邻从而G是闭图闭图的交一定是闭图但是并不一定 闭包 定义若一个与G有相同点集的闭图G‘使G包含于G且对异于G‘的任何图H若有G包含于H包含于G’则H不是闭图则称G‘是G的闭包 也就是说G的闭包是包含G的极小闭图搁这扯犊子呢定义一大堆 闭包的构造方法将图中度数之和至少是图的顶点个数的非邻接顶点对递归的连接起来知道不再由这样的顶点对存在为止。 即使得度数之和≥n的顶点对都成为邻接的从而成为闭图 一个图的闭包不一定是完全图 定理任意图G的闭包是唯一的 证明设G1和G2是G的闭包则显然由G包含于G1G包含于G2可得G包含于G1交G2由于由闭包定理G1交G2是闭图其包含于G1也包含于G2如若它比G1G2还小则G1G2就不能称之为闭包了所以它们三者相等 充分条件4G是n阶简单图u和v是G中不相邻的顶点且满足d(u)d(v)≥n则G是H图的充要条件是Guv为H图 和Ore定理有点像但是又不完全一样忽略了任意的uv证明必要性若G是H图则显然Guv也是H图。充分性设Guv是H图C是一个H圈如果C不含边uv则G中本来就含有H圈则得证如果圈C中有uv边设Cuvv3v4...vnu令G1Guv则dG1(u)dG(u)1,dG1(v)dG(v)1所以dG1(u)dG1(v)dG(u)dG(v)2≥n2一定存在i(3≤i≤n-1)使得u与vi相邻v与vi1相邻若不存在这样的i因为v3,v4...,vn-1中有dG1(u)-2个点u相邻则v4,v5..vn就有dG1(u)-2个点不能与v相邻从而dG1(v)≤(n-1)-(dG1(u)-2)n1-dG1(u)这与dG(u)dG(v)2≥n2矛盾所以一定存在i(3≤i≤n-1)使得u与vi相邻v与vi1相邻从而G中存在不经过uv的H圈C1uvivi-1...v3vi1vi2...vnu所以G是H图 充分条件5Bondy定理一个简单图G是H图当且仅当它的闭包是H图 证明若G的闭包等于G结论显然成立若G的闭包和G不同设ei是为了构造G的闭包而依次添加的所有边G是H图当且仅当Ge1是H图Ge1是H图当且仅当Ge1e2是H图如此反复下去可以得到定理结论 推论设G是n≥3的简单图若G的闭包是完全图则G是H图 显然呀完全图一定是H图闭包是H图则一定是H图 推论G是n≥3的简单图若G中每个点的度d(v)≥n/2则G是H图 dirac定理废话··· 推论G是n≥3的简单图若G中任何两个不邻接的点u和v均有d(u)d(v)≥n则G是H图 就是Ore定理 充分条件6度序列判定法设简单图G的度序列是(d1,d2...dn)d1≤...dn且n≥3若对任意的kn/2或有dkk或有dn-k≥n-k则G是H图 也就是对于小于n/2的k满足两个条件中的一个就可以这个太麻烦了不用证明 例题若G是度序列(d1,d2,...dn)的非平凡简单图且满足d1≤d2≤...≤dn证明弱不存在小于(n1)/2的正整数m使得dmm且dn-m1n-m则G有H路 证明在G外加一个新点v把它和G的所有顶点连接得图G1G1度序列(d11,d21,...dn1,n)因为不存在····由度序列判定定理知G1是H图所以去掉点v显然G有H路
补充有割点的图不一定是非哈密尔顿图注意这里是图而非简单图若是简单图成立而图的话可以是哈密尔顿图加一个自环即为反例
