图论模型及其算法.ppt

NOIp图论算法与模型构建 长沙市一中曹利国 图的存储结构 两点之间是否有边 A i j 0或1 需要n n的二维数组 稀疏图 顶点多 边数少 稠密图 顶点少 边数多 完全图 每两条边都有一个顶点 图的遍历 dfs bfs图的连通性 对一个图 可以分解为多个连通分量 如何找到一个生成树 MST最小生成树 一个有n个结点的连通图的生成树是原图的极小连通子图 且包含原图中的所有n个结点 并且有保持图联通的最少的边 网络流的流量问题 noi 匹配问题 图结构 图结构包括 点边图涉及到的概念边的权点的度 图的储存结构 矩阵邻接表邻接多重表十字链表 无向图邻接表 1 5 2 4 3 12345 1 5 4 3 2 2 2 3 1 2 4 5 4 5 邻接链表每一个顶点有一个所有与之相邻的链表每一条边2个 对无向图 要在两个顶点的链表中都加入空间复杂度O E 对稀疏图这种方式比较好 邻接表 Pascal语言constmaxv 10000 typeTnode record 定义顶点类型c integer 顶点编号next Tnode 此点的邻接链表end Var 数组g表示每个顶点的邻接链表 的链表头 哨兵g array 1 maxv ofTnode n m i a b integer t Tnode C 语言 includeusingnamespacestd constintmaxv 10000 structTnode 定义顶点类型intc 顶点编号Tnode next 此点的邻接链表 数组g表示每个顶点的邻接链表 的链表头 哨兵Tnodeg maxv intn m i a b Tnode t 邻接表的实现A 指针 图G有n个顶点 编号从1到n 有m条有向边 输入时每行两个整数ab 表示边为从顶点a连接到顶点b 下面程序用指针实现图的邻接链表 Pascal语言procedureins x integer varp Tnode Begin 插入链表子过程new t t c x t next p next p next t end beginreadln n m 初始化邻接链表 哨兵 fori 1tondog i next nil 读入边 插入邻接链表fori 1tomdobeginreadln a b ins b g a ins a g b 无向边时再加入 end C 语言voidins intx Tnode 无向边时 邻接表的实现A 指针 Pascal语言constmaxV 1000 最多顶点数maxE 10000 最多边数typeTnode record 定义顶点类型c integer 节点编号next integer 此节点的邻接链表end vare array 1 maxE ofTnode g array 1 maxV ofTnode n m efree i a b t integer procedureins x integer varp Tnode begin 取一个空元素插入链表p后e efree c x e efree next p next p next efree efree efree 1 新空元素下标end C 语言constintmaxV 1000 最多顶点数maxE 10000 最多边数structTnode 定义顶点类型intc 顶点编号intnext 此点的邻接链表 数组g表示每个顶点的邻接链表 的链表头 哨兵Tnodeg maxV e maxE intn m i a b efree t voidins intx Tnode 新空元素下标 邻接表的实现B 数组 Pascal语言beginreadln n m 初始化邻接链表 哨兵 fori 1tondog i next 1 efree 1 读入边 插入邻接链表fori 1tomdobeginreadln a b ins b g a ins a g b 无向边时 end C 语言intmain cin n m efree 0 初始化邻接链表 哨兵 for i 1 i a b ins b g a ins a g b 无向边时 邻接表的实现B 数组 TypeLink Node Node Recordv w Longint 顶点和费用 Next Link End Map Array 1 Maxn ofLink 用临接表记录的图 Read n m s t Fori 1tomdoBeginRead a b c New p p v b p w c p Next Map a Map a p End 图的遍历 从图中某一顶点出发 按某种搜索方法访遍其余顶点 且使每一顶点仅被访问一次 这一过程称为图的遍历 遍历图的基本搜索方法有两种 深度优先搜索DFS和广度优先搜索BFS 这两种方法都适用于有向图和无向图 图的深度优先搜索遍历 图的深度优先遍历DFS算法是每次在访问完当前顶点后 首先访问当前顶点的一个未被访问过的邻接顶点 然后去访问这个邻接点的一个未被访问过的邻接点 这样的算法是一个递归算法 连通图的深度优先遍历算法思想 1 访问初始顶点v并标记顶点v已访问 2 查找顶点v的第一个邻接顶点w 3 若顶点v的邻接顶点w存在 则继续执行 否则回溯到v 再找v的另外一个未访问过的邻接点 4 若顶点w尚未被访问 则访问顶点w并标记顶点w为已访问 5 继续查找顶点w的下一个邻接顶点wi 如果v取值wi转到步骤 3 直到连通图中所有顶点全部访问过为止 深度优先遍历的程序实现 邻接表 Pascal 图的一般结构typegraph node record end typeAdjList recordid integer next AdjList end varn nodes S i integer nodes array 1 maxN ofgraph node visited array 1 maxN ofinteger adj array 1 maxN of AdjList 标识项点有没有访问过 每个顶点都有邻接链表 邻接链表的节点数据结构 深度优先遍历的程序实现 邻接表 Pascal 置每个点标识为 未访问 从所有未被访问的点k出发 调用DFS k proceduresearch begink integer fork 1ton nodesdovisited k 0 fork 1ton nodesdoifvisited k 0thenDFS k end 置被访问节点的 时间 次序 访问k的所有相邻的节点 procedureDFS k integer begin 从k出发搜索varj AdjList begininc S i visited k S i j adj k while jNULL dobeginifvisited j id 0thenDFS j id j j next end end 图的广度优先搜索遍历 图的广度优先遍历BFS算法是一个分层搜索的过程 和树的层序遍历算法类同 它也需要一个队列以保持遍历过的顶点顺序 以便按出队的顺序再去访问这些顶点的邻接顶点 连通图的广度优先遍历算法思想 1 顶点v入队列 2 当队列非空时则继续执行 否则算法结束 3 出队列取得队头顶点v 访问顶点v并标记顶点v已被访问 4 查找顶点v的第一个邻接顶点col 5 若v的邻接顶点col未被访问过的 则col入队列 6 继续查找顶点v的另一个新的邻接顶点col 转到步骤 5 直到顶点v的所有未被访问过的邻接点处理完 转到步骤 2 宽度优先遍历的程序实现 邻接表 C 图的一般结构structgraph node structAdjList intid AdjList next intn nodes S index 0 graph nodenodes maxN intvisited maxN AdjList adj maxN 标识项点有没有访问过 每个顶点都有邻接链表 邻接链表的节点数据结构 宽度优先遍历的程序实现 邻接表 C 置每个点标识为 未访问 从所有未被访问的点k出发 调用BFS k voidsearch intk for k 0 k n nodes k visited k 0 for k 0 k n nodes k if visited k BFS k 宽度优先遍历的程序实现 邻接表 C intq maxN voidBFS intk intfront back q 0 k front back 0 for fronnext if visited j id q back j id visited j id S index BFS用的队列 一般全局 Front back 队列不空 访问k的所有相邻的节点 图的连通性问题 有向图的强连通子图生成树问题 强连通子图 有向图的强连通子图强连通子图中 任两个节点都直接或间接相连以深度优先搜索为基础的算法 1 4 2 7 8 5 3 6 生成树问题 无向图的最小生成树 贪心思想 Prim算法 适用于点少的图Kruskal算法 适用于边少的图有向图的最小树形图 局域网 net 某局域网内有n n 100 台计算机 由于建网时工作人员的疏忽 现在网内存在回路 造成网络卡的现象 我们用f i j 表示i j之间连接的畅通程度 f i j 1000 f i j 值越小表示i j之间连接越通畅 f i j 为0表示i j之间无网线连接 现在我们需要除去一些连线 使得网络中没有回路 并且被除去网线的 f i j 最大 请求出这个最大值 实际问题 生成树 一个 V 个点的图 取其中 V 1条边 并连接所有的顶点 则组成原图的一个生成树 属性 v 1条边 连通 无环 最小生成树 加权图的最小生成树是一棵生成树 其所有边的权值之和不会大于其它任何生成树 简单讲 找出连接所有点的最低成本路线 最小生成树 MST 红边连接了所有顶点 所以构成一棵生成树权和 1 2 4 4 7 8 9 环属性 一棵生成树上 增加一条边e 再删除e所在环上的最大边 会得到另一棵 更好 的生成树 如果e不是最大边 最小生成树 MST 算法原理 9 4 剪切属性 在图中 剪切将顶点划分成两个不相交集合 交叉边为这些顶点在两个不同集合的边 对于任何一个剪切 各条最小的交叉边都属于某个MST 且每个MST中都包含一条最小交叉边 最小生成树 MST 算法原理 7 4 9 最小边原则 图中权值最小的边 如果唯一的话 一定在最小生成树上 唯一性 一棵生成树上 如果各边的权都不相同 则最小生成树是唯一的 反之不然 最小生成树 MST 算法原理 Prim算法构建MST的过程 将1号节点置入集合S中 找到所有连接S中的节点和非S中的节点的边中的权值最小的那一条 并标记这条边 同时将连接的非S中的节点加入S集合 重复2步骤 直到所有节点都在S中了 1 2 4 3 5 6 1 2 3 1 2 3 1 2 1 2 算法描述1 1 将G剪切成两个集合A B A中只有一个点r 2 取最小权的交叉边 x y x A y B 3 将y加入A 4 如果已经加了n 1条边 结束 否则 转 3 最小生成树 MST Prim算法 算法描述2 MST Prim G r 从任意点r出发 生长成一MSTfori 1tondodis i 初始化每点到A集合的最小值inA i false 设顶点不在A中dis r 0 将r设为0 或 准备取出fori 1tondov get min 取dis 中最小的值c和顶点v inA v true v放入A中sum sum c c加入MST的总和中updata v 枚举交叉边 v B 改进dis 最小生成树 MST Prim算法 算法要点 每次求最小权交叉边时 如果都重新计算 则显然要枚举 x y x A y B O n 2 时间复杂度 其实每次A中只是增加一个新顶点v 最多有交叉边 v y 修改量只有与v有边的顶点 为O n 只需记录下B中的每个元素y与A所有元素中最小权边 则求最小值最多为O n 有时可以用 堆 优化 最小生成树 MST Prim算法 Kruskal算法 Kruskal算法同样是常用的求最小生成树的算法之一 其算法思想如下 Kruskal算法每次选择n 1条边 所使用的贪婪准则是 从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中 注意到所选取的边若产生环路则不可能形成一棵生成树 Kruskal算法分e步 其中e是网络中边的数目 按耗费递增的顺序来考虑这e条边 每次考虑一条边 当考虑某条边时 若将其加入到已选边的集合中会出现环路 则将其抛弃 否则 将它选入 这个算法可以用并叉集优化到o e e 的时间复杂度 表示阿克曼反函数 Kruskal算法 找到连接两个不同连通分量 由已标记的边构成的 的边中 权值最小的那一条 标记这条边 重复1步骤 直到所有节点都在同一连通分量中 1 2 4 3 5 6 1 2 3 1 2 3 1 2 1 2 MST Kruskal G 1 将G所有条边按权从小到大排序 图mst开始为空 2 从小到大次序取边 x y 3 若加入边 x y mst就有环 则放弃此边 转 2 4 将边 x y 加入mst 如果已经加了n 1条边 结束 否则 转 2 最小生成树 MST Kruskal算法 算法要点 Kruskal算法的最难点在于怎样判断加入边 x y 后是否形成了环 问题可化为 判断边 x y 的两个顶点x y在图 实际是森林 mst中是否已经连通 如果已经连通 加入边将形成环 否则 不形成环 并查集 连通点集之类问题 有高效算法 并查集 最小生成树 MST Kruskal算法 算法描述 MST Kruskal G fori 1tondof i i 初始化并查集sort e e m 边按大小排序c 0 取边的计数器fori 1tomdo 从小到大取边v find set e i v 左端点所在连通块 根 u find set e i u 同查并集的getfather 右端点所在连通块 根if u v不在同一连通块上 如果不在同一连通块union v u 合并两连通块sum sum g v u 加入这条边的权if c n 1 break if取了n 1条边 结束 最小生成树 MST Kruskal算法 时间复杂度分析Prim算法普通的方法O V 2 Prim算法中用 堆 方法O E V log V 对稀疏图较好Kruskal算法O E log E N A V 对稀疏图较好 最小生成树 MST 时间复杂度 图的拓扑结构 拓扑排序顶点表示活动的网 AOV 网例如课程选择中课程之间的关系关键路径边表示活动的网 AOE 网求图中总长最长的路径例如计算工程所需时间 拓扑排序算法 寻找入度为0的节点将找到的节点放入队列中 删除所有这个节点引出的边重复1 直至没有度为0的节点如果有节点不在队列中 则说明原图中有环 否则无环 1 2 5 3 6 4 7 求关键路径算法 对给定的图进行拓扑排序按照拓扑排序的结果扩展和标记 1 2 3 4 5 6 8 7 9 6 4 5 1 1 2 4 7 9 2 4 最短路径 对在权图G V E 从一个源点s到汇点t有很多路径 其中路径上权和最少的路径 称从s到t的最短路径 简单讲 找出连接两个给定点的最低成本路径单源最短路径问题 求从源点s到其它所有点的最短路径问题 最短路径 ShortestPath 定义 三角形性质设源点s到点x y的最短路径长度为dis x dis y x与y之间的距离是len x y 则有下面的 三角形定理 dis x len x y dis y 松驰若在处理过程中 有两点x y出现不符合 三角形定理 则可改进一下 松驰 if dis x len x y dis y dis y dis x len x y 最短路径 ShortestPath 属性 X Y S 如果边没有负权的 我们可以用类似Prim算法的贪心算法 Dijkstra算法 算法描述1 SP Dijkstra G s 1 将G中顶点分成两个集合A B A集合中由已经求出最短路径的顶点组成 B集合是其它顶点 开始时A中只有一个点s 2 从B集合中取一个当前最短的顶点v 3 把v加入A集合 并对v相连的顶点试做 松驰 4 如果 A V 结束 否则转 2 最短路径 Dijkstra算法 Dijkstra算法 Dijkstra算法中心 1 2 4 3 3 1 6 3 2 0 Dist值 4 3 2 1 节点号 3 2 6 5 4 选择 标记 扩展 算法描述2 SP Dijkstra G s 求单源s到其它点的最短距离fori 1tondodis i 初始化每点到s距离inA i false 设顶点不在A中dis s 0 将dis s 设为0 准备取出fori 1tondov get min 取dis 中最小的值c和顶点v inA v true v放入A中updata v 检查 v B 松驰dis sum sum c c加入MST的总和中 最短路径 Dijkstra算法 与prim不相同点 cookingBessie喜欢为在外面的奶牛做晚餐 Bessie按响铃给他们一个信号叫他们进来就可以了 晚餐将在T 1 T 1 000 000 毫秒完成 而且Bessie强调那些想吃她晚餐的奶牛必须准时到 这些牛在F 1 F 500 各不同的草地标号为1 F用P 1 P 10 000 个双向的小路连接 Bessie在第1个草地 给出一头牛走每一条小路所用的时间 问多少个草地上的奶牛可以在T毫秒内到Bessie所在的草地 假设多头牛可以共享一条路 最短路径 实例 如果边有负权的话 Dijkstra算法是错误的 这里需要不断迭代地做 松驰 直到无 松驰 为止 算法描述3 SP Bellman G s 1 初始化每点到s点的最短距离为 2 取所有边 x y 看x能否对y松驰 3 如果没有任何松驰 则结束break 4 如果松驰次数 N 转 2 5 否则 图中有 负圈 最短路径 Bellman ford算法 算法说明 Bellman ford算法N次迭代就可以判断图中是否有 负环 取所有边有两种方法 1 扫描每一点的邻接链表 2 用有序点对 x y 记录边时 可直接取边 但要请注意对无向图 要注意 y x 也要松驰 对于求s到某点t的最短距离 可能因为其它地方有 负环 而出现问题 要预处理 最短路径 Bellman ford算法 算法描述4 SP Bellman G s 求单源s到其它点的最短距离fori 1tondodis i 初始化每点到s距离dis s 0 将dis s 设为0fori 1tondo 最多迭代nrel false 是否有松驰标志for每条边 x y 取图的每一条边if dis x len x y dis y 不满足三角形性质dis y dis x len x y 松驰dis y rel true ifrel falsereturn0 没有一次松驰 则结束return 1 迭代了n次 有负圈 最短路径 Bellman ford算法 对迭代的改进 SPFA算法Bellman ford算法中 每次都要检查所有的边 这个看起来比较浪费 对于边 x y 如果上一次dis x 没有改变 则本次的检查显然是多余的 我们每次只要从上次刚被 松驰 过的点x 来看看x能不能松驰其它点即可 SPFA算法中用BFS中的队列来存放刚被 松驰 过的点 由于顶点个数为 V 队列如果用数组的话显然要用 循环队列 使用空间 最短路径 SPFA算法 算法描述 SP SPFA G s 求单源s到其它点的最短距离fori 1tondodis i vis i false 初始化每点到s距离 不在队列dis s 0 将dis s 设为0vis s true count 1 s放入队列head 0 tail 0 q 0 s 队列头尾指针while count 0 dov q head 队头节点vfor每条边 v i 与v相连的每一条边if dis v len v i dis i 不满足三角形性质dis i dis v len v i 松驰dis i if vis i false 不在队列 则加入队列vis i true count 1 tail 1 q tail i vis v false head 1 count 1 v出队列 最短路径 SPFA算法 求每对节点之间最短距离问题 例如 求一个图的直径 即所有最短路径中最长的 如果多次调用单源最短路径算法 效果并不好 特别是对有负边的图 如果无负环 则有简单的Floyd warshell算法 这是动态规划算法 最短路径 Floyd算法 动态规划算法定义d i j k 为路径中间只允许经过节点1 k的情况下i到j的最短路距离它有两种情况最短路经过点k d i j k d i k k 1 d k j k 1 最短路不经过点k d i j k d i j k 1 综合起来 状态转移方程为d i j k min d i k k 1 d k j k 1 d i j k 1 边界条件d i j 0 len i j 不存在的边权可为 最短路径 Floyd算法 算法描述6 SP Floyd G 求每对节点的最短距离fori 1tondoforj 1tondodis i j len i j 初始化边界条件fork 1tondo K放在最外层 数组少一维fori 1tondoforj 1tondoif dis i k dis k j dis i j 状态转移dis i j dis i k dis k j 最短路径 Floyd算法 Dijkstra单源非负O V 2 对稠密图好可用 堆 优化O E log V 对稀疏图较好Bellman Ford单源无负环O V E 可先用Dijkstra预处理优化SPFA用更新队列优化 时间复杂度平均好 但不确定 Floyd全源无负环O V 2 最短路径 算法比较 网络流与匹配问题 网络最大流最小费用最大流二分图的最大匹配二分图的最佳匹配 网络流算法 寻找增广链 并根据增广链修改流量 重复这一步骤 直到不再存在增广链 如果需要在此基础上求最小费用最大流 只需从增广链的选择上着手 二分图与匹配算法 二分图的匹配算法又称匈牙利算法匈牙利算法的中心 可增广轨不断寻找可增广轨 并根据可增广轨修改匹配最佳匹配只是在选择可增广轨时 将匹配的权值作为选择的条件 图的应用 模型构建 例题1 TRAVEL 一个城市中有N个车站 已知M条连接这些车站的公共汽车单向路线 设计算法求出从第一号车站到第N号车站的最少换车次数 分析 这道题粗看起来似乎不太简单 但我们仔细分析一下题目就会发现 这道题实际上可以转化为最短路径问题来进行求解 考虑经过的所有路线中 每条路线都只保留一头一尾两个车站 则经过的车站数目再减2实际上就是所求的换车次数了 要使换车次数最少 也就是要找从1到N的一条最短路径 而图中的边也需要重新设计 在每一条路线中 任两个结点均由其中的前者向后者连一条边 然后将每条边的长度都定为1 利用图论模型进行构造 例题2 圆桌吃饭问题n个人围着一张圆桌吃饭 每个人都不愿意两天与同一人为邻 问最多能坐多少天 并给出一种排列方案 查分约束系统 转化为图论模型 设G V E 为一完全图 V n 图中的每个顶点代表一个人 连结顶点的边表示人之间的相邻关系 因此 每种围绕圆桌的吃饭方案就成为图中的一条哈密尔顿回路 设L 为G中的一条哈密尔顿回路 其中所含的边的集合记为e L 问题转化为 求m与L1 L2 Lm 使得e Li e Lj 并且m达到最大值 构造方法 作一圆 把圆周分成n 1等分 标上n 1个刻度 将顶点1至n 1依次排列在圆周上 顶点n放在圆心 先从圆心出发 向任意点连一条线 再从这点出发 沿圆周向左右两个方向迂回连线 直到连完圆周上所有的点 再连回圆心 这样就构造出一条哈密尔顿回路 保持所有的顶点位置不变 把所有连线围绕圆心逆时针方向旋转一个刻度 得到一条新的哈密尔顿回路 这样连续旋转 n 1 div2次 就得到了 n 1 div2条回路 N 5 构造图象 充分展示各变量之间的关系 例3 01串问题 NOI 给定N L0 A0 B0 L1 A1 B1 设计一个长度为N的01串 使得对于任何连续的长度为L0的子串 0的个数大于等于A0 且小于等于B0 对于任何连续的长度为L1的子串 1的个数大于等于A1且小于B1 解题分析 模式1分析不等式 设hi为01子串s0 si 1 I n 中1的个数 其中s0 0 h0 0 显然 由hi的定义可以得出不等式0 hi 1 hi hi hi 1 1 移项即得 0 hi hi 1 1 hi 1 hi L0 b0 hi hi l0 当I L0时 根据条件 Si L0 1 Si中0的个数 L0 hi hi L0 在a0 b0之间 即a0 L0 hi hi L0 b0 a0 L0 hi L0 hi b1 hi l1 hi 当I L1时 根据条件 Si L1 1 Si中1的个数 hi hi L1 在a1 b1之间 即a1 hi hi L1 b1 a1 hi hi L1 一旦有了h序列 我们可以由左至右构造s串 如果hi 1 hi 则说明si 0 否则si 1 1 I n 由此看来 问题的关键是如何计算h序列 仔细观察上述推论条件 发现有以下特点 1 除h0 0外 其余的条件都是由 连接的不等式 2 每个不等式都是含两个h未知数 一个常数的一次不等式 可见 所有不等式都整理成了k hi hj它给我们启示 上述不等式类似于连接两点的一条有向边 因此 我们联想到信息学解题中常用的图论知识 模型2构造有向图G我们构造有向图G 如图 其中vi代表s串中的第I位 若k 表明si sj中至少需增加k个1 k为正值 或减少k个1 k为负值 由此得出构造有向图G的方法 0 hi hi 1 1 hi 1 hi a0 L0 hi L0 hi L0 b0 hi hi l0 a1 hi hi L1 b1 hi l1 hi 计算图G的最长路径 我们已构造了一个有n 1个顶点的有向图G 1 图G中无环令D I 表示从顶点0到顶点I的最长路径长度 对于图中每条从点I指向点J的权为C I J 的边 有性质D I C I J D J 注意 这与上述不等式的形式相似 这样 令hi D I h完全符合所有限制条件 即为原不等式组的一组解 2 G中含有环可用反证法证明无解 从s1出发 顺序确定每位二进制数 当hi hi 1时 说明s1 si 1中1的个数与s1 si中1的个数相同 即si为0 否则si为1 最短路 例题4 求第一 第二 第三最短路问题 城市交通 见文档 城市交通分析 在求两点之间的最短路径时 有一种比较优秀的方法 Floyd Warshall 算法 其算法的中心思想是这样的 求A至B的满足中间结点不超过K的最短路径 而后 随着K逐渐增加至N而求出A至B的最短路径 则其算法的结构如下 ForK 1ToN K从1增至N ForA 1ToNDoForB 1ToNDo 求每一对结点的中间结点不超过K的最短路径 IF Map A K 0 And Map K B 0 Then 如果A与K K与B均可达 IF Map A B 0 Or Map A B Map A K Map K B Then 如果A B不可达 或者A B之间的路径不如A K B这条路径短 则改变Map A B 的值 Map A B Map A K Map K B 注 Map A B 为从A到B的最短路的距离 如果A B不可达 则Map A B 0 在求改进M条边使最短路下降最快中 我们同样可以发现 1 将道路A B改造M条边可以分为如下两个问题 如果K是最短路上的一点 一 求A K改造T条边 二 求K B改造M T条边 T可以取从0至M的任意值 问题A B改造M条边的最优解取决与这两个子问题的最优解 2 在求M条边的过程中 始终只与改造T与M T条边的问题发生联系 以上两个特点即为 动态规划 的 无后效性 与 最优子问题 两个性质 所以 这个 城市交通 问题的算法为 动态规划 算法 设Map A B M 的值为从A到B且改造M条边的最短路长度 则 Map A B M Min Map A K T Map K B M T 其中T为从