graph-theory

• A graph is a simple graph if:
  • each edge connects two different vertices and
  • where no two edges connect the same pair of vertices.

简单图是一种没有自环和重复边的图。也就是说，在简单图中，每条边连接两个不同的点，且同一对顶点之间只有一条边。

• A multigraph is a graph that may have multiple edges connecting the same pair of vertices.
• If there are m different edges associated to the same unordered pair of vertices.

Multigraph（多重图）是一种有重复边的图。也就是说，在Multigraph中，两个顶点之间可以有多条边。
在图论中，Multiplicity（重数）指的是一条边在一个图中出现的次数。在简单图中，每条边的重数为1，而在Multigraph中，一条边的重数可以大于1。

• A loop is an edge that connects one vertex to itself.
• Graphs that may include loops, and possibly multiples edges connecting the same pair of vertices are called pseudo-graph.(伪图)

在图论中，Loop（自环）是一条连接同一个顶点的边。自环的两个端点是同一个顶点。在简单图中不存在自环，但在Multigraph中可以存在自环。自环的重数为自环的数量。

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

• 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

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

• A cycle is a graph that contains n vertices and n edges denoted by where n is the number of nodes in the graph.

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

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

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