10/14/2022 1 离散数学 图论是现今离散数学的一个重要的分支，它较早的起源往往来自于一些不相关联的数学问题.例如十八世纪时一个著名的哥尼斯堡七桥问题.对于这个有趣的问题,Euler在写于1736年的一篇论文中给出了第一个完整的解答,他的这篇论文开创了后来称为位置几何学这个图论新分支的研究方向.10/14/2022 2 离散数学哥尼斯堡七桥问题10/14/2022 3 离散数学一、基本图类与相关概念则则AA&B B = (1, 3), (1, 4), (2, 3), (2, 4)= (1, 3), (1, 4), (2, 3), (2, 4)，11、无向图、无向图无序积：无序积：设设AA,BB是两个集合，称是两个集合，称aa, , bb| | aaAA bbBB 为为AA与与BB的无序积，记作的无序积，记作AA&BB。 习惯上记习惯上记aa, , bb为为(aa, , bb)，有序对记为有序对记为。无论无论aa, , bb取值如何，恒有取值如何，恒有(aa, , bb) = () = (bb, , aa)AA&A A = (1, 1), (1, 2), (2, 2)= (1,
