网络理论是21世纪最令人兴奋和最具活力的科学领域之一。

网络无处不在, 从提供我们的身体动力的代谢产物到社交网络, 都塑造着我们的生活。

本模块旨在介绍网络背后的理论，

我们将图论作为语言的基础。

了解网络拓扑结构，还将继续了解不同的网络属性和模型，

我们谈论无标度网络，令人惊讶的小型语音现象

和生物网络。

这些本质上都是数学，

还将在提示中看到，这里回忆起的所有概念都出现在现实生活中。

此外，本模块中介绍的符号将使我们能够以一致的方式

讨论整个课程中遇到的各种网络。

用于建模网络的基本数学概念是图。那么让我们看看，图是什么？

看这张图片。 看到了什么？

通过一组点来连接它们，它们是图。

图代表离散数学的关键概念，形式上这些点称为图顶点或网络节点，

它们之间的链接称为边。

因此，图G被定义为由V或 V(G) 表示的一组顶点，

以及由E或 E(G) 表示的边集。

图形易于从图片中绘制和理解, 易于通过计算机程序处理。

如果两个顶点由边连接，则称为相邻或邻居。

顶点u和v之间的边由{u，v}或短uv表示。

因此，可以通过列出顶点和边来描述图形，如此处所写，或者使用漂亮的图片。

你更喜欢哪一个？

边缘是一对。 有向边是有序对。

它表示为（v1，v2），而无向边是没有方向的无序对

表示为{v1，v2}。

更多术语。

n个顶点是相同顶点的图的边缘称为环。

如果该顶点是其末端之一，则边缘与顶点一起入射。 那么让我们看看图G1。

v2和v3是相邻。

e2与v2一起，e6是环。

我们遇到的图形或网络可以根据它们的边缘样式分为两大类：

有向图和无向图。

无向图由一组非空的顶点组成，由V和E表示，一组无向边。

有向图是一组顶点V和一组有向边。

例如，G1是无向图，而G2是有向图。在生物学，

转录调控网络和代谢网络通常是更放松的有向图。

例如，在转录调控网络节点中

代表具有表示它们之间相互作用的边缘的基因，

这将是有向图，因为如果基因A调节基因B，则存在自然方向

与从A开始并在B结束的相应节点之间的边缘相关联。

而蛋白质交互网络通常被建模为无向图，

其中节点代表蛋白质和边缘代表互动。

稍后在本单元和其他模块中，我们将更多地讨论这些网络及其属性。

通过描述性名称引用一些基本特殊图是一种习惯。

我们将回顾最着名的一些。 第一个是循环图。 长度为n的循环图是图，

n个顶点以n个边缘以循环方式连接。

顶点数应该多于三个。

由Cn表示的环，其中n是顶点的数量，或者它们可以是边数，因为它们是相等的。

下一个是图形路径。 长度n的路径看起来像一条中间有结的线。

它有n + 1个顶点连接，因此有n个边。

正如其名称所示，下一个是n个顶点上的完整图形

所有对形成边缘。 节点数应该多于一个称为完整图。

二分图是具有两个部分的图形，边缘将节点从一个部分连接到另一个部分。

完全的二分图

C(m,n) 在两个部分中有m + n个顶点，并且边的连接

来自不同部分的所有 m,n 对。最后两个图形类是轮子和n个立方体。

Wn表示将新的单个顶点连接到环Cn的所有顶点而形成的图。

我们看到的最后一种图是n立方体或超立方体。

它由Qn显示，是一个图形，其顶点是 2^n 二进制字符串，

当且仅当字符串恰好在一个坐标中不同时，两个顶点相邻。

图G中的顶点V的程度是G之间入射的边的数量。

如果图的所有顶点具有相同的度数d，则该图是d-正则的。

对于有向图，

我们可以改进我们的定义并将其分为两个：度数和出度。

在度数中，v是终点顶点的边数，

出度是v为初始顶点的边数。

如果以自然数序列写出图的顶点度数

然后我们度序列或图的分数。

在抽象图中，它们的顶点通常没有名称，所以我们必须以某种方式对它们的度序进行排序。

特定顺序并不重要。

如果知道图的度序列，那么您可以对图中的边数进行说明吗？

可以证明，简单无向图中的边数是其度序列之和的两倍。

握手定理可用于确定给定序列是否是图。

为什么序列1 2 3 4不能是图的度序列？

是的，总和不是偶数，因此是不可能的。