图论与路由

① 图论中的邻接与关联两术语的含义

邻接是点与点或者边与边之间的关系。在无向图中，如果两个点之间内至少有一条边相连，容则称这两个点是邻接（adjacent）的。同样，如果两条边有共同的顶点，则两条边也是邻接的。

关联是点与边之间的关系。一个点如果是一条边的顶点之一，则称为该点与该边关联（incident）。

② 离散数学与图论什么关系，离散数学中的图就是图论吗

图论是离散数学研究的众多对象之一。离散数学用“图”的方法研究图论，但图论是一种理内论，其容他学科也有自己的研究方法（如数据结构也有图论部分）。无论如何，各学科都保留了图论的基本概念（有向与无向、点集、边集、回路、最短路径等）与算法理论（Dijkstra、最小生成树、DFS等）

③ 联图的定义，关于图论的。

图G与H的联图是一个新的图，一般记为GVH，表示在G与H的基础上，再将G的每一个点与H的每一个点之间连接一条边。严格定义看图片。

④ 图论的基本概念有哪些

1、有向图和无向图

有向图，就是有方向的图；所谓无向图，就是没有版方向的图。

2、路径和环权

我们把没有经过重复的点的路径就叫做简单路径。

环的定义是在路径的定义的基础上做了一定的拓展，首尾相接的路径我们就把它叫做一个环。同样我们也有简单环，也就是除开首尾以外，剩下的部分不会经过重复的点的环就叫做简单环。

3、极大独立集

如果K是G的独立集，且不是任何其他独立集的真子集，就为极大独立集。

4、极大团

如果一个团不被其他任一团所包含，即它不是其他任一团的真子集，则称该团为图G的极大团。

5、最大团

顶点最多的极大团，称之为图G的最大团。

6、独立集

独立集是指图G=(V,E)中两两互不相邻的顶点构成的集合。

⑤ 路由协议有哪些各有什么作用

路由分为静态路由和动态路由，其相应的路由表称为静态路由表和动态路由表。静态路由表由网络管理员在系统安装时根据网络的配置情况预先设定，网络结构发生变化后由网络管理员手工修改路由表。动态路由随网络运行情况的变化而变化，路由器根据路由协议提供的功能自动计算数据传输的最佳路径，由此得到动态路由表。

根据路由算法，动态路由协议可分为距离向量路由协议（Distance Vector Routing Protocol）和链路状态路由协议（Link State Routing Protocol）。距离向量路由协议基于Bellman-Ford算法，主要有RIP、IGRP（IGRP为Cisco公司的私有协议）；链路状态路由协议基于图论中非常著名的Dijkstra算法，即最短优先路径（Shortest Path First，SPF）算法，如OSPF。在距离向量路由协议中，路由器将部分或全部的路由表传递给与其相邻的路由器；而在链路状态路由协议中，路由器将链路状态信息传递给在同一区域内的所有路由器。 根据路由器在自治系统（AS）中的位置，可将路由协议分为内部网关协议（Interior Gateway Protocol，IGP）和外部网关协议（External Gateway Protocol，EGP，也叫域间路由协议）。域间路由协议有两种：外部网关协议（EGP）和边界网关协议（BGP）。EGP是为一个简单的树型拓扑结构而设计的，在处理选路循环和设置选路策略时，具有明显的缺点，目前已被BGP代替。

EIGRP是Cisco公司的私有协议，是一种混合协议，它既有距离向量路由协议的特点，同时又继承了链路状态路由协议的优点。各种路由协议各有特点，适合不同类型的网络。下面分别加以阐述。

2 静态路由

静态路由表在开始选择路由之前就被网络管理员建立，并且只能由网络管理员更改，所以只适于网络传输状态比较简单的环境。静态路由具有以下特点：

· 静态路由无需进行路由交换，因此节省网络的带宽、CPU的利用率和路由器的内存。

· 静态路由具有更高的安全性。在使用静态路由的网络中，所有要连到网络上的路由器都需在邻接路由器上设置其相应的路由。因此，在某种程度上提高了网络的安全性。

· 有的情况下必须使用静态路由，如DDR、使用NAT技术的网络环境。

静态路由具有以下缺点：

· 管理者必须真正理解网络的拓扑并正确配置路由。

· 网络的扩展性能差。如果要在网络上增加一个网络，管理者必须在所有路由器上加一条路由。

· 配置烦琐，特别是当需要跨越几台路由器通信时，其路由配置更为复杂。

3 动态路由

动态路由协议分为距离向量路由协议和链路状态路由协议

⑥ 研究图论与网络最优化算法这个方向有什么用

研究这个算法的最终目的肯定是降低算法的时间复杂度以最快时间得到结果，也就是计算效率内的提容升，很多涉及到优化计算的软件都需要这个算法的支持，现在软件的框架变成很简单，但是核心的算法是很重要的，如果说就业的话，面很窄，但是一般人也很少会这个，会的人又用得到，薪水应该会不错

⑦ 什么是路由啊 路由的组成 以及路由的算法

路由：路由（routing）是指分组从源到目的地时，决定端到端路径的网络范围的进程。路由工作在OSI参考模型第三层——网络层的数据包转发设备。路由器通过转发数据包来实现网络互连。虽然路由器可以支持多种协议（如TCP/IP、IPX/SPX、AppleTalk等协议），但是在我国绝大多数路由器运行TCP/IP协议。路由器通常连接两个或多个由IP子网或点到点协议标识的逻辑端口，至少拥有1个物理端口。路由器根据收到数据包中的网络层地址以及路由器内部维护的路由表决定输出端口以及下一跳地址，并且重写链路层数据包头实现转发数据包。路由器通过动态维护路由表来反映当前的网络拓扑，并通过网络上其他路由器交换路由和链路信息来维护路由表。

路由器的组成：

1. RAM（随机存储器）

   功能：存放路由表；存放ARP告诉缓存；存放快速交换缓存；存放分组交换缓冲；存放解压后的IOS；路由器加电后，存放running配置文件；

   特点：重启或者断电后，RAM中的内容丢失。

2. NVRAM（非易失性RAM）

   功能：存储路由器的startup配置文件；存储路由器的备份。

   特点：重启或者断电后内容不丢失。

3. FLASH（快速闪存）

   功能：存放IOS和微代码。

   特点：重启或者断电后内容不丢失；可存放多个IOS版本（在容量许可的前提下）；允许软件升级不需替换CPU中的芯片。

4. ROM(只读存储器)

   功能：存放POST诊断所需的指令；存放mini-ios；存放ROM监控模式的代码。

   特点：ROM中的软件升级需要更换CPU的芯片（还好这种情况比较少遇到)

5. CPU（中央处理器）

   衡量路由器性能的重要指标，负责路由计算，路由选择等。

6. 背板：

   背板能力是一个重要参数，尤其在交换机中。

路由算法：又名选路算法，可以根据多个特性来加以区分。算法的目的是找到一条从源路由器到目的路由器的“好”路径（即具有最低费用的路径[1]）。算法设计者的特定目标影响了该路由协议的操作；具体来说存在着多种路由算法，每种算法对网络和路由器资源的影响都不同；由于路由算法使用多种度量标准（metric），从而影响到最佳路径的计算。

算法分类：主要有RIP、IGRP（IGRP为 Cisco公司的私有协议）；链路状态路由协议基于图论中非常著名的Dijkstra算法，即最短优先路径（Shortest Path First， SPF）算法，如OSPF。在距离向量路由协议中，路由器将部分或全部的路由表传递给与其相邻的路由器；而在链路状态路由协议中，路由器将链路状态信息传 递给在同一区域内的所有路由器。 根据路由器在自治系统（AS）中的位置，可将路由协议分为内部网关协议 （Interior Gateway Protocol，IGP）和外部网关协议（External Gateway Protocol，EGP，也叫域 间路由协议）。域间路由协议有两种：外部网关协议（EGP）和边界网关协议（BGP）。EGP是为一个简单的树型拓扑结构而设计的，在处理选路循环和设置 选路策略时，具有明显的缺点，已被BGP代替。

⑧ 离散数学、组合数学、图论的关系是什么

图论是组合数学的一个分支，而离散数学是专为计算机专业编的数学书，和组合数学有部分知识交叉。

离散数学（Discrete mathematics）是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。离散的含义是指不同的连接在一起的元素，主要是研究基于离散量的结构和相互间的关系，其对象一般是有限个或可数个元素。

组合数学（Combinatorial mathematics），又称为离散数学。广义的组合数学就是离散数学，狭义的组合数学是离散数学除图论、代数结构、数理逻辑等的部分。但这只是不同学者在叫法上的区别。总之，组合数学是一门研究离散对象的科学。

图论〔Graph Theory〕是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。

(8)图论与路由扩展阅读：

一、离散数学学科内容

1、集合论部分：集合及其运算、二元关系与函数、自然数及自然数集、集合的基数。

2、图论部分：图的基本概念、欧拉图与哈密顿图、树、图的矩阵表示、平面图、图着色、支配集、覆盖集、独立集与匹配、带权图及其应用。

3、代数结构部分：代数系统的基本概念、半群与独异点、群、环与域、格与布尔代数。

4、组合数学部分：组合存在性定理、基本的计数公式、组合计数方法、组合计数定理。

5、数理逻辑部分：命题逻辑、一阶谓词演算、消解原理。

二、图论的起源

众所周知，图论起源于一个非常经典的问题——柯尼斯堡（Konigsberg）问题。

1738年，瑞典数学家欧拉( Leornhard Euler)解决了柯尼斯堡问题。由此图论诞生。欧拉也成为图论的创始人。

1859年，英国数学家汉密尔顿发明了一种游戏：用一个规则的实心十二面体，它的20个顶点标出世界著名的20个城市，要求游戏者找一条沿着各边通过每个顶点刚好一次的闭回路，即“绕行世界”。用图论的语言来说，游戏的目的是在十二面体的图中找出一个生成圈。

这个生成圈后来被称为汉密尔顿回路。这个问题后来就叫做汉密尔顿问题。由于运筹学、计算机科学和编码理论中的很多问题都可以化为汉密尔顿问题，从而引起广泛的注意和研究。