离散数学之图2

Representing Graphs

Adjacency Lists

Way i: One way to represent a graph without multiple edges is to list all the edges of this graph.
Way ii: Another way to represent a graph with no multiple edges is to use adjacency lists, which specify the vertices that are adjacent to each vertex of the graph.

邻接列表是把一个点的所有邻接点都列出来

我们可以用链表或者hashmap嵌套数组的方式存储这张图。

Adjacency Matrices

邻接矩阵

Adjacency list VS. adjacency matrix

When a graph is sparse(这张图很稀疏，边少), it is usually preferable to use adjacency lists rather than an adjacency matrix to represent the graph.
- 如果这张图很稀疏，那么如果用邻接矩阵的话空间消耗很大
The adjacency matrix of a sparse graph is a sparse matrix, that is, a matrix with few nonzero entries, and there are special techniques for representing, and computing with, sparse matrices.
- 对于稀疏图，我们可以采用稀疏矩阵的方式，也就是只保留1，不保留0
Suppose that a simple graph is dense, we compare the complexity of determining whether the possible edge $(v_i , v_j)$ is present.
- For case of adjacency matrix, we only need to examine the $(i , j)$-th entry in the matrix;
- For case of adjacency list, we need to search the list of vertices adjacent to either $v_i$ or $v_j$ in $O(|V|)$.
- 如果要看这个有向图顶点的入度，那么需要扫遍所有的邻接表或者建立你邻接表

邻接矩阵的优缺点

邻接表的优缺点

Incidence Matrices 连接矩阵

邻接矩阵是点和点之间的关系。但是连接矩阵式点和边的关系

这个矩阵上，一列只存在两个1或者一个1，一行上可能存在多个1。因为列是边，一条边只可能链接两个顶点或者自环，如果是自环，那么只有一个1了。

这个矩阵也是很稀疏的，但是用它可以来构造邻接矩阵。

Random walk and Laplacian

Random Walk

分子在溶液当中做布朗运动，这个过程叫做马尔可夫随机过程。这个过程对于溶质分子来说是在一个连续的空间中做随机游走。现在我们要讲的是离散的马尔可夫链。

比如说我们网上冲浪，点击一个网页会有很多子页面出现，子子孙孙无穷尽也。这个就相当于一个web Graph,我们就在这张图中随机游走。

利用随机游走我们可以判断一个人是否为小偷。如果一个人在公交图上随机游走，那么他有很大嫌疑是一个小偷

假设x走到y的概率都已一样的，那么$P(y|x) = \frac{1}{d(x)}$ 。我们定义D是一个对角矩阵。 P就是一个概率转移矩阵。概率转移矩阵一行加起来的数值一定等于1

Combinatorial Lapacian 组合拉普拉斯

组合拉不拉斯矩阵，这个矩阵等于对角矩阵-邻接矩阵，(对角矩阵的元素就是这个顶点的度)

0一定是这个矩阵的特征值。每一行的元素加起来等于0(对于简单图来说) ，对应的特征向量就等于v0

这个拉普拉斯矩阵可以帮助我们正则化

Normalized Laplacian 标准化拉普拉斯

isomorphism of Graphs 图的同构

The simple graphs $G1 = (V1; E1) $and $G2 = (V2; E2) $are isomorphic if there exists a one to one and onto function f from $V1 $ to $V2$ with the property that a and b are adjacent in $ G1$ if and only if $ f (a)$ and $f (b)$ are adjacent in $ G2$, for all $a$ and $b$ in $V_1$. Such a function $f $is called an isomorphism.

When two simple graphs are isomorphic, there is a one-to-one correspondence between vertices of the two graphs that preserves the adjacency relationship.

同构，说明V1到V2之间存在一个一一对应的满射，也就是说如果我不看一个顶点的标签，只看边和顶点的结构，那么这两幅图其实是一样的简单图的同构关系是等价的。 G1和自己同构，同构具有传递性

下面，如果不看标签，那么G，H其实是一样的。所以G、H是同构的

利用函数来找出一对一的关系，是很难的。我们如何进行判断？我们要看图中的顶点是否有相同的顶点数，相同的边数，相同顶点的度。

又比如说这幅图：我们可以去掉一些同构的顶点，判断剩下来的顶点是否同构。像下面这种，去掉四个顶点后发现不是同构的。

有没有更有效地方法判断是否同构呢？也就是说，我们通过画两个图的邻接矩阵，然后通过行列变换，一定能把他们化成一个矩阵。比如下图的 $A_G$和$A_H$ 它们是同构的

如果是有向图，怎么判断是否同构？

The same number of vertices;
The same number of edges;
The same degree for the same vertex.
The path and distance between vertices

我们列出每一个点的入度和出度。如果每个两个图都能找到一一对应的入度和出度的顶点，我们就说这两张图是同构的

$Degree^-$- u	$Degree^+$-u	$Degree^-$- v	$Degree^+$-v
2	1	2	0	1
2	3	1	3	2
1	3	2	1	3
2	0	2	3	4

我们发现节点都是能一一对应的，说明这两个图是同构的

Connectivity(Vertex&Edge)

首先我们要分清楚 Walk, Trail, Circuit, Path ,和Cycle的区别

walk就是想怎么走就怎么走，每条边每个顶点都是可以重复的。

Trail就是顶点可以重复，但是边是不能重复的

Circuit就是封闭的Trail，也就是说Circuit也是可以重复顶点但是不能重复边

Path就是既不可以重复顶点、又不能重复边的

Close 就是封闭的Path，即不能重复顶点也不能重复边

1代表可重复，0代表不可重复	Vertex	Edge
Walk	1	1
Trail	1	0
Circuit(Closed Trail)	1	0
Path	0	0
Cycle(Closed Path)	0	0

Paths

Paths in undirected graphs

Let n be a nonnegative integer and G a directed graph. A path of length $n$ from $u$ to $v$ in G is a sequence of $n$ edges $e1,e_2,e_3,e_4,e_n$ of G such that $e_i$ is associated with $(x{i-1},x_i)$for $i = 1, 2,…, n$ where $x_0 = u$ and $x_n = v$
When there are no multiple edges in the directed graph, this path is denoted by its vertex sequence$ x_0, x_1, x_2, … x_n$ A path of length greater than zero that begins and ends at the same vertex is called a circuit or cycle.

A path or circuit is called simple if it does not contain the same edge more than once. 一个simple circuit除了顶点可以重复，但是边是不能重复的

In the simple graph, a， d， c， f ， e is a simple path of length 4, because {a，d}， {d， c} , {c,f} and {f , e} are all edges.

However $ d, e, c, a $is not a path,b ecause {e,c} is not an edge.
Note that $b, c, f , e, b$ is a circuit of length 4 because {b,c}, {c, f }, {f ,e}, and {e,g} are edges, and this path begins and ends at b.
The path $a, b, e, d, a, b$, which is of length 5, is not simple because it contains the edge {a,b} twice.

Paths in directed graphs

Let n be a nonnegative integer and G an undirected graph. A pathof length n from u to v in G is a sequence of n edges e $e1,e_2,e_3,e_4,e_n$ of G for which there exists a sequence $x_0 = u, x_1 … x{n-1}, xn = v$ of vertices such that ei has, for $i = 1….,n $ the endpoints$ x{i-1} $and $xi$ .
When the graph is simple, we denote this path by its vertex sequence $x_0,x_1,…x_n $(because listing these vertices uniquely determines the path).
The path is a circuit if it begins and ends at the same vertex, that is, if $u = v$, and has length greater than zero. The path or circuit is said to pass through the vertices$ x_1,x_2,…x{n-1} $or traverse the edges $e_1….. e_n$
A path or circuit is simple if it does not contain the same edge more than once.

Example:

Paths in acquaintanceship graphs
In an acquaintanceship graph there is a path between two people if there is a chain of people linking these people, where two people adjacent in the chain know one another.
Paths in collaboration graphs
In a collaboration graph, two people a and b are connected by a path when there is a sequence of people starting with a and ending with b such that the endpoints of each edge in the path are people who have collaborated.

Connectedness in undirected graphs 无向连通图

无向图中如果任意两个顶点都有一条path的话，那么这个无向图就是连通的

An undirected graph is called connected if there is a path between every pair of distinct vertices of the graph.
An undirected graph that is not connected is called disconnected.
The first graph is connected, because for every pair of distinct vertices there is a path between them.
However, the second graph is not connected. For instance, there is no path in the graph between vertices a and d.

性质：

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. 连通分量是最大的连通子图。

That is, a connected component of a graph G is a maximal connected subgraph of G.

The graph H is the union of three disjoint connected subgraphs $H1,H2,H3$These three subgraphs are the connected components of H.

连通分量

Connected components of call graphs

How Connected is a Graph?

Network robustness

robustness(鲁棒性)即网络遭受到攻击的时候仍然能保持连通的能力

Motivations

In a phone call network, dense and frequent calls among users in the network reduce the likelihood of churn.
In IP networks, service providers therefore aim to monitor,manage and optimize their networks to keep their networks robust. 路由器相互之间转发数据包，如果区域之间只有一个路由，那么路由收到攻击的时候网络就会宕掉
In social platforms, some external or internal events may be detected from the burst of user interaction networks. 根据网络链接的状况，判断是否有事情发生

Existing measurements 测量方法

Node connectivity and edge connectivity
Cheeger ratio, vertex expansion, and edge expansion
Algebraic connectivity and R-energy

Cut and bridge

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). Analogously, an edge
whose removal produces a graph with more connected components than in the original graph is called a cut edge or bridge. Note that not all graphs have cut vertices, e.g., $ K_n $for$n \geq 3.$

比如这张图，我如果去掉 {c,e} 这座桥，那么两个子图就不再连通，所以这张图的 robustness就比较差

鲁棒性最好的就是完全图

Connectivity

Expander robustness

Edge boundary 和 Vertex boundary

Laplacian robustness

对于拉普拉斯矩阵，我们去度量它的特征值的方差。方差越大，那么说明顶点之间相连的状况相差很大。方差等于0 ，那么说明每一个顶点都至少和另外n-1个顶点相连，也就是一个Click

我们不需要把特征值算出来，我们用下面的公式来，扫描一遍即可

Example of network robustness metrics

R-energy: application I

R-energy: application II

Connectedness in Directed Graphs

Strongly and weakly connected 强连通和弱连通

强连通和弱连通只对于连通图来说，强连通是既能过去，又能回来；弱连通只能过去，无法回来

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.