双语离散数学复习 para.6 图论

双语离散数学复习 para.6 图论思维导图。该导图介绍了graph的the definition of the graph等。

para.6 graph theory

• 1.graph
  • the definition of the graph
    • vertices(nodes)
    • edge
  • symple and multi graph
    • there's no loop(?)
    • no multiedge
  • degree
    • loop degree ==2
    • isolated
    • some therothem
      • 1.hand shaking therothem(deg(\sum$v_i$))==2e
      • 2.even number of vertices of odd degree
      • 3. (for digraph)deg+=deg-
    • degree of digraph
      • deg-()(v is the terminal)
      • deg+()(v is the initial)
  • directed graph
    • symple digraph
    • multidigraph
  • adjacent(邻接的)
    • 
  • regular(same degree)
  • complete graph
    • if n vertices denoted by k_n
    • stand for contains exactly one edge between each pair
    • is (n-1)regular
  • cycle
    • 2regular
  • wheel
    • add a vertices in c_n and turn tobe w_n
    • not regular
    • e(w_n)=2n
  • hypercube
    • Q_n
    • v=2^n
    • E=2^(n-1)/2
  • bipartite
    • 
    • use draw color to judge
    • complete bipartite graph K_m,n
      • v=(m+n)
      • e=nm
      • if n==m then it is regular
  • subgraph and union
  • reprecent the graph
    • adjacency list
      • (when less)
    • adjacency martices
      • when more
      • symmeyric or not?
  • isomorphism
    • one to one function and onto for two graphs
    • condition
      • deg;e;v
      • formulate
      • connectedness
      • circuit
  • connectivity
    • connectivity
      • path
        • no repetition v and e
      • trail
        • path + repetition v
      • walk
        • path +repetiton v and e
    • def :connect
      • connected component
      • cut edge
      • cut vertices
    • connectedness in digraph
      • strongly connected
      • weakly connected
    • way to count the num of path
      • A^n(n stand for the num of edge)
  • euler and hamilton path
    • euler therom(edge)
      • euler circuit
        • way to construct : using the subgraph
      • euler path
      • therom
        • circuit exist:every degree is even
        • path exist : two v have odd deg
    • hamilton therom(vertices)
      • hamilton path
      • hamilton circuit
        • dirac'theorem
          • if deg(vi)>n/2,there is
        • ore's theorem
          • every deg(u)+deg(v)>=n
  • shortest path(TSP)
    • weight martices
    • dijkstra's algorithm
      • form one to all
      • O(n^3)
    • floyd's algorithm
      • from all to all
      • O(n^3)
  • planar graphs
    • def:planar graphs
      • could draw in a plane
      • add edge one by one
      • eg K_4
    • euler formular
      • r=e-v+2
    • corollary 1
      • if G is a connected symple graph
      • v>=3
      • e<=3v-6
        • for: 2e=sum deg(r)>=3r
    • cor 2
      • if G is a connected symple graph,then it has a vertex of degree<=5
      • prof:against the cor1
    • cor3
      • if G is a connected symple graph ,with no circle of len 3
      • e<=2v-4
        • for: 2e=sum deg(r)>=4r
• tree
  • def of the tree
    • 
  • spanning tree
    • minimum spanning tree
      • cayley's therorem
        • k_n to n^(n-2)trees
        • n=v and m=e
      • prim's algorithm
        • O(V^2)
        • when the v is not much
        • based on v
      • Kruskal’s Algorithm
        • O(Elog(E))
        • when the edge is not much
        • based on edge
• 主题
• 主题
• 主题