网站优化北京seo,在东莞找工作上哪个网站,龙岩网站设计找哪家好,在线平面设计师招募例题中有2019年罗马尼亚大师赛第3试题树树#xff1a;一个连通图#xff0c;如果没有一个环#xff0c;则叫树。森林#xff1a;若干个独立的树形成一个森林。链#xff1a;一个特殊的树是节点中#xff0c;除去两个节点的度为1#xff0c;其它均为2#xff0c;叫做链。…例题中有2019年罗马尼亚大师赛第3试题树树一个连通图如果没有一个环则叫树。森林若干个独立的树形成一个森林。链一个特殊的树是节点中除去两个节点的度为1其它均为2叫做链。二叉树如果一个树只有一个节点的度为2其它的节点的度要么为3要么为1那这样的树叫二叉树。树链二叉树之所以重要是因为这些图可以灵活表达计算机内部基本数据结构。例如我们打开一个应用软件按下一个功能键会有菜单弹出或者窗口弹出管理这些菜单与窗口最好的办法是将其组织成树结构。链是计算机内部维护一个动态数组的最佳结构通过插入删除节点只需要修改边指针而不需要真实移动数据。二叉树可以做分类编译。能够灵活运用这些基本结构并用程序语言表达出来是程序员的基本功。那些年薪几十万上百万的程序员对此都有相关的知识与运用经验而习得这些经验与做数学习题差不多也许更简单一点就是要多编写程序但题量会大一点要求格式更严谨一点而已。不论是树还是链其顶点数如果是n的话边数一定是n-1.定理n个顶点n-1条边的图一定是树。证明用归纳法n1命题成立假设nk时命题也成立我们看nk1的情况考虑k1个顶点k1条边这样的图中的一条最长路径如果有一个端点a如果d(d)1,则必然有环因为否则的话可以添加一条边到这条最长路径中使得新路径长度为增加1.删去节点a设与a相邻的一个节点为b同时删除边{ab}就剩下k个节点k-1条边的连通图了按归纳假设这是棵树故nk1时命题成立。例题1.考虑平面的若干点任意两点之间的直线段长度都不相同如果将每个点与其距离最近的点连成一条直线段求证:所画出的线段不会形成一个封闭的多边形。证明首先将这些点当成一个图的顶点按题设的办法将做了的直线段对应成图的一条边形成图G假设G中有环。如下图由于任意两点之间的直线距离最短故这个环路上所有边对应的直线段长度均不相同不妨设最长的线段长度为D对应边为{ab}设a1是与a相邻的顶点a2是与b相邻的顶点边{aa1}{bb2}对应的线段长度分别为D1D2则DD1,D2.故从a出发做出的直线段不能为b从b出发的直线段也不能为a。也就是说按题设根本做不出边{ab}来。因此这个图中没有环路。但即使没有环路也可能有如下图这样两种方式形成闭合的图形。我们接下来证明按题目要求做出的直线段是不能出现交叉现象的。反证法假设作出的线段如下图出现了交叉虚线连接addbbcca则按照题设直线段的做法有ab4ab2ab2dc另一方面设abcd相交于w点则wacwac,wcwbcb,wbwdbd,wdwcad相加得2ab2cdabbccdda矛盾这就证明本题。割边如果一个连通图中去掉一个边就成为非连通的了这条边叫连通图的一条割边。对于树来说没条边都是割边。生成树若图G的的一个子图T包含所有的顶点且为一棵树则称T为图G的生成树。在图G中而不在生成树T中的边称为对应于树T的弦所有弦的集合是树T的补弦的数目就是图G的圈数记作N(G)树枝的数目称为图的秩记作及R(G)。如果G有n个结点m条边则R(G)n-1N(G)m-nl。R(G) N(G)m。生成树的算法去圈法如果连通图G无回路根据的定义则G本身就是一棵生成树。如果连通图G有回路去掉回路的任一条边得到生成子图G1显然G1仍然是连通的如果G1不含回路则G1就是G的生成树否则又可去掉回路的任一条边得到另一个生成子图只要生成图还有回路就去掉回路的一条边由于图的有限性最后一定得到不含回路的生成子图T由于每次去掉回路的一条边并不破坏图的连通性所以T是G的生成树。这种办法可以产生图的生成树。生长法在G中任找一条边e1然后找一条不与e1形成回路的边e2再找一条不与边集合(e1,e2)形成回路的边e3如此继续下去使找的边都不与已找到的边集合形成回路直到过程不能进行下去为止则所有找到的边集合{e1,e2,e3,...,em}构成的图就是G的一棵生成树。设T是图G的一棵生成树由T的树枝和一条弦构成的回路称为对应于这条弦的基本回路基本回路的集合称为基本回路集。如左图是右图的一棵生成树则对应于弦e1的基本回路是C(e1){e1,e6,e7}对应于弦e2的基本回路是C(e2){e2,e7,e8}对应于弦e4的基本回路是C(e4){e4,e3,e8,e9}对应于弦e5基本回路是C(e5){e5 e6 e9}树T的基本回路集是C{C(e1)C(e2)C(e3)C(e4)}如果我们给图上的每个边赋权那么就得到一个赋权的图。例如结点是城市,边的权表示两个城市间的距离,从一个城市出发走遍各个城市,如何选择最优的旅行路线.又如城市间的通信网络问题,如何布线,使得总的线路长度最短等等就是要找一棵生成树且使得生成树的边权的和最小。这样的生成树叫最小生成树。最小生成树的Kruskal算法:设G是有n个结点,m条边(m≥n-1)的连通图.1.将所有边按照权升序排序:e1, e2, e3,… ,emTΦ2.i1.。。。。。m做如下操作如果T∪{ ei }有回路则去掉ei返回2TT∪{ ei };如果inT就是最小生成树结束否则i返回2.例题2.连通图G中每条边赋予一个数设c为最小值如果G中存在一个具有s条边的基本回路求证这个图至少有s个不同的最小生成树。证明利用上面的kruskal算法中间 的支撑树集合T在选前s-1条边时必然都是从这个基本回路中选出的边从s个边中每次选s-1条边总计有s种不同的选法。而这s个s-1条边的集合各不相同所以最终生成的最小生成树至少也有s个。做为高中联赛题目不说kruskal算法直接求证本题应该是不算太难的题。那就需要把kruskal算法的基本思想先说清楚然后再填上上面的答案才能得分。这是常见的高联出题方法。一个连通图G的顶点数为n边数为e则生成树的边为n-1故弦数为e-(n-1)e-n1每个弦对应于一个基本回路。所以有定理顶点数基本回路数n-1e-n1e。线性电路基本分析方程假设一个电路图只有电池与电阻元件总计为e个电路图上的每个元件对应于图的一条边直连不同元件的线路端点收缩为成一个顶点总计有n个顶点。下图表达简单的电路图变换成图论中的图。根据基尔霍夫定律流入流出一个节点(顶点)的电流代数和为0任意一个电路回路的电压代数和为0。注意到一个树中每个节点连出的边不完全相同可以形成n-1个独立的电流方程。每个基本回路都有一条弦是唯一的可以形成e-n1个独立的回路电压方程用电阻乘以电流代表一个电阻元件的电压只要这些电阻阻值确定电池电压确定就可得到e个独立的以流过每个元件电流为变量的一次方程组这个方程组是有唯一解的。这就是电路分析的基本方法也是图论理论的一个来源而现今是现代集成电路CAD软件分析中研究电路电气响应特性的核心方法。树搜索算法深度优先搜索算法(DFS)深度优先搜索的基本思想是在搜索其它他顶点之前尽可能深地渗透到树的深层中。这个想法可以描述如下处理次序a - b -- d -- i - j - k - e - c - f - i - g - h宽度优先搜索算法(BFS)宽度优先搜索的基本思想是在深入到树中之前尽可能多地处理上层顶点。这个想法可以描述如下
