画布 1
图论部分
  n 图的基本概念
    n 图的定义,无向图,有向图,简单图
      n 有序积: A×B={ <x,y> |x∈A∧y∈B} 有序对: <x,y>≠<y,x>
      n 无序积: A&B={ (x,y) |x∈A∧y∈B} 无序对: (x,y)=(y,x)
      定义 一个图是一个三元组<V,E,φ>，记作G,其中
      (1) V是一个非空的顶点集合，
      (2) E是边集合，EÍV&V(或V ́V), 并且是多重集合, 若EÍV&V，则G是无向图;若EÍV ́V，则G是有向图
          注意:1. 环对于顶点度的贡献是2
          2. 悬挂顶点的度为1
          3. 悬挂边: 与悬挂顶点关联的边
          4. 孤立顶点的度为0
      握手定理(图论基本定理)
          考点
    n 度,握手定理,度数列,可(简单)图化
        定理7.3:非负整数列d=(d1,d2,...,dn)是可图化的,
当且仅当d1+d2+...+dn=0(mod 2).
    n 图的同构
    n 简单图和多重图
    完全图 正则图
        正则图的最大度等于最小度
        peterson图--10 阶 3 正则图
    子图
      设图G=<V,E>, 图G'=<V',E'>
    图运算II
    名词解释
      圈(cycles)
      轮(wheels)
    鸽巢原理
  n 路与回路、连通性
    n 通路,回路,路径,圈,周长,围长
    n 极大通路法
      p121(6)(7)
    n 无向图的连通度性
      无向图的连通性
        u和v是连通的:结点u和v之间若存在通路, 记作u~v
          规定u~u.
          连通关系R={<u,v>| u,v ÎV且u~v}是V上的等价关系
        G是连通的:p(G)=1.(即G是平凡图或任意两结点都是连通的)
        距离
    n 二部图
      定理7.8 一个无向图G=<V,E>是二部图当且仅当G 中无奇圈.
    无向图的连通度
      点割集
      边割集
        割边(cut-edge)(桥)
      点连通度κ
        点连通度: 为了破坏连通性,至少需要删除κ个顶点
          G是k-连通的: κ(G)≥k
      边连通度λ
        边连通度: 为了破坏连通性,至少需要删除λ条边
          G是k-边连通的: λ(G)≥k
            G非连通的λ(G)=0
p(G)>1
      Whitney定理, 简单连通图κ,λ,δ之间的关系
        定理10: κ≤λ≤δ.
          引理1: 设E’是边割集,则p(G-E’)=p(G)+1.
        δ.最小度
        λ边连通度
        κ点连通度
        定理11 G是n(≥6)阶简单无向连通图,λ(G)<δ(G),则存在 图G*,它以G为生成子图, G*由完全图Kn1和Kn-n1,以及 它们之间的λ(G)条边组成, λ(G)+2≤n1≤|̈n/2|̂.
        定理14: n阶简单连通图的κ,λ,δ之间关系有且仅有3种 可能:
      2-连通, 2-边连通的充要条件
        定理15: 3阶以上无向简单连通图G是2点-连通图 ⇔ G中任意两个顶点共圈.
3阶以上无向简单连通图G是2-连通图 ⇔ G中任意两个顶点之间有两条以上独立路径.
          (⇐) 显然G是连通的,并且删除任何一个顶点不破坏 连通性, 所以κ≥2.
          (⇒) 分情况讨论: 在两个顶点之间有
(1) 1条路径--不可能
(2) 2条路径 (2a)独立: 成立
(2b)非独立: 不可能
(3) 3条路径 (3a) 3路径有1个公共交点: 不可能
(3b) 有2个交点: 同(2a) 有2条独立路径
(3c) 有3个以上交点: 产生2条独立路径
(4) 4条以上路径
        定理16: 3阶以上无向图G是2-边连通图⇔G中任意两 个顶点共简单回路.
3阶以上无向图G是2-边连通图⇔G中任意两 个顶点之间有两条以上边不交路径.
      块(block): 极大无割点连通子图 显然，若G是块,则κ≥2
      k-(边)连通
        定理: 3阶以上无向图G是k-点连通图⇔ G中任意两个顶点之间有k条以上独立路径。
        定理: 3阶以上无向图G是k-边连通图⇔ G中任意两个顶点之间有k条以上边不交路径。
      桥
        无向连通图G中边e是桥⇔G的任何圈都不经过e.
        无向连通图G中边e是桥⇔可以把V(G)划
分成V1与V2,使得从V1中任意顶点u到V2中任意顶 点v的路径都要经过e.
      结论
        2-连通图: κ≥2, 连通无割点
        2-边连通图: λ≥2, 连通无桥
        K2是块, 但不是2-(边)连通图
        2-连通图⊂2-边连通图
        n33, 2-连通图Û块
    有向图的连通性
      u到v的距离(或短程线): u到v长度最短的路径长度 (u 可达v)，记作d<u,v>。
      n 规定:若u不可达v, d<u,v>=∞.
      n 距离的性质:
d<u,v>>=0, d<u,u>=0，d<u,v>+d<v,w> ≥d<u,w>
      图的直径: D = max d < u, v > u,vÎV
      如果有向图D的基图是连通的,则称图D为弱连通的
      如果图G中的任何一对结点之间都是互相可达的, 则称图G是强连通的.
        定理7.21 有向图D是强连通的, 当且仅当D中存在至少包 含每个结点一次的回路.
          充分性:回路包含每个节点
必要性:每个节点都是强连通的,pi 是 vi 到 vi+1 的路,pn
是 vn 到 v1 的路,这 p1p2...pn 所围成的回路至少经过 G 在每一个节点
      对于所有u,v∈V(D),若u→v, u→v至少成立一个, D是单向连通的.
        定理7.22 图G单向连通当且仅当G中存在经过每个顶点至 少一次的路。
    连通图的性质
      在简单有向图中，具有强连通性质的极大子图， 称为强分图;
        定理 在有向图G=<V,E>中,它的每一个顶点位于且仅位 于一个强分图中.
      具有单向连通性质的极大子图，称为单 向分图;
      具有弱连通性质的极大子图，称为弱分图。