A directed graph (V, E) consists of a nonempty set V and a set of directed edges E.
The edge (u, v) in a directed graph starts at u and ends at u.
The edge (v, u) starts at v and ends at u.
The edges in an undirected graph have no direction.
Degree
Undirected
The degree of a vertex in an undirected graph is the number of edges connected with it except that a loop at a vertex contribute twice to the degree of that vertex.
Denoted by where v is a vertex.
Directed
In-Degree and Out-Degree
The in-degree of a vertex (u) in a directed graph is the number of edges that end at this vertex, denoted by .
The out-degree of a vertex in a directed graph is the number of edges that start at this vertex, denoted by
Handshaking Theorem
Theorem: For an undirected graph
Odd Degree Theorem
Theorem: An undirected graph has an even number of vertices of odd degree.
(奇度点个数偶数)
Theorem: In a directed graph
Some Special Simple Graphs
Complete Graphs
A complete graph is a simple graph in which there is an edge between each pair of distinct vertices, denoted by where n is the number of nodes in the graph.
Cycle
A cycle is a graph that contains n vertices and n edges denoted by where n is the number of nodes in the graph.
Wheel
A wheel is obtained by adding an additional vertex to the cycle , for n > 3, and connect this new vertex to each of the vertices in , by new edges.
Cube
A cube of dimension n is a simple graph of vertices, where each vertex represents a bit string of length n. Two vertices are adjacent if and only if they differ by one bit.
Complete Bipartite Graphs
A simple graph is called bipartite if its vertex set V can be partitioned into two disjoint set , and , such that every edge in the graph connects a vertex in , and a vertex in ,
and , are called a bipartite of the vertex set V of G.
Theorem
Theorem: A simple graph G = (V, E) is bipartite if and only if it ispossible to color each vertex with one of two colors so that noadiacent vertices have the same color.
Subgraphs and Proper Subgraphs
A subgraph H = (W, F) of graph G = (V, E) is made up of vertices and edges