离散数学图论
• 在图形中，只关心点与点之间是否有连线，而不关 心点具体代表哪些对象，也不关心连线的长短曲直， 这就是图的概念。
• 当研究的对象能被抽象为离散的元素集合和集合上 的二元关系时，用关系图表示和处理十分方便。
离散数学图论
§8.1图的基本概念
• 图论的起源可以追溯到1736年由瑞士数学家欧拉(Leonhard Euler， 1707-1783)撰写的一篇解决“哥尼斯堡七桥问题”的论文。
离散数学图论
欧拉简介
离散数学图论
图的基本概念
• 定义8.1图（Graph）G包括一个非空的对象的集合 V={v1,v2,…,vn}
与有限的V中两个对象构成的无序对构成的集合 E={e1,e2,…,em}，
前者称为结点集(Vertex set)，后者称为边集（Edge set）。
一般用G=<V，E>表示图。
第四篇图论
本篇包括第八章、第九 章。主要内容有图的基本理 论、欧拉图、哈密尔图、树 等。
离散数学图论
• 图论是一个古老而又年轻的数学分支，它诞生于18 世纪，它是用图的方法研究客观世界的一门科学， 为任何一个包含二元关系的系统提供了一个直观而 严谨的数学模型，因此物理系、化学、生物学、工 程科学、管理科学、计算机科学等各个领域都有图 论的足迹。
• 这是一种全新的思考方式，由此欧拉在他的论文中 提出了一个新的数学分支，即图论，因此，欧拉也 常常被图论学家称为图论之父。
离散数学图论
欧拉
• 欧拉是著作较多的著名数学家之一，曾发表了886篇论文，出版 了近90本书。在数学界的许多分支如数论、几何、组合数学等领 域的很多定理和公式都以欧拉命名的。
离散数学图论
哥尼斯堡七桥问题
• 把四块陆地用点来表示，桥用点与点连线表示。
离散数学图论
• 欧拉将问题转化为：任何一点出发，是否存在通过 每条边一次且仅一次又回到出发点的路？欧拉的结 论是不存在这样的路。显然，问题的结果并不重要， 最为重要的是欧拉解决这个问题的中间步骤，即抽 象为图的形式来分析这个问题 。
• 现在图论的主要分支有图论、超图理论、极值图论、 算法图论、网络图论和随机图论等。
离散数学图论
• 第三阶段是1936年以后。由于生产管理、军事、交 通运输、计算机和通讯网络等方面的大量问题的出 现，大大促进了图论的发展。现代电子计算机的出 现与广泛应用极大地促进了图论的发展和应用。
• 目前图论在物理、化学、运筹学、计算机科学、电 子学、信息论、控制论、网络理论、社会科学及经 济管理等几乎所有学科领域都有应用。。
离散数学图论
• 在计算机科学中计算机科学的核心之一就是算法的 设计与理论分析，而算法是以图论与组合数学为基 础；图论与组合数学关系也非常密切，已正式成为 计算机诸多分支中一种有力的基础工具。
• 因而，作为计算机专业人员，了解和掌握图论的基 本原理和方法是必要的。
离散数学图论
• 图论交叉地运用了拓扑学、群论和数论知识，其定 理证明难度高低不等，有的简单易懂，有的难于理 解，但其每一步证明都需要技巧，每一个定理都像 艺术平一样值得品味与推敲。
离散数学图论
• 例子：教材116页例8.1，例8.2
离散数学图论
• 根据图中边的方向，分为有向图、无向图。 • 边关联：有向边lk=(vi,vj)，其中vi称为起点，vj称为
终点。无论边是否有向，称lk与vi,vj相关联。 • 邻接：边lk=(vi,vj)，称vi,vj是邻接的点，若干条边关
联同一个结点，则称边是邻接的。 • 环：边lk=(vi,vj)， vi与vj是同一个点。 • 孤立点：不与任何点相邻接的点。
• 1847年德国的克希霍夫(G.R.Kirchoff)将树的概念 和理论应用于工程技术的电网络方程组的研究。
• 1857年英国的凯莱(A.Cayley)也独立地提出了树的 概念，并应用于有机化合物的分子结构的研究中。
离散数学图论
• 1936年匈牙利的数学家哥尼格(D.Konig) 发表了第 一部集图论二百年研究成果于一书的图论专著《有 限图与无限图理论》，这是现代图论发展的里程碑， 标志着图论作为一门独立学科。
• 因此，尽管本教材介绍的是较为基础的图论内容， 但阅读理解与完成习题是学习图论必不可少的步骤。
离散数学图论
• 图是人们日常生活中常见的一种信息载体，其突出 的特点是直观、形象。图论，顾名思义是运用数学 手段研究图的性质的理论，但这里的图不是平面坐 标系中的函数，而是由一些点和连接这些点的线组 成的结构 。
离散数学图论
定义图的子图
• 子图：设G=<V,E>， G’=<V’,E’>，若V’是V的子集，E’是E的子集， 则G’是G的子图。
• 真子图：若V’是V的子集，E’是E的真子集。 • 生成子图：V’=V，E’是E的子集。 • 举例说明一个图的子图。
离散数学图论
定义（n,m）图
• (n,m)图：由n个结点，m条边组成的图。 • 零图：m=0。即（n,0）图实上，G与G’互为补图。
离散数学图论
图的同构
• 看一下教材120页一个图的几个不同图形。 • 我们常将一个图和它的图形等同起来，但这是两个不同的概念，
离散数学图论
• 完全图：一个（n,m）图G，其n个结点中每个结点均与其它n-1个 结点相邻接，记为Kn。
• 无向完全图：m=n(n-1)/2 • 有向完全图：m=n(n-1) • 举例说明以上几种图。
离散数学图论
定义补图
• 设图G=<V,E>， G’=<V,E’>，若G’’=<V,E∪E’>是完全图，且 E∩E’=空集，则称G’是G的补图。
离散数学图论
图论的发展
• 图论的产生和发展经历了二百多年的历史，从1736年到19世纪中 叶是图论发展的第一阶段。
• 第二阶段大体是从19世纪中叶到1936年，主要研究一些游戏问题： 迷宫问题、博弈问题、棋盘上马的行走线路问题。
离散数学图论
• 一些图论中的著名问题如四色问题(1852年)和哈密 尔顿环游世界问题(1856年)也大量出现。同时出现 了以图为工具去解决其它领域中一些问题的成果。