Discrete Mathematics

七桥问题


欧拉图

通过图(无向图或有向图)中所有边且每边仅通过一次通路称为欧拉通路,相应的回路称为欧拉回路。具有欧拉回路的图称为欧拉图(Euler Graph),具有欧拉通路而无欧拉回路的图称为半欧拉图。

  1. 无向连通图G是欧拉图,当且仅当G不含奇数度结点(G的所有结点度数为偶数);
  2. 无向连通图G含有欧拉通路,当且仅当G有零个或两个奇数度的结点;
  3. 有向连通图D是欧拉图,当且仅当该图为连通图且D中每个结点的入度=出度
  4. 有向连通图D含有欧拉通路,当且仅当该图为连通图且D中除两个结点外,其余每个结点的入度=出度,且此两点满足deg-(u)-deg+(v)=±1。(起始点s的入度=出度-1,结束点t的出度=入度-1 或两个点的入度=出度)
  5. 一个非平凡连通图是欧拉图当且仅当它的每条边属于奇数个环。
  6. 如果图G是欧拉图且 H = G - uv,则H有奇数个u,v-迹仅在最后访问v;同时,在这一序列的u,v-迹中,不是路径的迹的条数是偶数。

哈密顿图

通过图G的每个结点一次,且仅一次的通路(回路),就是哈密顿通路(回路). 存在哈密顿回路的图就是哈密顿图·

哈密顿图的充分条件和必要条件

  1. 在无向简单图G=中½V½³3,任意不同结点,则G是哈密顿图.(充分条件,定理4)
  2. 有向完全图D=;,若 ,则图D是哈密顿图. (充分条件,定理5推论)
  3. 设无向图G=,”V1ÌV,则P(G-V1)£½V1½(必要条件,定理3)

握手定理

设G=为任意无向图,V={v1,v2,…,vn},|E|=m,则所有顶点的度数和为2m


康托定理

  1. 闭区间上的连续实函数是一致连续的。
  2. 一个集合本身的势严格小于其幂集的势。
  3. 如果一个全序集是可列集,且是稠密的,无最大和最小值的,则它一定和有理数集序同构。

Reference :

  1. 欧拉图
  2. 哈密顿图
  3. 七桥问题
  4. 握手定理
  5. 康托定理