S1图的基本概念一、图、连通图、赋权图3.赋权图3.赋权图在实际问题中，常常遇到每条边对应一个数量指标的情况。例如，若用边表示线路（电线、公路、铁路、管道等）则往往要考虑它们的长度，或相应的运输价格等，这时，我们需为图的各边给出相应的数量指标，并称之为“权”。定义3-4（赋权图）：设图G=(V，E)，若为其每一边[v，v]相应地赋予一个数w，并称之为边[v，v,]的权，则称这种图为赋权图。相对于非赋权图，赋权图在图论的理论和应用方面有着重要的地位，赋权图中的边不仅表示图中各点之间的关联关系，而且同时表示出了各点之间的数量关系，所以赋权图被广泛应用于各领域的最优化问题。定义3-5（图的权）：图中各条边权的和称为图的权，记作W(G)=m. ko",11、一笔画问题
11 §1 图的基本概念 一、图、连通图、赋权图 3. 赋权图 二、一笔画问题 3. 赋权图 定义3-4（赋权图）： 在实际问题中，常常遇到每条边对应一个数量指标的情况。例如，若用边表示线 路（电线、公路、铁路、管道等），则往往要考虑它们的长度，或相应的运输价 格等，这时，我们需为图的各边给出相应的数量指标，并称之为“权”。 相对于非赋权图，赋权图在图论的理论和应用方面有着重要的地位，赋权图中的 边不仅表示图中各点之间的关联关系，而且同时表示出了各点之间的数量关系， 所以赋权图被广泛应用于各领域的最优化问题。 定义3-5（图的权）：图中各条边权的和称为图的权，记作 v v G ij i j W G w
S1图的基本概念S1 图的基本概念一、图、连通图、赋权图二、一笔画问题三、中国邮路问题四、子图和树12、一笔画问题
12 §1 图的基本概念 二、一笔画问题 §1 图的基本概念 一、图、连通图、赋权图 二、一笔画问题 三、中国邮路问题 四、子图和树
二、一笔画问题S1图的基本概念我们可以笔不离纸地连续画出该图，并且各边没有重复，即可以“一笔画画出该图，我们称这种图为可一笔画的。定义（可一笔画的图）：如果连通图有一条包括所有顶点，但各边只出现一次的路线，则称这个连通图为可一笔画的图。VVAVV's25V223欧拉不仅证明了哥尼斯堡问题是不可能一笔画回到原出发点的，而且还证明了哥13尼斯堡问题甚至不是可一笔画的。为了了解欧拉的结论，我们给出下列定义及定理。定义：欧拉链
13 欧拉不仅证明了哥尼斯堡问题是不可能一笔画回到原出发点的，而且还证明了哥 尼斯堡问题甚至不是可一笔画的。为了了解欧拉的结论，我们给出下列定义及定 理。 §1 图的基本概念 二、一笔画问题 定义：欧拉链 定义（可一笔画的图）： 我们可以笔不离纸地连续画出该图，并且各边没有重复，即可以“一笔画”画出该图，我们 称这种图为可一笔画的。 如果连通图有一条包括所有顶点 ，但各边只出现一次的路线，则 称这个连通图为可一笔画的图。 v3 v1 v4 v2 v5 v3 v1 v4 v2 v5
二、一笔画问题S1图的基本概念定义3-7（欧拉链）：经过且仅经过图中每条边一次的链称为欧拉链。定义3-8（欧拉圈）：经过且仅经过图中每条边一次的圈称为欧拉圈。定义3-8（欧拉图）：含有欧拉圈的图称为欧拉图。定理3-1（欧拉链的充要条件）：连通图含有欧拉链的充分必要条件是图中奇点的个数为0或2。定理3-2（欧拉链的充要条件）：连通图含有欧拉圈的充分必要条件是图中不存在奇点。哥尼斯堡人想走欧拉链的特点是过七座桥，且每经过图的所有边1857年，英国数学家哈密尔顿提出了一个与上座桥只能走过一且每条边只经过述问题密切相关的问题，即一个图是否存在这次，最后回到出一次，但对是否样一条路线，该路线经过所有顶点，且每个顶发点，这样的想经过所有顶点及点只经过一次？可以证明，这样的路线必定是一个圈，称为哈密尔顿圈。含有哈密尔顿圈的法是不可能实现通过各顶点的次14的。图称为哈密尔顿图。数没有限制。哈密尔顿图
14 §1 图的基本概念 二、一笔画问题 哈密尔顿图 定义3-7（欧拉链）：经过且仅经过图中每条边一次的链称为欧拉链。 定义3-8（欧拉圈）：经过且仅经过图中每条边一次的圈称为欧拉圈。 定理3-1（欧拉链的充要条件）： 连通图含有欧拉链的充分必要条 件是图中奇点的个数为0或2。 定理3-2（欧拉链的充要条件）： 连通图含有欧拉圈的充分必要条 件是图中不存在奇点。 定义3-8（欧拉图）：含有欧拉圈的图称为欧拉图。 1857年，英国数学家哈密尔顿提出了一个与上 述问题密切相关的问题，即一个图是否存在这 样一条路线，该路线经过所有顶点，且每个顶 点只经过一次？可以证明，这样的路线必定是 一个圈，称为哈密尔顿圈。含有哈密尔顿圈的 图称为哈密尔顿图。 哥尼斯堡人想走 过七座桥，且每 座桥只能走过一 次，最后回到出 发点，这样的想 法是不可能实现 的。 欧拉链的特点是 经过图的所有边， 且每条边只经过 一次，但对是否 经过所有顶点及 通过各顶点的次 数没有限制
二、一笔画问题S1图的基本概念(2)(1)(6)(5)(3)(4)哈密尔顿图，非欧拉图欧拉图，非哈密尔顿图（无奇点）（有奇点）既是欧拉图又是哈密尔顿图的图是存在的《参考消息》2010.10.26：瞬间解出“巡回售货员问题，蜜蜂大脑击败电脑”需要指出，我们已经知道欧拉图的判断准则英国《卫报》网站10.24报道。伦敦大学皇家霍洛即所有顶点均为偶点（或不存在奇点），但是尚没有一个哈密尔顿图的判断准则。然而，哈维学院的研究研究小组利用电脑控制的人造花朵密尔顿图是有一定实用价值的，如与其有密切测试蜜蜂的行为，发现大脑小如草籽的蜜蜂很快关系的“巡回售货员问题”，即找出一条包含所能够确定最短路线。目前电脑是通过穷比法来求有顶点的最短闭合路线（这里，城市为顶点，解的。该问题对于依赖于交通流、互联网、供应城市之间的距离为边的长度）。链的现代生活不无意义。15三、中国邮路问题
15 §1 图的基本概念 二、一笔画问题 三、中国邮路问题 (2) (1) (6) (3) (4) (5) 哈密尔顿图，非欧拉图 （有奇点） 欧拉图，非哈密尔顿图 （无奇点） 既是欧拉图又是哈密尔顿图的图是存在的 需要指出，我们已经知道欧拉图的判断准则， 即所有顶点均为偶点（或不存在奇点），但是 尚没有一个哈密尔顿图的判断准则。然而，哈 密尔顿图是有一定实用价值的，如与其有密切 关系的“巡回售货员问题”，即找出一条包含所 有顶点的最短闭合路线（这里，城市为顶点， 城市之间的距离为边的长度）。 《参考消息》2010.10.26：瞬间解出“巡回售货员问 题，蜜蜂大脑击败电脑” 英国《卫报》网站10.24报道。伦敦大学皇家霍洛 维学院的研究研究小组利用电脑控制的人造花朵 测试蜜蜂的行为，发现大脑小如草籽的蜜蜂很快 能够确定最短路线。目前电脑是通过穷比法来求 解的。该问题对于依赖于交通流、互联网、供应 链的现代生活不无意义