下载文档原格式
问题一：建立一个资源利用的规划模型，需加入时间资源、资金资源。
1、问题的提出1.1基本情况某公司现在新购一生产线，生产电脑配件B1、B2、B3。
已知生产单位产品的利润与所需的劳动力时间、设备台时及单位产品的资金投入，公司的资金拥有量和工作时间拥有量如表1-1所示：表1T项目B1配件种类资源限制B2B3资金（百元）412200劳动力/工时643360设备台时（小323210时）产品利润（元/754件）1.2提出问题1、假设每种配件的市场都是供不应求，不用考虑市场及原材料的供应问题那么在现有的条件下应该如何分配者三种配件的生产才能获得最大利润。
2、模型的建立2.1确定决策变量因为获得最大利润的核心目标，要确定各种配件的生产数量从而去求得所能获得的最大利润。
因此可以设尤，x ,x来表示B1，B2, B3的产量。
1 2 32.2确定目标函数该问题归结为求效益最大化的问题。
这里所追求的利润s应是最大（简写为max）max S = 7 x + 5 x + 4 x1 2 32.3确定约束条件考虑到资金限制和劳动力总工时以及设备台时的要求，会有一定的约束条件用不等式表示参考表1_1数值有'4x + x + 2x < 200<6x + 4x + 3x < 360I3x + 2x + 3x < 210侦1 2 32.4建立模型综合前述各步及变量非负的条件建立起线性规划模型如下。
求变量气(i = 1,2,3)使得目标函数：max S = 7 x + 5 x + 4 x1 2 3取得最大值，并满足如下的约束条件的要求：4x + x + 2x < 2001 2 36x + 4x + 3 x < 360s.t. < 1 2 3|3x i+ 2x2 + 3x3 < 210I x , x , x > 0v 1 2 33、模型的求解分析上述线性规划模型是非标准的线性规划模型，用常规方法将其变为标准型的线性规划模型，然后利用单纯形法进行求解。
运筹学知识点要求运筹学知识点要求第一部分结论1、运筹学的特点（1）以最优性或合理性为核心。
（2）以数量化、模型化为基本方法。
（3）具有强烈的系统性、交叉性特征。
（4）以计算机为重要的技术支持。
2、运筹学模型求解方法：知道迭代算法的原理步骤。
3、运筹学模型（1）运筹学模型：使用较多的是符号或数学模型，大多数为优化模型。
（2）模型的一般结构（3）模型的三大要素决策变量、目标函数及优化方向、约束条件。
（4）了解模型的分类4、建立优化模型解决实际问题（1）要求能对较简单的实际问题建立优化模型。
主要涉及：一般线性规划模型，整数（特别是0－1规划）规划模型。
5、了解运筹学运用领域。
第二部分线性规划1、线性规划模型的几种表示形式及特点2、线性规划模型的标准形式及如何标准化3、线性规划问题各种解的概念及关系（关系图示）（可行解、非可行解、基本解、基本可行解、最优解，基本可行解的个数小于等于）4、线性问题有关解的基本定理（主要是概念理解）（1）不一定都有最优解（2）若有，一定会在基本可行解上达到（3）基本可行解的个数有限小于等于（4）并非所有最优解都是基本可行解（5）了解凸集与凸组合的概念，理解两个最优解的凸组合都是最优解。
（6）可行解为基本可行解的充要条件5、线性规划单纯形法（1）制作初始单纯表（注意非基变量检验系数的求法，特别注意求有待定系数时的检验系数）（2）各种解的判别条件，对于最大化目标函数问题，包括：唯一最优解：有最优解无穷多最优解存在一个k 有：（或称之为线性规划问题存在可择最优解）无界解，存在k 有：（3）线性规划问题求解结果中解的情况有最优解（唯一最优解、无穷多最优解），无界解，无可行解（4）基变换中入基变量的确定A 、入基变量的必要条件（）B 、最速上升准则的理解，不是使目标函数改进最大，而是使目标函数改进速度最大。
m nC m nC 0<j σ0≤j σ0≤j σ0=j σ0,0'≤>k k p 且σ0≥j σ（5）最小比值确定出基变量的目的：保证基变换后新的基本解是可行的。
运筹学模型的类型运筹学模型是指通过数学方法来描述和解决复杂问题的一种工具。
根据问题的性质和要求，运筹学模型可以分为以下几种类型：1. 线性规划模型（Linear Programming Model，简称LP）：线性规划是一种优化问题，它的目标是在满足一些约束条件下，使某个线性函数取得最大或最小值。
线性规划模型广泛应用于生产调度、资源分配、物流运输等领域。
2. 整数规划模型（Integer Programming Model，简称IP）：整数规划是线性规划的扩展，它要求决策变量只能取整数值。
整数规划模型常用于生产调度、排产计划、网络设计等问题。
3. 非线性规划模型（Nonlinear Programming Model，简称NLP）：非线性规划是一种优化问题，它的目标函数和约束条件都可以是非线性的。
非线性规划模型广泛应用于经济学、金融学、工程学等领域。
4. 动态规划模型（Dynamic Programming Model，简称DP）：动态规划是一种优化方法，它将一个复杂问题分解为若干个子问题，并逐步求解这些子问题。
动态规划模型常用于生产调度、资源分配、投资决策等问题。
5. 排队论模型（Queuing Theory Model，简称QT）：排队论是一种研究等待线性的数学理论，它可以用来描述和分析顾客到达、服务时间、系统容量等因素对系统性能的影响。
排队论模型广泛应用于交通运输、通信网络、医疗卫生等领域。
6. 决策树模型（Decision Tree Model，简称DT）：决策树是一种分类和回归的方法，它可以将一个问题分解为若干个子问题，并逐步求解这些子问题。
决策树模型常用于金融风险评估、医学诊断、市场营销等领域。
总之，不同类型的运筹学模型适用于不同的问题领域和求解目标，选择合适的模型可以帮助我们更好地解决实际问题。
运筹学模型
运筹学模型，又称作“模型解决方案”，是一种将抽象的或复杂
的问题转化成客观的数字模型的方法。
它的研究内容包括对数学模型、解答技术和应用技术的研究。
运筹学模型可以解决许多复杂的解答问题，如飞机起降时间安排、体育竞赛规则、战略规划等，这些问题比较复杂，无法通过决策树或经验分析来解决。
运筹学模型，最早由英国经济学家威廉赫尔贝克（William R. Hertz）提出。
他在1898年发表了著名的《运筹学模型》，认为模型
通过统计分析和多元解释的方式来描述经济行为和社会发展趋势。
他在这篇文章中提出了“多元线性回归模型”，这是当时关于经济运筹
学模型领域第一次重大突破。
赫尔贝克的模型可以分为两类：定性模型和定量模型。
定性模型，例如允许研究者进行排除法分析，以此发现模式的多样性。
此外，它还可以运用其他定性分析工具，如思维网络、分类树、社会格局等，来解决复杂的运筹学问题。
而定量模型，则可以利用多元线性回归，对复杂的数据进行建模，探寻其规律性和行为规律。
运筹学模型在许多领域都有重要作用，如工程、管理、决策分析、运输等领域，它们能够更有效地帮助解决复杂的实际问题，节约时间和资源，从而提高生产效率。
例如，对于运输问题，可以使用运筹学模型来分析最佳路线；如果是生产问题，则可以使用运筹学模型来计算最优的生产策略。
另外，运筹学模型还可以用来评估决策的风险和收益，从而指导企业决策。
总之，运筹学模型是一种有效的解决复杂问题的方法，它不但能够有效地解决实际问题，而且还可以提供给企业更有成效的决策和策略框架，为企业提供有效的发展指引。
运筹学分配问题建模
运筹学分配问题是指在特定的条件下，如何合理地分配资源以达到最优化的解决方案的问题。
这类问题可以用数学模型来描述和解决。
在运筹学中，分配问题通常涉及到有限的资源和不同的需求或约束条件。
在建模时，可以使用线性规划、整数规划、动态规划或网络流等方法来求解。
以一个简单的分配问题为例，假设有三个项目（A、B、C）需要分配有限的资源（如人力、时间或资金）。
每个项目会产生不同的效益（如收益或效率），同时存在一些约束条件（如人力资源的限制或时间的限制）。
我们的目标是在满足约束条件下，最大化总体效益。
为了建模这个问题，我们可以定义以下变量和参数：
令x1、x2、x3分别表示项目A、B、C的分配比例；
令c1、c2、c3分别表示项目A、B、C的效益；
令r表示可用资源的数量；
令a1、a2、a3分别表示项目A、B、C所需资源的数量。
然后，我们可以建立以下数学模型：
目标函数：maximize Z = c1*x1 + c2*x2 + c3*x3
约束条件：a1*x1 + a2*x2 + a3*x3 <= r
x1 + x2 + x3 = 1
x1, x2, x3 >= 0
这个数学模型可以被解释为：我们要最大化总体效益（Z），
但同时要满足资源约束条件（第一个约束条件），并且项目的分配比例之和为1（第二个约束条件）。
当我们求解这个数学模型时，可以得到最优的分配比例，从而实现最大化总体效益。
这只是一个简单的示例，实际的运筹学分配问题可能更加复杂，可以根据具体情况进行进一步的建模和求解。
运筹学模型的分类和类型运筹学是一门应用于决策制定和问题解决的学科，它通过数学模型和分析方法来优化资源的利用。
运筹学模型是在特定情境中描述问题和优化目标的数学表示。
根据问题的性质和优化目标的类型，运筹学模型可以被分类为多种类型。
在本文中，我将介绍一些常见的运筹学模型分类。
一、线性规划模型：线性规划模型是最基本的运筹学模型之一。
它的特点是目标函数和约束条件均为线性的。
线性规划模型常用于求解资源分配、生产计划、物流运输等问题。
通过线性规划模型，我们可以找到使资源利用最优化的决策方案。
某公司需要确定每种产品的生产数量，以最大化总利润，且需满足各种资源约束条件，这时可以使用线性规划模型进行求解。
二、整数规划模型：整数规划模型是在线性规划模型的基础上引入整数变量的扩展。
在某些情况下，问题的决策变量只能取整数值，这时就需要使用整数规划模型进行求解。
某物流公司需要确定车辆的调度方案，每辆车的装载量可以是整数，这时可以使用整数规划模型来求解最佳调度方案。
三、动态规划模型：动态规划模型是一种考虑时间因素的决策模型。
它通常用于求解多阶段决策问题。
动态规划模型通过将问题划分为多个阶段，并建立各阶段之间的转移方程，来寻找最优决策序列。
在项目管理中，我们需要确定每个阶段的最佳决策，以最小化总工期和成本，这时可以使用动态规划模型进行求解。
四、网络流模型：网络流模型是一种描述网络中资源分配和流量传输的模型。
它通常用于求解网络优化问题，如最小费用流问题、最大流问题等。
网络流模型中，节点表示资源或流量的源点、汇点和中间节点，边表示资源或流量的传输通道。
通过建立网络流模型，我们可以确定资源的最优分配方案，以及网络中的最大流量或最小成本。
在供应链管理中，我们需要确定货物从生产商到消费者的最佳流向，以最小化总运输成本，这时可以使用网络流模型进行求解。
五、排队论模型：排队论模型是一种描述排队系统的模型。
它通常用于评估系统性能指标，如平均等待时间、平均逗留时间等。
运筹学优化模型与算法运筹学是一门研究如何做出最优决策的学科，它利用数学模型和算法来解决各种优化问题。
在现实生活中，我们经常面临各种决策问题，比如如何合理安排生产计划、如何规划物流配送路线、如何优化投资组合等等。
这些问题都可以通过运筹学的优化模型和算法来解决。
运筹学的优化模型是建立在一定的假设和约束条件下的数学描述，它可以帮助我们理清问题的结构和关系，并将问题转化为数学形式。
通过对模型进行求解，我们可以得到最优解或者近似最优解，从而指导我们做出决策。
在运筹学的优化模型中，目标函数是至关重要的。
目标函数是衡量优化问题的指标，我们希望通过优化算法来使目标函数取得最大值或最小值。
在实际应用中，目标函数可以是利润最大化、成本最小化、效率最大化等等，具体取决于问题的特点和需求。
除了目标函数，约束条件也是运筹学优化模型中不可或缺的一部分。
约束条件是对问题的限制和要求，它们限制了决策变量的取值范围和关系。
通过合理设置约束条件，我们可以确保最优解在可行解空间内，从而使得优化结果具有实际意义。
在运筹学的优化模型中，常见的建模方法包括线性规划、整数规划、非线性规划、动态规划等等。
这些方法各有特点，适用于不同类型的优化问题。
线性规划适用于目标函数和约束条件均为线性的问题；整数规划适用于决策变量为整数的问题；非线性规划适用于目标函数或约束条件为非线性的问题；动态规划适用于具有重叠子问题性质的问题等等。
根据问题的特点，我们可以选择合适的建模方法来求解。
除了优化模型，运筹学还涉及到优化算法的设计和求解。
优化算法是用来求解优化模型的具体方法和步骤。
常见的优化算法包括单纯形法、分支定界法、梯度下降法、遗传算法等等。
这些算法各有优缺点，适用于不同类型的优化问题。
通过合理选择和设计优化算法，我们可以高效地求解复杂的优化问题。
运筹学的优化模型和算法在各个领域都有广泛的应用。
在生产管理中，通过合理安排生产计划和调度，可以提高生产效率和降低成本；在物流配送中，通过优化路线和运输方式，可以提高物流效率和降低物流成本；在金融投资中，通过优化投资组合和风险控制，可以获得更高的投资收益和降低投资风险等等。
运筹学运输模型应用例题
当谈到运筹学输模型的应用例题时，有很多不同的领域和情景可以涉及。
以下是几个常见的例子：
1. 生产计划：一个公司想要最大化其生产效率和利润。
运筹学输模型可以用来确定最佳的生产计划，包括资源分配、生产顺序和生产量等方面。
通过考虑供应链、库存管理和各种约束条件，可以优化生产计划，使得企业能够在最小成本下达到最高的产出。
2. 运输网络优化：一个物流公司需要确定最佳的货物运输路线和配送计划。
运筹学输模型可以考虑诸如货物数量、运输成本、时间窗口和路线限制等因素，以确定最佳的路线和调度方案，从而提高物流效率并降低运输成本。
3. 供应链优化：对于一个复杂的供应链系统，例如零售商和供应商之间的关系，运筹学输模型可以帮助确定最佳的订购量、库存水平和补货策略，以最大程度地减少库存成本和滞销风险，并确保及时交付。
4. 设施选址：当一个公司需要选择新的工厂或分销中心的位置时，运筹学输模型可以帮助确定最佳的选址方案。
通过考虑到达时间、配送成本和市场需求等因素，可以找到最优的位置来最大化服务范围并降低运营成本。
5. 项目调度：在项目管理中，一个公司需要合理地安排各项任务的执行顺序和时间安排，以确保项目能够按时交付。
运筹
学输模型可以帮助确定最佳的项目调度方案，考虑到任务之间的依赖关系、资源约束和最小化项目总工期等目标。
这些只是一些例子，实际上运筹学输模型在各个领域都有广泛的应用，包括金融、医疗、能源等。
通过建立准确的数学模型，并采用适当的优化算法，可以帮助决策者做出更明智的决策，提高效率和利润，并解决复杂的实际问题。
运筹学模型
运筹学是一门多学科交叉的学科，它研究最优化管理和决策问题，旨在帮助组织有效地实现其目标。
运筹学模型是一种经过精心设计的数学模型，用于寻找最优解决方案，以解决组织中面临的复杂问题。
运筹学模型是一种结构，它涵盖了组织中的所有变量，以及这些变量之间的关系。
运筹学模型可以被用于解决不同类型的问题，例如资源配置、路径规划、调度、生产计划等等，以帮助组织实现最佳效果。
运筹学模型包括三个基本部分，即规划、分析和决策。
规划是指组织定义其目标，确定可以达到目标的所有可能解决方案。
分析是指评估这些解决方案的可行性和优劣，并从中选择最佳解决方案。
最后，决策是指根据最佳解决方案，决定组织如何实施它。
为了有效地使用运筹学模型，组织必须清楚地确定其目标、对所有可能的解决方案进行全面的评估、根据分析结果选择最佳解决方案、并有效地实施这一解决方案。
此外，组织还应该及时监测整个运筹学过程，以确保最佳解决方案的有效实施，以及及时调整解决方案，以应对组织中的变化。
总的来说，运筹学模型是一种有效的管理和决策工具，可以帮助组织有效地实现其目标。
它可以帮助组织确定最佳解决方案，并有效地控制其实施和监控整个过程。
运筹学的基本理论与方法运筹学（Operations Research）是一门应用数学学科，旨在通过量化建模和优化方法，解决实际问题和做出最优决策。
本文将介绍运筹学的基本理论与方法，包括问题建模、优化模型、经典算法等方面。
一、问题建模运筹学的第一步是把实际问题转化为数学模型，以便进行分析和求解。
问题建模通常涉及以下几个方面：1. 目标：明确问题的目标是什么，如最大化利润、最小化成本、优化资源利用率等。
2. 决策变量：确定可以控制或调整的变量，即决策变量，如生产数量、采购量、分配方案等。
3. 约束条件：考虑问题的限制条件，如资源限制、技术限制、时间限制等。
二、优化模型基于问题建模的基础上，可以建立相应的优化模型，常见的几种常用优化模型如下：1. 线性规划：线性规划是最经典的优化模型之一，目标函数和约束条件都是线性的。
线性规划可以通过诸如单纯形法、内点法等算法求解。
2. 整数规划：整数规划是线性规划的拓展，决策变量需要取整数值。
整数规划一般通过分支定界法、割平面法等算法求解。
3. 动态规划：动态规划适用于具有决策阶段和状态转移的问题，通过将问题分解为子问题，利用最优子结构性质，建立递推关系来求解。
4. 近似算法：对于复杂优化问题，精确求解往往是不可行的，此时可以采用近似算法，如启发式算法、模拟退火算法、遗传算法等。
三、经典算法运筹学中有一些经典的算法常用于求解各类优化问题，下面介绍几个典型的算法：1. 单纯形法：单纯形法是一种求解线性规划问题的经典算法，通过不断在可行域内移动以达到最优解。
2. 分支定界法：分支定界法通常用于解整数规划问题。
通过不断划分问题的可行域，并对每个子问题求解，最终得到整数规划的最优解。
3. 模拟退火算法：模拟退火算法是一种全局优化算法，通过模拟金属退火过程来避免陷入局部最优解。
4. 遗传算法：遗传算法是一种模拟生物进化过程的优化算法，通过选择、交叉、变异等操作来搜索最优解。
四、应用领域运筹学方法在各个领域都有广泛应用，包括但不限于以下几个方面：1. 生产与物流：优化生产计划、供应链管理、仓储布局等，以提高生产效率和降低成本。
运筹学模型运筹学是研究决策问题的科字，它主要研究如何在有限的资源条件下获得最佳解。
它是个综合性的学科，是由多学科科学的知识、方法和经验结合而成的。
运筹学模型是用来分析决策问题的重要工具，它利用数学技术和计算机技术，根据具体情况构建模型，从而获得最优解。
运筹学模型的构建过程主要有三个步骤，即问题求解、模型开发和解算。
首先，根据实际环境和问题特征，正确描述和理解问题，将其表示为一个模型。
其次，根据模型的表示形式，采用恰当的运筹学方法，按照一定的程序进行求解。
最后，将求解的结果以图表、数据等形式呈现出来，供决策者参考；此外，还可对结果进行分析，以便做出更有效的管理决策。
运筹学模型主要应用于交通运输、医疗保健、人力资源、金融投资、能源管理、质量管理、生产调度、计划管理、物流管理等领域，有助于节约时间和资源，提高自动化决策的精度和效率。
运筹学模型的开发主要集中在模型构建、数值算法两个方面。
模型构建也就是建立模型的过程，这个过程需要根据实际问题一步步进行，确定模型的变量、约束条件以及目标函数，并要求解出最优解。
数值算法则是实现模型的过程，大多数模型只能通过迭代的方式近似求解，因此，对数值算法的选择也是重要的。
常见的运筹学方法有贪婪法、动态规划、整数规划等，它们都有一定的优缺点，可以根据问题的特性和实际情况，合理选择适当的算法，以求得最优解。
此外，为了更好地服务决策者，运筹学模型还需要系统化地进行建模和验证。
在建模时，必须结合实际环境，考虑问题的复杂性，全面准确地把握各个变量和约束条件；在验证时，需要采用合适的方法，测试模型的准确性，与实际环境相匹配，以保证模型的可用性。
总之，运筹学模型是决策问题分析的有效工具，它有助于节约时间与资源，提高决策的准确性。
运筹学模型的开发主要集中在模型构建和数值算法两个方面，要求在建模过程中考虑问题复杂性、全面把握各个变量，而在验证过程中，要采用合适的方法测试模型的准确性，与实际环境相匹配。
运筹学方法与模型运筹学是运用数学、统计学和计算机科学等专业知识和技术，以科学化的方法帮助人们做出最佳决策的学科。
运筹学研究的对象包括决策分析、优化算法、模拟系统、控制论以及信息论等多个方面。
方法。
1.数学方法：运筹学在问题解决中利用了大量数学原理和方法，如线性规划、非线性规划、统计分析、概率论等。
2.统计方法：运筹学在处理大量数据时应用的方法，如数据采集、整理、分析和解释等，让人们可以据此推断数据的趋势。
3.计算机方法:运筹学借助计算机技术，使用计算机建模和仿真技术，将复杂的问题转化为简单的研究对象，并求解其最优解。
4.运筹思想：运筹学旨在找到最优策略，其思想是在各种因素和条件的制约下，达到最佳结果的决策。
这是一个重要的应用范畴。
模型。
1.线性规划模型：这是一种基本的运筹学模型，它通过建立一系列线性等式或不等式来描述形式化问题。
通过优化算法求解，找到最优解。
2.整数规划模型：整数规划模型是在线性规划的基础上，加上整数限制条件的扩展。
为求解整数规划问题，需要使用各种启发式算法、分枝限界法等。
3.随机规划模型：随机规划模型是在考虑风险或不确定性因素的情况下，寻找最优策略的模型。
4.动态规划模型：动态规划模型是用于描述决策过程的数学模型。
通过建立方程组，求解最优决策方案，它广泛应用于生产、库存、资源分配问题等领域。
总结。
运筹学作为一门独立的学科，旨在建立数学模型，找到最优决策方案。
在现代企业管理和科学研究中，它的应用越来越广泛。
运筹学所涉及的方法和模型丰富多样，它不断的激发着人们通过科学的手段来寻找最佳解决方案的创新思维。
第5章 运筹学模型5.2 图论模型图论是运筹学的一个重要分支，它是建立和处理离散类数学模型的一个重要工具。
用图论的方法往往能帮助人们解决一些用其它方法难于解决的问题。
图论的发展可以追溯到1736年欧拉所发表的一篇关于解决著名的“哥尼斯堡七桥问题”的论文。
由于这种数学模型和方法直观形象，富有启发性和趣味性，深受人们的青睐。
到目前为止，已被广泛地应用于系统工程、通讯工程、计算机科学及经济领域。
传统的物理、化学、生命科学也越来越广泛地使用了图论模型方法。
本章将在介绍图的一些基本概念的基础上，着重介绍最小生成树、最短路、最大流及最小费用最大流问题。
5.2.1 图的基本概念城市之间的交通关系，家族成员之间的关系，工厂、企业、事业单位内部，部门之间的上下关系，工程中各个工序之间的先后关系等等，用图形来描述往往是很有益的。
图论是研究某种特定关系的一门学问。
1.图图 (graph) 由若干个点 (称作顶点，vertex) 和若干条连接两两顶点的线段（称edge ）组成。
通常，顶点可用来表示某一事物，边用来表示这些事之间的某种关系。
如图5-1中的五个顶点可以代表五个城市。
如果两个顶点之间有一条边连接，就表示这两个城市之间有一条铁路。
同样，它也可以代表五个人。
如果两个人认识，则用一条边把这两个顶点连接起来。
图5-1由于图是用来表示某些事物之间的联系，因而在画图时，顶点位置，边的长短、曲直是无关紧要的。
只要两个图的顶点可以一一对应，并且使得对应的顶点之间是否有边相连完全相同，就可以认为是同一个图。
例如：图5-1也可以画成图5-2的形式。
图 5-2 设图的顶点集合V ={n v v v ,...,, 21}, 边的集合 E ={m e e e , ... ,,21} 把图记作) , (E V G =。
这里大括号 { } 内的元素是没有顺序的，而小括号（ ）内的元素是有顺序的。
如果边e 连接顶点u 和v ，则记作e = {v u ,}。
u 和v 称作e 的端点，e 称作u 和v 的关联边。
如果u 和v 之间有一条边，即{v u ,}∈E ，则称u 和v 相邻。
如果两条边有一个共同的端点，则称这两条边相邻。
没有关联边的顶点称作孤立点。
两个顶点之间可以有不止一条边，端点相同的两条边称作平行边，如果一条边的两个端点重合，则称作环。
不含环和平行边的图称作简单图。
如图5-3中), (E V G =,V={6i 1 | ≤≤i v },E ={9j 1 | ≤≤j e }, 1e ={21,v v },}, {322v v e =, 21 v v 和相邻，31 v v 和不相邻。
21 e e 和相邻。
6v 是孤立点。
7e 和8e 是平行边，9e 是环。
设P 是图) , (E V G =中以顶点u 和v 为首尾、点边交替的序列。
如果序列中每一条边的端点恰好是与它前后相邻的两个顶点，则称这 个序列p 是从u 到v 的一条链。
当链的首尾相连时，它称作圈。
如果链上所有顶点都不相同， 图5-3 则称这条链是初级链。
如果圈上除首尾两个定点之外所有顶点都不相同，则称这个圈是初级圈。
例如，在图5-3中，},,,,,,,,,,{452232211911v e v e v e v e v e v p =是一条从41 v v 到的链，但不是初级链。
},,,,,,,,,,{112658475412v e v e v e v e v e v p =是一个圈，但不是初级圈。
在简单图中，可以用顶点序列表示链和圈。
任意两个顶点间都有一条链的图称作连通图。
图5-3不是连通图。
设有两个图) , (E V G =和),(111E V G =。
如果E E V V ⊆⊆11,则称1G 是G 的子图，如果),(111E V G =是) , (E V G =的子图，并且V V =1，则称1G 是G 的生成子图。
如果V V ⊆1， 1E 是E 中所有端点属于1V 的边组成的集合，则称1G 是G 的关于1V 的导出子图，图5-4中的3个图均是图5-3的子图，其中（b ）是生成子图，（c ）是关于},,{5211v v v V =的导出子图。
图 5-4我们常常可以利用图比较简便的解决某些实际问题，下面是一个例子。
例 1 有5位运动员参加游泳比赛，表5-1给出每位运动员参加的比赛项目。
问如何安排比赛，才能是每位运动都不连续的参加比赛？表 5-1赛没有同一运动员参加，则可以把这两项紧排在一起，用一条边把代表这两个项目的顶点连起来。
这样得到 图5-5，不难看出，为了解决这个问题，只需找到一条包含所有顶点的初级链。
如P= {B,C,D,A,E}是一条初级链，其对应的比赛安排是：50m 蛙泳，100m 蝶泳，100m 自由泳，50m 仰泳，200m 自由泳。
图 5-52.有向图在图) , (E V G =中，边是没有方向的，即},{},{u v v u =，这种图称作无向图。
但是，有些关系不是对称的，用图表示这样的关系时，边是有方向的，用箭头表示，称作弧。
从顶点u 指向v 的弧a 记作),(v u a =。
u 称作a 的始点，v 称作a 的终点。
这样的图称作有向图。
设顶点集合V ={n v v v ,...,, 21}，弧集合A ={m a a a , ... ,,21}，有向图记作) , (A V D =，和无向图类似，在有向图中也有环、平行弧、子图等概念。
当然，在有向图中必须注意到弧是有方向的。
例如，平行弧不仅要求两条弧的端点相同而且要求它们的始点和始点相同，终点和终点相同。
设P 是有向图) , (A V D =中从顶点u 到v 的点弧交替的序列。
如果序列中每一条弧的始点和终点恰好分别是与它前后相邻的顶点，则P 称D 是中的一条路。
当路的首尾相连时，称作一条回路。
和无向图一样，顶点全不相同的路称作初级回路。
例如，图5-6给出一个有向图) , (A V D =，其中V ={4321,,, v v v v }，}, 81|{≤≤=i a A i ),(),,(232211v v a v v a ==， 图 5-6},,,,,,{1435461v a v a v a v p =是一初级回路。
3. 树无圈的连通图称作树(tree)。
设) , (E V G =为一个连通图，如果树) , (E V T =是) , (E V G =的生成子图，则T 称作G 生成树。
图5-7给出3棵树，其中（b ）和（c ）都是图5-1的生成树。
图 5-7不难证明树有下列性质：性质1 树的边数等于顶点数减1。
性质2 树的任意两个顶点之间有且只有一条初级链。
性质3 在树中任意去掉一条边，就得到一个非连通图。
性质4 在树中任意两个顶点之间添加一条边，恰好产生一个初级圈。
5.2.2 最小生成树设图) , (E V G =，对每一条边E e ∈， 指定一个实数)(e ω，我们称这样的图为赋权图，记作) ,, (ωE V G =，其中ω是边集合E 到实数集的映射，实数)(e ω称作边的权。
当},{j i v v e =时，常把)(e ω记作j i ω。
类似地，对有向图) , (A V D =的每一条弧A a ∈指定一个实数)(a ω，得到赋权有向图，记作) ,, (ωA V D =，)(a ω称作弧a 的权，当),(j i v v a =时，常把)(a ω记作j i ω。
在实际应用中，权可以有各种各样的含义，如距离、时间、费用、运输量、流量等。
1．最小生成树的概念设) ,, (ωE V G =是一个连通的赋权图，),(S V T =是G 的生成树，把T 中所有边的权之和称作树T 的权，记作)(T ω，即∑∈=se e T )()(ωω，G 中权和最小的生成树*T称作最小生成树。
2．最小生成树的算法Kruskal 于1956年给出一个求最小生成树的算法：避圈法。
其基本方法如下：(1) 画出图) ,, (ωE V G =中的全部顶点。
(2) 按边权的大小从小到大选边（n 个顶点需n-1步），并且每一步都不能构成圈。
例 2 现有5个城市，打算用铁路把它们连接起来。
这5个城市之间哪两个可以修建铁路以及铁路的长度如图5-8所示（每一条边旁边有一个数字，即表示这段铁路的长度）。
试给出修建铁路的方案，使铁路总长度最短。
图 5-8解 此题提出的问题是求给定赋权图的最小生成树。
做题步骤如图5-9所示：图 5-9注意，在第四步,可以不取},{42v v ，而取},{53v v ，得到另一棵最小生成树，其权和为12。
如图5-10所示。
可见最小生成树不唯一。
计算在每一步都要判断添加的边是否构成圈。
这在图不很复杂时，直接观察并不困难。
但在使用计算机时，则必须进一步给出形式化的方法，计算的具体步骤如下：Kruskal 算法1. 按权从小到大排列边)()()(21m e e e ωωω≤≤≤令 n i i v l i ≤≤←1 ,)( 图 5-10 2. 令S ←φ,K ←1(φ表示空集)。
3. 设)()( },,{v l u l v u e k ==若，则转6；否则令}{k e s s ←，执行4。
4. 对所有i i v v l u l v l 的顶 )}(),(max{)(=令 )}(),(min{)(v l u l v l i ←。
5. 若|S|= n-1,则 是S 最小生成树的边集合，计算结束；否则执行6。
（|S|表示S 中元素的个数）6. 若k=m ，则说明图是非连通的，停止计算；否则令k ←k+1，转3。
5.2.3最短路问题1. 最短路的概念设 (,)G V E =为连通图，图中各边 (,)i j v v 有权 i j ω（其中i j ω=+∞ 表示 ,i j v v之间没有边），,s t v v 为图中任意两点，所谓最短路问题就是求一条路μ，使它为从s v 到t v 的所有路中总权最小的路。
即：(,)()i j i jv v L μμω∈=∑ 最小。
2. 图的矩阵表示对于赋权图( , )G V E =，由其边(,)i j v v 的权i j w ，构造矩阵()i j n n A a ⨯= ，其中：(,)inf() (,)0 i j i j i j i j i jw v v Ea v v E v v ⎧∈⎪=∞∉⎨⎪=⎩称矩阵A 为赋权图G 的权矩阵。
例如图5-11的权矩阵为：图5-113．最短路的算法（1）由图写出其权矩阵。
（2）由Matlab 软件求最短路。
（3）软件计算程序为：function[D,R]=floyd(a) n=size(a,1); D=afor i=1:n for j=1:n R(i,j)=j; endend Rfor k=1:n for i=1:n for j=1:nif D(i,k)+D(k,j)<D(i,j) D(i,j)=D(i,k)+D(k,j); R(i,j)=R(i,k); end end end k D REnd例 3求下图5-12从1v 到6v 的最短路。
