5.1 Introduction to Graphs Types of Graphs 图的种类 Undirected Graphs 无向图 Simple graph 简单图
Multigraph 多重图
Pseudograph 伪图
13
2018/10/27
5.1 Introduction to Graphs
Chapter 5
graph theory
图论——计算机问题求解的描述工具
抽象 求解
实际问题
数学模型
求解算法（算法）
用大量数据验证
测试
编程实现
图论是离散数学的分支： 图(graph)： 是一个离散集和某些两元素子集的集合。 数学形象是：纸上画几个顶点，把其中一些点用 曲线段或直线连起来。图显示的是点与点之间的二元 关系。
如何才能在所有桥都恰巧只走一遍的前提下，回到原出发点?
桥所连接的地区 视为点 A A
C
C D B
D
B
每一座桥视为一 条线
求从图中任一点出发，通过每条边一次，最后回到起点。
如果通奇数座桥的地方不止两个，那麽 满足要求的路线便不存在了。 如果只有两个地方通奇数座桥，则可从 其中一地出发可找到经过所有桥的路线。 若没有一个地方通奇数座桥，则从任何 一地出发，所求的路线都能实现。
A multigraph allows multiple edges for two vertices.多重图允许
顶点对之间有多重边
A pseudograph is a multigraph which permits loops.伪图也是多
重图，它可以存在环。
For example,
b c
b c
b c a d
5.1 Introduction to Graphs
Directed Graph: In a directed graph有向图 G = (V, E) the edges are ordered pairs （有序对）of (not necessarily distinct) vertices.有向图(V,E)是由非空顶点集V、边集E所组成的，边V中
其后，图论在现代数学、计算机科学、工程技术、优 化管理等领域有大用而得以大力发展。
莱昂哈德· 欧拉(Leonhard Euler，
1707.4.5~1783.9.18) 历史上最伟大的两位数 学家之一（另一位是高斯）。欧拉出生于瑞士 ，他是一位数学神童。作为数学教授，他先后 任教于圣彼得堡(1727-1741)和柏林，尔后再 返圣彼得堡(1766)。 欧拉的离世也很特别：据说当时正是下午 茶时间，正在逗孙儿玩的时候，被一块蛋糕卡 在喉头窒息而死。 欧拉是第一个使用“函数”一词来描述包 含各种参数的表达式的人，例如：y = F(x) (函 数的定义由莱布尼兹在1694年给出)。欧拉是 有史以来最多产的数学家，他的全集共计75卷 。欧拉实际上支配了18世纪的数学，对于当时 新发明的微积分，他推导出了很多结果。 在他生命的最后7年中，欧拉的双目完全 失明，尽管如此，他还是以惊人的速度产出了 生平一半的著作。小行星欧拉2002是为了纪 念欧拉而命名的。
如何才能在所有桥都恰巧只走一遍的前提下，回到原出发点?
不少数学家都尝试去解析这个事例。而这些解析 ，最后发展成为了数学中的图论。 莱昂哈德· 欧拉(Leonhard Euler)在1736年圆 满地解决了这一问题，证明这种方法并不存在。 他在圣彼得堡科学院发表了图论史上第一篇重要 文献。欧拉把实际的问题抽象简化为平面上的点与 线组合，每一座桥视为一条线，桥所连接的地区视 为点。这样若从某点出发后最后再回到这点，则这 一点的线数必须是偶数。
莱昂哈德· 欧拉
Konisberg七桥问题(Euler问题) 柯尼斯堡七桥问题是图论中的著名问题。
这个问题是基于一个现实生活中的事例:位于当 时东普鲁士柯尼斯堡(今日俄罗斯加里宁格勒)有一条 河，河中心有两个小岛。小岛与河的两岸有七条桥 连接。如何才能在所有桥都恰巧只走一遍的前提下 ，回到原出发点？
a
14 2018/10/27
d
a
d
5.1 Introduction to Graphs
The relations of different undirected graphs 各种无向图之间的关系
Pseudographs 伪图
Multigraphs 多重图
Simple Graphs 简单图
15
2018/10/27
【Definition】 A simple graph G=(V,E) consists of vertices, V, and edges, E, connecting distinct elements of V.简单图G=(V,E)是
由非空顶点集V和边集E所组成的，V的不同元素的无序对称为边。 - no loops 没环 - can‘t have multiple edges joining vertices 两个顶点间最多只 有一条边
为什么要学习图论？ 可以采用图论的成果和方法；
最重要的是：可以培养我们思考问题和 解决问题的能力。
图论诞生和孕育于民间游戏。 创生：1736年 瑞士数学家欧拉——图论之父；
进展：1936年，匈牙利数学家寇尼希(Konig)发表名 著《有限图和无限图理论》； 1930年，波兰数学家库拉托父斯基 (Kulatowsky)证明了平面图可以画在平面上；
元素的有序对。允许有环(即相同元素的有序对)，但不允许在两个 顶点之间有同向的多重边。
In a directed multigraph 有向多重图G = (V, E) the edges are ordered pairs of (not necessarily distinct) vertices, and in addition there may be multiple edges. 有向多重图
CHAPTER 5
5.1 5.2
Graphs
Introduction to Graphs 图的概述 Graph Terminology 图的术语
5.3 Representing Graphs and Graph Isomorphism图 的表示和图的同构 5.4 5.5 5.6 5.7
4
Connectivity 连通性 Euler and Hamilton Paths 欧拉通路和哈密顿通路 Pg 平面图与着色 Trees 树