Definition

• edge(arc), node(vertex)
• degree: # of adjecant nodes
  • simplegraph: no two edge connect the same pair
  • multigraph: edges connect same pair
  • loop: edge connect same vertex
    • add two degree
  • pseudograph: multigraph+loop
• directed, undirected
• Subgraph H(w,f) of G(v,e): w in v, f in e
• proper subgraph: H ≠ G
• induced subgraph: node를 뽑고 그 안의 모든 엣지 연결

Theorem

• 2E = SUM (degree(v))
• undirected graph has even # of (odd degree)
  • 2E = SUM(evendeg(v)) + SUM(odddeg(v))
• E = SUM(deg-(v)) = SUM(deg+(v))

Special Types of Graph

• complete graph Kn: v node, vC2 edge

• cycle Cn

• wheels Wn: Cn+ 중심 하나

• n-cubes Qn:

  

• Bipartite graph: 모든 엣지가 두 부분집합 연결

• complete bipartite Km,n: 집합의 모든 점이 다른 집합의 모든 점과 연결

Representing Graphs

• adjacent list

• adjacent matrix

• incidence matrix

  

Isomorphism (사상) G1(V1,E1) and G2(V2,E2) is isomorphic: for adjacent a,b in G1: f(a) and f(b) is adjacent in G2 이런 f를 isomorphism

• 찾는 방법은 어렵다.

Connectivity

• path u to v: {e1,e2,…,en}
• circuit: u=v
• connected: path exists between all u,v
  • strongly connected(digraph): for all u,v, exists a path(방향 고려)
  • weakly connected(digraph): 방향을 무시한 그래프가 connected
• counting paths with adjacency matrix A

  • number of length r path from vi to vj : A^r (i,j)

    

Euler Path, Circuit

• Euler Circuit: simple circuit contains every edge

  • 조건: all node have even degree

  • 찾기:

    

• Euler path: simple path contains every edge (한붓그리기)

  • 조건: exactly 2 node with odd degree

Hamilton Path, Circuit

• Hamilton Circuit: simple circuit contains every vertex only ONCE
• Hamilton Path: simple path contains every vertex only once
• Finding Hamilton Circuit
  • Dirac’s thm simple G, n≥3 vertices, all degree > n/2 →exists
  • Ore’s thm simple G: n≥3 vertices, for non-adj (u,v), deg(u)+deg(v) ≥n →exists
• traveling salesperson problem(TSP)
  • Hamilton circuit with smallest sum of weights