Word Table

术语	翻译	术语	翻译	术语	翻译
isolated	孤立的	pendant	悬挂的	in-degree	入度
out-degree	出度	bipartite graphs	二分图	sparse	稀疏的
isomorphism	同构	incidence matrix	关联矩阵	invariant	不变量
cut vertices	割点	cut edge	割边	homeomorphic	同态
planar graph	平面图	chromatic number	染色数

Graphs and Graph Models

A graph \(G=(V,E)\) consists of \(V\) ,a nonempty set of vertices (or nodes) and \(E\) ,a set of edges. Each edge has either \(1\) or \(2\) vertices associated with it , called its endpoints.

A digraph \((V, E)\) consists of a nonempty set of vertices \(V\) and a set of directed edges \(E\). Each directed edge is associated with an ordered pair of vertices. The directed edge \((u, v)\) is said to start at \(u\) and end at \(v\).

Type	Edges	Multiple Edges	Loops
Simple graph	Undirected	No	No
Multigraph	Undirected	Yes	No
Pseudograph	Undirected	Yes	Yes
Simple directed graph	Directed	No	No
Directed multigraph	Directed	Yes	Yes
Mixed graph	Directed and undirected	Yes	Yes

Graph Terminology

The set of all neighbors of a vertex \(v\) of \(G=(V,E)\) , denoted by \(N(v)\) , is called the neighborhood of \(v\) . If \(A\) is a subset of \(V\) , we denote by \(N(A)\) the set of all vertices in \(G\) that are adjacent to at least one vertex in \(A\) , \(N(A)=\bigcup_{c\in A}N(v)\)

The degree of a vertex in an undirected graph is the number of edges incident with it, except that a loop at a vertex contributes twice to the degree of that vertex. The degree of the vertex v is denoted by \(\deg(v)\)

Graph Properties

Let \(G=(V,E)\) be an undirected graph with \(m\) edges, then

\[ 2m=\sum_{v\in V}\deg(v) \]

An undirected graph has an even number of vertices of odd degree.

In a graph with directed edges the in-degree of a vertex \(v\), denoted by \(\deg^−(v)\), is the number of edges with \(v\) as their terminal vertex. The out-degree of \(v\), denoted by \(deg^+(v)\), is the number of edges with \(v\) as their initial vertex.

Let \(G=(V,E)\) be a graph with directed edges, then

\[ \sum_{v\in V}\deg^-(v)=\sum_{v\in V}\deg^+(v)=|E| \]

\(K\)-Complete \(C\)-Cycle \(W\)-Wheels \(Q\)-Cube

Bipartite Graphs and Matchings

A simple graph \(G\) is called bipartite if its vertex set \(V\) can be partitioned into two disjoint set \(V_1\) and \(V_2\) such that every edge in the graph connects a vertex in \(V_1\) and a vertex in \(V_2\) , the pair \((V_1,V_2)\) is a bipartition of the vertex set \(V\) of \(G\)

A simple graph is bipartite if and only if it is possible to assign one of two different colors to each vertex of the graph so that no two adjacent vertices are assigned the same color.

A matching \(M\) in a simple graph \(G=(V,E)\) is a subset of the set \(E\) of edges of the graph such that no two edges are incident with the same vertex.

A matching \(M\) in a bipartite graph \(G=(V,E)\) with bipartition \((V_1,V_2)\) is a complete matching from \(V_1\) to \(V_2\) if every vertex in \(V_1\) is the endpoint of an edge in the matching, equivalently \(|M|=|V_1|\)

Hall’s Marriage Theorem

The bipartite graph \(G=(V,E)\) with bipartition \((V_1,V_2)\) has complete matching from \(V_1\) to \(V_2\) if and only if \(|N(A)|\geq|A|\) for all subsets \(A\) of \(V_1\)

Subgraphs

A subgraph of a graph \(G=(V,E)\) is a graph \(H=(W,F)\) ,where \(W\subseteq V\) and \(F\subseteq E\) A subgraph \(H\) of \(G\) is a proper subgraph of \(G\) if \(H\neq G\)

Let \(G=(V,E)\) be a simple graph, the subgraph induce by a subset \(W\) of the vertex set \(V\) is the graph \((W,F)\) , where the edges set \(F\) contains an edge in \(E\) if and only if both endpoints of this edge are in \(W\)

Graph Isomorphism

The simple graphs \(G_1=(V_1,E_1)\) and \(G_2=(V_2,E_2)\) are isomorphic if there exists a one-to-one and onto function \(f\) from \(V_1\) to \(V_2\) with the property that \(a\) and \(b\) are adjacent in \(G_1\) if and only if \(f(a)\) and \(f(b)\) are adjacent in \(G_2\) ,for all \(a\) and \(b\) in \(V_1\)

Connectivity

A path is a sequence of edges that begins at a vertex of a graph and travels from vertex to vertex along edges of the graph.

A path or circuit is simple if it does not contain the same edge more than once.

An undirected graph is called connected if there is a path between every pair of distinct vertices of the graph. We say that we disconnect a graph when we remove vertices or edges, or both, to produce a disconnected subgraph.

There is a simple path between every pair of distinct vertices of a connected undirected graph.

A connected component of a graph \(G\) is a connected subgraph of G that is not a proper subgraph of another connected subgraph of \(G\).

Cut Vertices

Sometimes the removal from a graph of a vertex and all incident edges produces a subgraph with more connected components. Such vertices are called cut vertices(or articulation points).

Connected graphs without cut vertices are called nonseparable graphs

The vertex connectivity of a noncomplete graph \(G\) , denoted by \(\kappa(G)\) the minimum number of vertices that can be removed to disconnect a graph.

A graph is k-connected (or k-vertex-connected), if \(\kappa(G)\geq k\)

The edge connectivity of a graph \(G\) , denoted by \(\lambda(G)\) is the minimum number of edges in an edge cut of \(G\)

An inequality for vertex connectivity and edge connectivity \(\kappa(G)\leq\lambda(G)\leq\min_{v\in V}\deg(v)\)

Connectedness in Digraphs

A directed graph is strongly connected if there is a path from \(a\) to \(b\) and from \(b\) to \(a\) whenever \(a\) and \(b\) are vertices in the graph.

A directed graph is weakly connected if there is a path between every two vertices in the underlying undirected graph.

The strongly connected components of \(G\) is the subgraphs that are strongly connected but not contained in larger strongly connected subgraphs.

Euler Paths and Circuits

A Euler circuit in a graph \(G\) is a simple circuit containing every edge of \(G\) . An Euler path in \(G\) is a simple path containing every edge of \(G\)

A connected multigraph with at least two vertices has an Euler circuit if and only if each of its vertices has even degree.

A connected multigraph has an Euler path but not an Euler circuit if and only if it has exactly two vertices of odd degree.

Hamilton Paths and Circuits

A simple path in a graph \(G\) that passes through every vertex exactly once is called a Hamilton path, and a simple circuit in a graph \(G\) that passes through every vertex exactly once is called a Hamilton circuit.

If \(G\) is a simple graph with n vertices with \(n\geq3\) such that the degree of every vertex in \(G\) is at least \(n/2\), then \(G\) has a Hamilton circuit.

If \(G\) is a simple graph with \(n\) vertices with \(n \geq 3\) such that \(\deg(u) + \deg(v) \geq n\) for every pair of nonadjacent vertices \(u\) and \(v\) in \(G\), then \(G\) has a Hamilton circuit.

Shortest-Path Problems

Graphs that have a number assigned to each edge are called weighted graphs.

Planar Graphs

A graph is called planar if it can be drawn in the plane without any edges crossing.

\[ 2e=\sum_{\text{all region R}}\deg(R)\geq3r \]

If \(G\) is a connected planar simple graph with \(e\) edges and \(v\) vertices, where \(v\geq3\), then \(e\leq 3v − 6\).

If a connected planar simple graph has \(e\) edges and \(v\) vertices with \(v\geq3\) and no circuits of length three, then \(e\leq 2v − 4\).

If \(G\) is a connected planar simple graph, then \(G\) has a vertex of degree not exceeding five.

Euler’s Formula

Let \(G\) be a connected planar simple graph with \(e\) edges and \(v\) vertices. Let \(r\) be the number of regions in a planar representation of \(G\). Then \(r=e-v+2\)

Kuratowski’s Theorem

A graph is nonplanar iif it contains a subgraph homeomorphic to \(K_{3,3}\) or \(K_5\)

Dual Graph

Each map in the plane can be represented by a graph, each region of the map is represented by a vertex. Edges connect two vertices if the vertices have a common border. The resulting graph is called the dual graph of the map.

The chromatic number of a graph is the least number of colors needed for a coloring of this graph. The chromatic number of a graph \(G\) is denoted by \(\chi(G)\).

the Four Color Theorem

The Chromatic number of a planar graph is no greater than four Any graph with chromatic number \(\geq5\) is not a planar graph