图计算法在实际生活中的应用

① 算法在实际生活中的应用

求解问题类的、机械的、统一的方法，它由有限多个步骤组成，对于问题类中的每个给定的具体问题，机械地执行这些步骤就可以得到问题的解答。算法的这种特性，使得计算不仅可以由人，而且可以由计算机来完成。用计算机解决问题的过程可以分成三个阶段：分析问题、设计算法和实现算法。
中国古代的筹算口决与珠算口决及其执行规则就是算法的雏形,这里,所解决的问题类是算术运算。古希腊数学家欧几里得在公元前3世纪就提出了一个算法,来寻求两个正整数的最大公约数，这就是有名的欧几里得算法,亦称辗转相除法。中国早已有“算术“、“算法”等词汇，但是它们的含义是指当时的全部数学知识和计算技能,与现代算法的含义不尽相同。英文algorithm(算法)一词也经历了一个演变过程，最初的拼法为algorism或algoritmi,原意为用阿拉伯数字进行计算的过程。这个词源于公元 9世纪波斯数字家阿尔·花拉子米的名字的最后一部分。
在古代，计算通常是指数值计算。现代计算已经远远地突破了数值计算的范围,包括大量的非数值计算,例如检索、表格处理、判断、决策、形式逻辑演绎等。
在20世纪以前，人们普遍地认为，所有的问题类都是有算法的。20世纪初，数字家们发现有的问题类是不存在算法的,遂开始进行能行性研究。在这一研究中,现代算法的概念逐步明确起来。30年代，数字家们提出了递归函数、图灵机等计算模型，并提出了丘奇－图灵论题（见可计算性理论），这才有可能把算法概念形式化。按照丘奇-图灵论题,任意一个算法都可以用一个图灵机来实现，反之，任意一个图灵机都表示一个算法。
按照上述理解，算法是由有限多个步骤组成的，它有下述两个基本特征：每个步骤都明确地规定要执行何种操作；每个步骤都可以被人或机器在有限的时间内完成。人们对于算法还有另一种不同的理解，它要求算法除了上述两个基本特征外,还要具有第三个基本特征:虽然有些步骤可能被反复执行多次，但是在执行有限多次之后，就一定能够得到问题的解答。也就是说，一个处处停机（即对任意输入都停机）的图灵机才表示一个算法，而每个算法都可以被一个处处停机的图灵机来实现
算法分类
算法可大致分为基本算法、数据结构的算法、数论与代数算法、计算几何的算法、图论的算法、动态规划以及数值分析、加密算法、排序算法、检索算法、随机化算法、并行算法。
算法可以宏泛的分为三类：
有限的，确定性算法 这类算法在有限的一段时间内终止。他们可能要花很长时间来执行指定的任务，但仍将在一定的时间内终止。这类算法得出的结果常取决于输入值。
有限的，非确定算法 这类算法在有限的时间内终止。然而，对于一个（或一些）给定的数值，算法的结果并不是唯一的或确定的。
无限的算法 是那些由于没有定义终止定义条件，或定义的条件无法由输入的数据满足而不终止运行的算法。通常，无限算法的产生是由于未能确定的定义终止条件。算法特征一个算法应该具有以下五个方面的重要特征：1、输入。一个算法有零个或多个输入，以刻画运算对象的初始情况。例如，在欧几里得算法中，有两个输入，即m和n。2、确定性。算法的每一个步骤必须要确切地定义。即算法中所有有待执行的动作必须严格而不含混地进行规定，不能有歧义性。例如，欧几里得算法中，步骤1中明确规定“以m除以n，而不能有类似以m除n以或n除以m这类有两种可能做法的规定。3、有穷性，一个算法在执行有穷步滞后必须结束。也就是说，一个算法，它所包含的计算步骤是有限的。例如，在欧几里得算法中，m和n均为正整数，在步骤1之后，r必小于n，若r不等于0，下一次进行步骤1时，n的值已经减小，而正整数的递降序列最后必然要终止。因此，无论给定m和n的原始值有多大，步骤1的执行都是有穷次。4、输出。算法有一个或多个的输出，即与输入有某个特定关系的量，简单地说就是算法的最终结果。例如，在欧几里得算法中只有一个输出，即步骤2中的n。5、能行性。算法中有待执行的运算和操作必须是相当基本的，换言之，他们都是能够精确地进行的，算法执行者甚至不需要掌握算法的含义即可根据该算法的每一步骤要求进行操作，并最终得出正确的结果。算法的描述1、用自然语言描述算法前面关于欧几里得算法以及算法实例的描述，使用的都是自然语言。自然语言是人们日常所用的语言，如汉语、英语、德语等。使用这些语言不用专门训练，所描述的算法也通俗易懂。2、用流程图描述算法在数学课程里，我们学习了用程序框图来描述算法。在程序框图中流程图是描述算法的常用工具由一些图形符号来表示算法。3、用伪代码描述算法伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法的工具。它不用图形符号，因此，书写方便、格式紧凑，易于理解，便于向计算机程序设计语言过度。

② 图论的实际应用例子

图论的实际应用例子如下：

什么是图形？

大多数人对"图形"这个术语有着非常广泛的理解，代表了大多数数学图形描述。然而，正如人们所期望的那样，在数学中有一个非常清晰的定义，即图形是什么，我们围绕它们建立有用的规则和计算，使它们对试图解决的问题有用。

多图是两个顶点之间具有有多条边的图，通常描绘不同的关系。可以想象一下飞机航线路线图，每条航线都是航班号。伦敦和纽约之间会有大量的边（路线）。

伪图（Pseudographs）是允许将顶点连接到自身的图形。毋庸置疑，在描绘人际关系的图表中通常不需要这样做。但是，例如你需要使用图表来描绘办公室中的咖啡订单以及谁正在购买适合他们的商品时，那么采用伪图将非常有用。

在完整的图形中，没有更多的边可以添加到边集上。所有顶点都相互连接。它可以是一个有用的数学工具来证明图形是完整的。

树图也非常明显，但它们在数学上被定义为连接且没有循环的图形。这意味着任何一对不同的顶点都可以通过一组边相互连接，但不可能通过一组边将顶点连接到自身。家谱通常就是这样的一个例子。例如皇室成员，那么可以看看西班牙国王查尔斯二世的家谱。