# 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)

## 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.

## Induced Subgraph#

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