Algorithms Lecture 2: Graph concepts

This is University of Auckland Algorithm Lecture 2, today’s lecture is mainly about basic concepts of Graph, an integral part of graph. This is my notes:

Concepts#

  1. A graph G consists of two sets of V and E.

    • V is the set of vertices(nodes).
    • E is the set of edges. Each edge connects two vertices u an v in V.
  2. Not every vertex of a graph needs to have an edge attached(自环), not every pair of vertices needs to be connected by an edge.

  3. Use G(V, E) for the graph itself, or E(G) for the edges, or V(G) for the vertices.

  4. Adjacent: Two vertices u and v are connected by an edge, means adjacent.

  5. Labelled graph: label the vertices uniquely.
  6. The order of a graph G is the number of its vertices:|V(G)|.
  7. The size of a graph of the number of its edges:|E(G)|.

  8. We can mainly divide the graph into two types:

    1. Undirected graph
    2. Directed graph(Di-graph)

Undirected graph#

无向完全图:在无向图中,如果任意两个顶点之间都存在边,则称该图为无向完全图。n个顶点边数:

当一个图接近完全图时,则称它为稠密图(Dense Graph),而当一个图含有较少的边时,则称它为稀疏图(Sparse Graph)。

Directed graph#

有向完全图:在有向图中,如果任意两个顶点之间都存在方向互为相反的两条弧,则称该图为有向完全图。n个顶点边数:

Degree of vertex#

  • The number of edges is the sum of the degrees of all vertices divide by 2.
  • A neighbor v of u is an out-neighbour of u is there’s an arc from u to v.
  • A neighbor v of u is an in-neighbour of u is there’s an arc from v to u.

Degree of vertex

顶点$v_i$的度(Degree)是指在图中与$v_i$相关联的边的条数。对于有向图来说,有入度(In-degree)和出度(Out-degree)之分,有向图顶点的度等于该顶点的入度和出度之和

Walk#

Walk

Path#

Path

SubGraph#

Subgraph

这句话的意思是说,所有的顶点和边都属于图G的图称为G的子图。

Spanning Subgraph#

Spanning Subgraph

含有G的所有顶点的子图称为G的生成子图。

Induced Subgraph#

Induced Subgraph

如果图G的子图H满足边(u,v)在图H中当且仅当边(u,v)在图G中,即图H包含了图G中所有两个端点都在V(H)中的边,则称H是G的导出子图。

我的理解是:

  1. 首先导出子图要是个子图,即图H的边集和点集都应该是图G的子集。
  2. 图G中端点相连应该有的边,图H中都应该有。(即不能缺少相连的边!)

Is an Induced Subgraph

Not an Induced Subgraph