第3期 毛华，等：利用二元拟阵K。图的一种建格方法 ·335· 模型的建立 很难给人们带来直接帮助，需要对交通运输网络进 行简化和直观化，得到一个简化的网络。若出行者 图论主要研究图的拓扑性质，为任何一个包含 需要计算出自己所居住的城市和其他任意两个城 某种二元关系系统提供一种分析和描述模型。众 市的距离和，即第1节定义9中的基最小圈，判断走 所周知，交通网络可以用图表示出来，也可把交通 哪个基最小圈距离和最短时，探究交通网络K图模 网络里的距离当作两点之间的权值加入进去。 型中的最小经济圈所需出行的路径距离就变得有 复杂网络中的交通网络对应图论里一类特殊 意义了。 的图结构，具有与应用相关的很多重要特征。对于 2.2模型的条件 一些网络中出现的复杂的网络，作如下处理。 设有个城市，每个城市看作一个顶点，两个城 1)对于两个顶点之间具有多重边的情况，选择 市之间有路可达时，用一条线相连接，建立城市网 其中权值最小的边。 络图。图中顶点用1,2，…，。表示，组成集合V= 2)当两个顶点之间的权值一样时，任意选择其 {1,2,…,心}。网络图中，之间有路径可达，记 中一条边，固定下来，成为最熟悉的一条道路。 相连接的边为em,将此交通网络图记为G=(V,E), 3)对于带环图的这种情况，因为实际问题考虑 得G为一个有限无向图。出行者从给定的一个顶 的是对于一个工厂的运输，自身运输没有任何实际 点城市，出发去办事，要求路径中必须经过两个顶 的意义。例如：如果是一家超市，自身对于自身运 点城市（除去给定城市顶点以外的其他任意两个顶 输也没有意义，所以不予考虑。 点城市)，再返回到出发城市顶点1。由于出行者 具有重边或有环的图都可以转化为简单图应 走的道路为一个三角形，现在的问题是要选择一个 对出行问题，因此复杂网络图可以转化为简单图， 三角形在距离和花费的时间都少的三角形作为出 用以讨论相应的出行问题。由于在具有n个顶点的 行者的最终出行方案，这就需要找到所有可能的出 简单图中，K图结构最复杂，所以只要解决了K。图 行方法，换句话说，出行者需要出行前找到所有需 的出行问题，其他的简单图的出行问题将会迎刃而 要走过的路径和出行方案，以便从中选择最佳方 解。对于非K的n个顶点的简单图，因为它们是 案，这些方案对决策者综合路径距离、时间、花费决 K的子图，所以可以通过加边，使其成为K图，只 策时有重要的意义，可以帮助其更加直观、快速地 需将新加边的权值定义为0，采用本文的方法，完全 做决定，节约决策时间。 可以解决出行问题。基于以上的讨论，只需解决具 2.3问题的分析 有K,图这样的交通网络的出行问题，因此本文只研 交通城市之间的无向图G进行转化后是顶点 究K图。 为n的完全图，记G为K,图。因K,图对应的关联 现有n个城市，任意两个城市均由交通道路连 矩阵满足二元拟阵M,知定义7的含圈基满足定义 接。一位出行者要从自己所居住的城市去其他n-1 3的拟阵M,即实际生活中人们出行方案里的最小 个城市办事情，要求到达其他任意两个城市后再回 三角形圈。于是在K,图的二元拟阵的标准矩阵表 到自己所居住的城市，现在的问题是：如何找到以3 示如下：在对应组成基本圈的三条边下标记1，没有 个城市为三角形经济圈的一个出行方案。 组成基本圈的边下标记0，然后把得到的矩阵作为 首先建立一个网络模型，构建其关联矩阵。由 含0和1的形式背景。在上面进行概念格的探索和 于关联矩阵是一个0-1矩阵，信息提取中的任一个 证明时发现，在K图中将二元拟阵中的基本圈即定 形式背景可视为一个0-1矩阵，因此依据形式背景 义9的基最小圈，作为对象，每两个顶点之间相连的 的特殊性，建立概念格信息提取方法，进而找到人 边作为属性，建立形式背景，找寻概念会遵循一定 们所需的最适合出行方案。 的数学规律，运用此规律进行建格，速度很快。 2.1问题的提出 2.4模型的解决 在不同城市间构建现代化交通网络，实现城市 2.4.1K。图的建格模型 间交通一体化，将会极大方便交通出行。问题是： 根据定义3给出K图的标准矩阵表示。当顶 如何在众多出行方案中选取合适的方案，成为人们 点n=3时，根据引理1的公式得边数为3，含圈基的 出行前需要解决的问题。交通运输网络错综复杂， 个数为-1=2，与其中一个顶点相连接构成的基最２ 模型的建立 图论主要研究图的拓扑性质，为任何一个包含 某种二元关系系统提供一种分析和描述模型。 众 所周知，交通网络可以用图表示出来，也可把交通 网络里的距离当作两点之间的权值加入进去。 复杂网络中的交通网络对应图论里一类特殊 的图结构，具有与应用相关的很多重要特征。 对于 一些网络中出现的复杂的网络，作如下处理。 １）对于两个顶点之间具有多重边的情况，选择 其中权值最小的边。 ２） 当两个顶点之间的权值一样时，任意选择其 中一条边，固定下来，成为最熟悉的一条道路。 ３）对于带环图的这种情况，因为实际问题考虑 的是对于一个工厂的运输，自身运输没有任何实际 的意义。 例如：如果是一家超市，自身对于自身运 输也没有意义，所以不予考虑。 具有重边或有环的图都可以转化为简单图应 对出行问题，因此复杂网络图可以转化为简单图， 用以讨论相应的出行问题。 由于在具有 ｎ 个顶点的 简单图中，Ｋｎ 图结构最复杂，所以只要解决了 Ｋｎ 图 的出行问题，其他的简单图的出行问题将会迎刃而 解。 对于非 Ｋｎ 的 ｎ 个顶点的简单图，因为它们是 Ｋｎ 的子图，所以可以通过加边，使其成为 Ｋｎ 图，只 需将新加边的权值定义为 ０，采用本文的方法，完全 可以解决出行问题。 基于以上的讨论，只需解决具 有 Ｋｎ 图这样的交通网络的出行问题，因此本文只研 究 Ｋｎ 图。 现有 ｎ 个城市，任意两个城市均由交通道路连 接。 一位出行者要从自己所居住的城市去其他 ｎ－１ 个城市办事情，要求到达其他任意两个城市后再回 到自己所居住的城市，现在的问题是：如何找到以 ３ 个城市为三角形经济圈的一个出行方案。 首先建立一个网络模型，构建其关联矩阵。 由 于关联矩阵是一个 ０－１ 矩阵，信息提取中的任一个 形式背景可视为一个 ０－１ 矩阵，因此依据形式背景 的特殊性，建立概念格信息提取方法，进而找到人 们所需的最适合出行方案。 ２．１ 问题的提出 在不同城市间构建现代化交通网络，实现城市 间交通一体化，将会极大方便交通出行。 问题是： 如何在众多出行方案中选取合适的方案，成为人们 出行前需要解决的问题。 交通运输网络错综复杂， 很难给人们带来直接帮助，需要对交通运输网络进 行简化和直观化，得到一个简化的网络。 若出行者 需要计算出自己所居住的城市和其他任意两个城 市的距离和，即第 １ 节定义 ９ 中的基最小圈，判断走 哪个基最小圈距离和最短时，探究交通网络 Ｋｎ图模 型中的最小经济圈所需出行的路径距离就变得有 意义了。 ２．２ 模型的条件 设有 ｎ 个城市，每个城市看作一个顶点，两个城 市之间有路可达时，用一条线相连接，建立城市网 络图。 图中顶点用 ｖ１ ，ｖ２ ，…，ｖｎ 表示，组成集合 Ｖ ＝ ｛ｖ１ ，ｖ２ ，…，ｖｎ ｝。 网络图中 ｖｉ，ｖｊ 之间有路径可达，记 相连接的边为 ｅｉｊ，将此交通网络图记为 Ｇ ＝ （Ｖ，Ｅ）， 得 Ｇ 为一个有限无向图。 出行者从给定的一个顶 点城市 ｖ１ 出发去办事，要求路径中必须经过两个顶 点城市（除去给定城市顶点以外的其他任意两个顶 点城市），再返回到出发城市顶点 ｖ１ 。 由于出行者 走的道路为一个三角形，现在的问题是要选择一个 三角形在距离和花费的时间都少的三角形作为出 行者的最终出行方案，这就需要找到所有可能的出 行方法，换句话说，出行者需要出行前找到所有需 要走过的路径和出行方案，以便从中选择最佳方 案， 这些方案对决策者综合路径距离、时间、花费决 策时有重要的意义，可以帮助其更加直观、快速地 做决定，节约决策时间。 ２．３ 问题的分析 交通城市之间的无向图 Ｇ 进行转化后是顶点 为 ｎ 的完全图，记 Ｇ 为 Ｋｎ 图。 因 Ｋｎ 图对应的关联 矩阵满足二元拟阵 Ｍ，知定义 ７ 的含圈基满足定义 ３ 的拟阵 Ｍ，即实际生活中人们出行方案里的最小 三角形圈。 于是在 Ｋｎ 图的二元拟阵的标准矩阵表 示如下：在对应组成基本圈的三条边下标记 １，没有 组成基本圈的边下标记 ０，然后把得到的矩阵作为 含 ０ 和 １ 的形式背景。 在上面进行概念格的探索和 证明时发现，在 Ｋｎ 图中将二元拟阵中的基本圈即定 义 ９ 的基最小圈，作为对象，每两个顶点之间相连的 边作为属性，建立形式背景，找寻概念会遵循一定 的数学规律，运用此规律进行建格，速度很快。 ２．４ 模型的解决 ２．４．１ Ｋｎ 图的建格模型 根据定义 ３ 给出 Ｋｎ 图的标准矩阵表示。 当顶 点 ｎ ＝ ３ 时，根据引理 １ 的公式得边数为 ３，含圈基的 个数为 ｎ－１ ＝ ２，与其中一个顶点相连接构成的基最 第 ３ 期 毛华，等：利用二元拟阵 Ｋｎ 图的一种建格方法 ·３３５·