论欧拉图、哈密顿图的判定及应用.pdf

维普资讯 L 中国高新技术企业 论欧拉图、哈密顿图的判定及应用 文 ／伍庆成 t摘要l 图论在现实生活 中有着较为广泛的应用。欧拉 图、哈密顿图的判定3-法有 多种，主要应用于解决中 国邮路 问题 、旅行售货 员f,-,I题 、排座位f,-,I题 、判定 图是否可一笔画等 。 【关键词】 欧拉 图 哈密顿图 回路 应用 用 图形可描述现实世界 中许 多状态变化 。图形表达事物是现 2、用 定 理 来判 定 代科学技术 中的一种重要手段 。图形不仅形象直观 ，而且 可 以结合 定理 3 设 图G是具有 n个顶 点的无 向连通 图，如果 G 中任意 数据 。可 以数形结合便于计算 。因此 图论 内容是相 当现实和必需的 ， 两个不 同顶 点 的度数 之和大于等于 n，则 G具有 哈密顿 回路 ，即 G 欧拉 图、哈密顿 图在现实生活 中有着较为广泛 的应用 。 是哈密顿 图。 一 、 欧拉 图的判定方 法 容 易用定理 3判定 图 5为哈密顿 图。 1、用 欧拉 图的定义来 判 定 定理 3是判 断哈密顿 图的充分条件 ，即不满足定理条件时，也可 定义 1 经过 图G 的每条边一次且仅一次 的路径 ，称为欧拉路 能存在 哈密顿 回路 ，图G也可能是哈密顿 图。 径 ．经过 图G 的每条边一次且仅一次 的回路 ，称为欧拉 回路 。具有欧 哈密顿 图的判定 比欧拉 图要复杂 。 拉 回路 的图称为欧拉 图。 定理 4 设 图G=V。E是哈密顿 图，则对于 V 的任意一个非空 如下 图可用定义判定为欧拉 图 子集 S，若 以 ISI表示 S中元素 的数 目，G—S表示 G中删去了S中的 点以及这些点所关联的边后得 到的子图，则W(G—S)≤ lSI成立 。其 中WfG—S)是 G—S中连通分支数 。… 定理 4是哈密顿 图的必要条件 。用它可 以证 明某些 图不是 哈密 顿 图。 图 1 图 2 2、用定理来判 定 定理 1 一个无 向连通 图是欧拉 图的充分必要条件是 图中各点 的度数为偶数 。 图 1用定理 1判定 比较简单 。 图 6 图 7 定理 2 设 图G是有 向连通 图 ，图G是欧拉 图的充分必要条件 图 6中删去 v成为具有 2个连通分支 的图，图 7中删去 a，b成 是 图中每个顶 点的入度和 出度相等 。 为具有 3个连通分支 的图 ，即图 6和 图7都不是哈密顿 图。 如 图 3用定理 2可判定为欧拉 图。 三 、欧拉 图、哈密顿 图的应 用