下载掌阅APP，畅读海量书库
立即打开
图论是数学的一个分支，它以图为研究对象。图论中图的节点和边直接映射网络中的节点和节点之间的关系，用图论研究社交网络，可以清晰地表示社交网络中的节点（个体）和边（关系）。这种表示方式便于分析网络结构、节点的重要性和社区发现等问题。而且，图论中的算法（如最短路径算法、最大流算法、图分割算法等）可以有效地处理大规模社交网络的数据，揭示网络中的潜在模式和规律。此外，图论方法能够量化网络特性，如中心性、连通性和聚集系数等，为社交网络的动态分析和预测提供了坚实基础。因此，图论应用在社交网络研究中不仅提升了数据分析的效率，还增强了对复杂网络行为的理解和预测能力。
一个图 G 由两部分组成，一部分是叫作 节点 （也称为顶点）的元素的有限集合 V ={ v 1 ， v 2 ， v 3 ，…， v n }，另外一部分是叫作 边 的不同节点对的有限集合 E ={ e 1 ， e 2 ， e 3 ，…， e m }。我们用 G =（ V ， E ）来表示图，其中 V 是节点集， E 是边集。集合 V 中的节点的个数 n 叫作图 G 的 阶 。如果 a ={ x ， y }={ y ， x }是 G 的一条边，就称 a 连接 x 和 y ，且 x 和 y 是 邻接的 ；也称 x 和 a 、 y 和 a 是 关联的 。由定义，图是一个抽象的数学实体，但如果把它用平面上的图形来表示的话，也可以认为图是一个几何实体。我们用不同的点表示节点，两个节点之间用一条简单的曲线来连接，当且仅当这两个节点确定图 G 的一条边 a 。我们称这样的一条曲线为 边曲线 ，用 a 来标记。画图时必须注意：一条边曲线 a 通过一个节点 x ，仅当 x 是边 a 的一个节点，否则我们的图形将含糊不清。
如果改变一下图的定义，允许某些节点对构成的边多于一条，则这样的图叫作 多重图 。在多重图 G =（ V ， E ）中， E 是一个多重集。边 a ={ x ， y }在 E 中出现的次数，叫作它的 重数 ，用 m { x ， y }表示。更一般地，若允许图中有环，即允许有形如{ x ， x }的边，使一个节点自邻接，则这样的图叫作 一般图 。
一个 n 阶图叫作 完全图 ，如果它的任意一对不同节点都构成一条边。或者说，在一个完全图中，任意一个节点都与其他所有节点邻接。一个 n 阶完全图有 n （ n -1）/2条边，并记为 K n 。
图1.7给出了完全图 K 1 ， K 2 ， K 3 ， K 4 ， K 5 的图形。不难看出，在任意一个 K 5 的图形中，至少有两条边相交于一个不是节点的点。
图1.7 完全图
一个一般图 G 是平面的，如果能在平面上画出它的图形，使其任意两条边仅在节点处相交。这样的图形也叫作 平面图 ，或叫作图 G 的 平面图表示 。在图1.7中， K 1 ， K 2 ， K 3 ， K 4 的图形是平面的，因此，这些图都是平面图， K 5 的图形不是平面的，因为它有两条边相交于一个非节点的点。
在一般图 G 中，与节点 x 相关联的边的数目叫作该节点的 度 （或次数），记为deg（ x ）。
如果 a ={ x ， x }是 x 的一个环，则 a 使 x 的度增加2。对任意一个一般图 G ，将其节点的度按一种非增的顺序排列如下：（ d 1 ， d 2 ，…， d n ）， d 1 ≥ d 2 ≥…≥ d n ≥0，则称该序列为 G 的 度序列 。完全图 K n 的度序列为（ n -1， n -1，…， n -1）（ n 个 n -1）。
定理1.1 设 G 是一个一般图，则其所有节点的度之和 d 1 + d 2 +…+ d n 是一个偶数，从而，其奇度数节点的个数也必为偶数。
证明 G 的每条边对节点度数之和的贡献是：使与其关联的两个节点度各增加1，或使一个带有环的节点度增加2。如果一些整数的和是偶数，那么其中奇数的个数也必为偶数。
定理1.2 两个同构的一般图具有相同的度序列，但具有相同度序列的图不一定同构。
定理1.3 设 G =（ V ， E ）是一般图，则其节点集 V 可以被唯一地划分为非空子集 V 1 ， V 2 ，…， V k ，满足下述条件：
（1）由 V 1 ， V 2 ，…， V k 导出的一般子图 G 1 =（ V 1 ， E 1 ）， G 2 =（ V 2 ， E 2 ），…， G k =（ V k ， E k ）都是连通的。
（2）对任意的 i ≠ j ， V i 中任一节点 x 与 V j 中任一节点 y 之间不存在连接它们的途径。
在定理1.3中，一般图 G 1 ， G 2 ，…， G k 叫作 G 的 连通分支 ，其中（1）说明这些连通分图确实都是连通的，（2）强调这些连通分图都是由连通导出的最大的一般子图；也就是说，对任意的 i 和任意的节点集 U ，当 V i 包含于 U 且 V i ≠ U 时，由 U 导出的一般子图是不连通的。
定理1.4 设 G 和 G′ 是两个一般图，则 G 和 G′ 同构的必要条件有
（1）如果 G 是简单图，则 G′ 也是简单图。
（2）如果 G 是连通图，则 G′ 也是连通图。更一般地， G 和 G′ 具有相同数目的连通分图。
（3）如果 G 有一个长度为某整数 k 的圈，则 G′ 也有一个长度为 k 的圈。
（4）如果有一个 m 阶完全图 K m 是 G 的（导出）一般子图，则 G′ 也有一个这样的一般子图。
1736年，欧拉在他发表的图论文章中解决了著名的哥尼斯堡七桥问题。在东普鲁士，古老的哥尼斯堡城位于普雷格尔河畔，河中有两个岛，城区的四个部分通过七座桥连接起来，如图1.8所示。每到星期日，哥尼斯堡城的居民将会环城散步，由此提出了这样一个问题：能否以一种方法环绕全城，经过每座桥且只经过每座桥一次。欧拉把哥尼斯堡地图改画成了一个一般图，如图1.9所示。就这个一般图 G 而言，用我们已介绍过的术语来叙述的话，上述问题就是要确定 G 中是否存在一条闭迹，使它包含 G 的所有边。
图1.8 哥尼斯堡七桥问题示意图
图1.9 哥尼斯堡七桥问题抽象成一般图
受这些问题的启发，我们做出一些定义。一般图 G 中的一条迹叫作 欧拉迹 ，如果它包含了 G 中所有的边。回想迹在一般图中的定义，迹中包含每条边最多一次，我们对此的解释是：一条边在迹中重复的次数不得超过它的重数。无论是哥尼斯堡城的居民还是邮递员，都是在寻找一条闭欧拉迹。可以很容易发现，图1.9所表示的哥尼斯堡七桥问题的一般图中，不存在闭欧拉迹。因为如果我们真的漫步在一般图中一条闭欧拉迹上，除了第一次离开的那个节点，也就是起始的那个节点外，每次都进入一个节点并离开它而到一条新的边，即还未走过的边，当漫游结束时，我们回到了起始的那个节点，但不再离开。这就意味着，与一个给定节点关联的边是成对出现的，其中的一条用于进入该节点，另一条则用于离开该节点。如果与一个节点关联的边能够成对出现的话，那也就意味着在每个节点处边的数目必然是偶数。因此，我们得到了在一般图中存在闭欧拉迹的一个必要条件，即每个节点的度数是偶数。由于在哥尼斯堡七桥问题的一般图中，四个节点的度数都是奇数，所以该图中不存在闭欧拉迹。
定理1.5 设 G 是一个连通一般图，则 G 中存在闭欧拉迹，当且仅当 G 中每个节点的度数是偶数。
定理1.6 设 G 是一个连通一般图，则 G 中存在一条开欧拉迹，当且仅当恰好有两个奇度节点 u 和 v ，且这条开欧拉迹连接 u 和 v 。
定理1.7 设 G 是一个连通一般图，并设 G 中奇度节点的个数 m >0，则 G 的边可以被划分为 m /2个开迹，但不能被划分为少于 m /2个开迹。
定理1.8 设 G 是一个具有 K 条边的连通一般图，则 G 中存在一条长度为2 K 的闭路径，在该路径中，每条边的重复次数等于它重数的2倍。
19世纪，威廉·罗曼·哈密顿爵士发明了一个智力游戏，在一个十二面体的边上找出一条路径，该路径起始于某个节点，当经过其他每个节点恰好一次后，又回到起始的那个节点。一个十二面体的节点和边确定了一个具有20个节点（因此阶数为20）和30条边的图，如图1.10所示，右图中的粗线边是哈密顿游戏的一个解，该解和其他的一些解很容易被找到。
图1.10 哈密顿游戏
哈密顿游戏适用于任意的简单图。设 G 是一个简单图，能否确定一条路径，从 G 的某一节点出发，沿 G 的边到达其他每个节点恰好一次后，又返回起始节点。
现在，我们把图 G 中哈密顿游戏的解叫作 哈密顿圈 。更确切地说， n 阶图 G 的一个哈密顿圈是 G 中一个长度为 n 的圈。回忆圈的定义：圈是一条闭路径，圈中除了第一个节点与最后一个节点相同外，其他节点互不相同。因此， n 阶图 G 中的一个哈密顿圈是一个长度为 n 的圈 x 1 —x 2 —… —x n —x 1 ，其中 x 1 ， x 2 ，…， x n 是 G 的以某种顺序排列的 n 个节点。连接 G 的节点 a 和 b 的长度为 n -1的路径 a = x 1 —x 2 —… —x n = b 叫作 G 中的一条 哈密顿路径 。因此， G 中的一条哈密顿路径是 G 的 n 个节点的一个排列，在该排列中，相邻两个节点之间由 G 的一条边连接，哈密顿路径从排列中的第一个节点起，依次连接到最后一个节点。哈密顿路径中的边与哈密顿圈中的边是有区别的。我们也可以在一般图中考虑哈密顿路径和哈密顿圈的问题，但边的重数并不影响哈密顿路径和哈密顿圈的存在性，哈密顿路径和哈密顿圈的存在与否，只与某些节点对之间是否有一条边连接有关，而与连接这些节点对之间的边的重数无关。
定理1.9 带有桥的连通图中不存在哈密顿圈。
设 G 是一个 n 阶简单图，考虑下面的性质， G 可能满足这个性质，也可能不满足。Ore性质：对所有不邻接的不同节点对 x 和 y ，有deg（ x ）+deg（ y ）≥ n
定理1.10 设 G 是一个满足Ore性质、阶数 n ≥3的简单图，则 G 中存在哈密顿圈。
定理1.11 在一个 n 阶简单图中，如果每对不邻接节点的度之和至少是 n -1，则图中存在哈密顿路径。
二分图
设 G =（ V ， E ）是无向图，若节点 V 可分割为两个互不相交的子集（ A ， B ），且图中的每条边（ u ， v ）所关联的两个节点 u 和 v 分别属于这两个不同的节点集，（ u ∈ A ， v ∈ B ），则称图 G 为 二分图 ，如图1.11所示。
图1.11 二分图
多重图
社交网络分析中，大多数图是简单图。若一个图中没有自环和重边，它被称为 简单图 。具有至少两个节点的简单无向图中一定存在度相同的节点。如果一个图中有自环或重边，则称它为 多重图 。
图1.12展示了多重无向图和多重有向图。在多重无向图中，节点 A ， B ， C ， D 之间存在多条无向边，包括自环和多重边。多重有向图则显示了相同节点之间的多条有向边，包括自环和多重有向边。灰色的边和自环强调了多重边的存在，而黑色的边显示了基本的连接关系。这种图结构在表示复杂网络关系时非常有用。
图1.12 多重图
设 G =（ V ， E ）是一个多重图，如果节点集 V 可以被划分为两个子集 X 和 Y ，使得 G 的任意一条边的一个节点在 X 中，另一个节点在 Y 中，则称 G 是二分的，具有这种性质的一对 X ， Y ，称为 G 的（也称节点集 V 的）一个 二分划 。二分划中属于同一子集的节点之间是不邻接的，我们通常这样来画一个二分图的图形：将 X 中的节点画在左边（因此也称为左节点），将 Y 中的节点画在右边（因此也称为右节点）。注意，二分图中不存在任何环，与二分图同构的多重图也是一个二分图。
定理1.12 一个多重图是 二分的 ，当且仅当它的任意一个圈的长度是偶数。
定理1.13 设 G 是一个具有二分划 X ， Y 的二分图，如果| X |≠| Y |，则 G 中不存在哈密顿圈。如果| X |=| Y |，则 G 中不存在起始于 X 中的顶点又终止于 X 中节点的哈密顿路径。如果 X 和 Y 相差至少是两个顶点，则 G 中不存在哈密顿路径。如果| X |=| Y |+1，则 G 中不存在起始于 X 终止于 Y 的哈密顿路径，反之亦然。
树形图是一种特殊的图结构，用于表示层次关系。树形图中的顶点常称为节点。树形图由节点和连接这些节点的边组成，且不存在环路。树形图通常用于数据结构、网络结构和层次化信息的可视化。以图1.13为例，本节将详细介绍树形图的特点及组成部分。
（1） 根节点 ：树形图有一个唯一的根节点，代表树的起始点。在该图中， A 是根节点。
（2） 父节点和子节点 ：每个节点可以有零个或多个子节点，并且每个子节点有且只有一个父节点。例如， A 是 B 和 C 的父节点， B 是 D ， E ， F 的父节点。
（3） 叶节点 ：叶节点是没有子节点的节点，位于树的最底层。在该图中， J ， K ， L ， O ， P 都是叶节点。
（4） 边 ：边是连接节点的线，表示节点之间的关系。在树形图中，边有方向，指示从父节点到子节点的方向。例如，从 A 到 B 和 A 到 C 的边表示 A 是 B 和 C 的父节点。
（5） 子树 ：子树是树的一个分支，包含一个节点及其所有后代节点。例如，以 B 为根的子树包括节点 B 、 D 、 E 、 F 、 I 、 J 和 K 。
树形图没有环路，确保每个节点有且只有一条路径到达根节点；清晰地表示层次关系，便于理解和分析复杂的信息；每个节点有唯一的父节点（根节点除外），使得结构明确且易于遍历和操作。
图1.13 树形图
假如我们要建立一个 n 阶连通图，要求使用最少数目的边“刚好能够做到”。一个简单的构造方法是：选择一个顶点，将它与其他 n -1个顶点之间都连上一条边，结果得到一个完全二分图 K 1， n -1 ，我们把它叫作 星 。星 K 1， n -1 是连通的，且有 n -1条边，如果从中去掉任何一条边，则得到一个不连通的图，其中的一个顶点不和任何边连接。另一个简单的构造方法是：用一条路径连接 n 个顶点，其结果也是一个连通图，有 n -1条边，如果从中去掉任意一条边，也将得到一个不连通的图。那么，我们能构造出一个具有 n 个顶点、少于 n -1条边的连通图吗？
假设有一个 n 阶连通图 G ，试想一个一个地把边放入 G 中，这样我们是从有 n 个顶点、没有边、因而有 n 个连通分图的图开始，每放入一条边，能减少的连通分图的数目最多为1。如果新边连接的两个顶点已在同一个连通分图中，则连通分图的数目保持不变；如果新边连接的两个顶点不在同一个分图时，则这两个分图变成一个连通分图，而其余分图保持不变。因为我们起始于 n 个分图，而每条边最多只能减少一个连通分图，所以至少需要 n -1条边，才能将连通分图的数目减少到1，即得到一个连通图。因此，我们证明了下面的基本结论。
定理1.14 一个 n 阶连通图至少有 n -1条边。此外，对任意一个正整数 n ，存在一个恰好为 n -1条边的连通图。从 n 个顶点、 n -1条边的连通图中去掉任意一条边，得到一个不连通的图，因此，每条边都是一个桥。
树定义为这样一个连通图，去掉其任意一条边后就不再连通。因此，树是一个连通图，其每条边都是桥，即每条边对图的连通性都是必不可少的。
定理1.15 一个 n ≥1阶的连通图是树，当且仅当它恰好有 n -1条边。
定理1.16 设 G 是一个连通图， a ={ x ， y }是 G 的一条边， a 是桥，当且仅当 G 的任何圈中不包含 a 。
定理1.17 设 G 是一个 n 阶连通图， G 是树，当且仅当 G 中不存在圈。
定理1.18 一个图 G 是树，当且仅当任意一对不同的顶点 x 和 y 之间，都有唯一的一条路径连接，且这条路径必是连接 x 和 y 的最短路径。
定理1.19 设 G 是一个阶数 n ≥2的树，则 G 中至少有2个悬挂顶点。
定理1.20 任何连通图都有一个生成树。
定理1.21 设 T 1 和 T 2 是连通图 G 的两个生成树， β 是 T 1 的一条边，则 T 2 中必有一条边 α ，使得 T 1 中加入 α 而去掉 β 后，得到的图仍是 G 的一个生成树。
有向图类似于无向图，但是在有向图中，边是有方向的，并叫作 弧 。因此，有向图用来模拟非对称的关系，同理，无向图用来模拟对称的关系。
有向图
D
=（
V
，
A
）有一个顶点的元素集合
V
和一个弧的有序顶点对（两顶点可以相同）的集合
A
，其中，每条弧的形式为
α
=（
a
，
b
），其中，
a
和
b
是顶点，我们认为弧
α
是离开
a
进入
b
的，即从
a
指向
b
。在有向图中，（
a
，
b
）和（
b
，
a
）是不同的。今后我们将使用与无向图类似的术语，但这是有区别的，这些术语只用于有向图，而不用于无向图，比如，弧
α
=（
a
，
b
）具有起始顶点
和终止顶点
τ
（
α
）=
b
。在有向图中，可能同时包含弧（
a
，
b
）和弧（
b
，
a
），也可能包含形如（
a
，
a
）的环，环（
a
，
a
）进入和离开的是同一个顶点
a
。我们可以将有向图一般化，使其成为允许有多重弧的一般有向图。画一般有向图的图形与画无向图的图形是一样的，但对有向图，必须在每条边上画个箭头表示它的方向。
定理1.22 在一般有向图中，顶点的入度之和等于出度之和，且都等于图中弧的个数。
定理1.23 设 D 是一个连通有向图，则 D 中存在闭的有向欧拉迹，当且仅当其每个顶点的入度都等于它的出度。
定理1.24 设 D 是一个连通有向图， x 和 y 是 D 的不同顶点，则 D 中存在一条从 x 到 y 的有向欧拉迹，当且仅当
x 的出度比其入度大1;
y 的入度比其出度大1;
任意顶点 z ≠ x ， y ， z 的入度与出度相等。
定理1.25 设 D 是一个没有任何环的强连通有向图，如果对任意顶点 x ，都有（ x 的入度）+（ x 的出度）≥ n ，则 D 中存在有向哈密顿圈。
下面我们来说明，一个竞赛图中总存在哈密顿圈，也就是说，总能使选手按下面的顺序排列 p 1 ， p 2 ，…， p n ，使得 p 1 胜 p 2 ， p 2 胜 p 3 ，…， p n -1 胜 p n 。由于我们并没有强调每个选手必须胜他后面的所有选手，所以这个排列并不意味着是选手之间相容的排列。实际上，一个竞赛图中甚至可能存在有向哈密顿圈，这意味着，排列 p 1 ， p 2 ，…， p n 中的每个选手都是第一名！
定理1.26 任意一个竞赛图中存在哈密顿路。
定理1.27 设 G =（ V ， E ）是连通图，则 G 有一个强连通有向图，当且仅当 G 中没有任何桥。
网络 是带有两个不同顶点 s 和 t 的有向图，其中的每条弧都带有一个非负的权重，叫作它的 容量 。如果把每条弧都想象成一个管道，其中流动着某种物质，弧的容量就好比是单位时间内流过该管道的流量，这里的一个重要的问题是，在所给容量的限制下，找出从“源” s 到“目标” t 的最大可能流量。对此问题的回答以及随之产生的构造最大流量的算法，是由最大流最小割（max-flow min-cut）定理给出来的。
网络是一个有向图（ V ， A ），其中给出了两个特殊的顶点，源 s 和目标 t ，这里 s ≠ t ，且每条弧 α 都有一个非负的权重 c （ α ），叫作该弧的容量， N =（ V ， A ， s ， t ， c ）表示一个网络。网络中要处理的一个基本问题是，在有向图中所给定的弧及所给定弧的容量的限制下，把一种物质从源移到目标。正式地说，网络 N 中的流（flow）定义为一个函数 f ，它为每条弧 α 定义了一个实数 f （ α ），满足下列限制条件：
（1）0≤ f （ α ）≤ c （ α ）（通过一条弧的流是非负的，且不超过弧的容量）；
（2）对每个顶点
x
≠
s
，
t
，
（对每个不同于源和目标的顶点
x
，进入
x
的流量等于流出
x
的流量）。
定理1.28 设 N =（ V ， A ， s ， t ， c ）是一个网络，则 N 中一个流的最大值等于 N 中一个割的最小容量。换句话说，一个最大流的值等于一个最小割的容量。如果所有弧的容量都是整数，则存在一个所有值也都是整数的最大流。
定理1.29 设 s 和 t 是有向图 D =（ V ， A ）中的不同顶点，则从 s 到 t 的逐对弧不相交的路径的最多数目等于一个 st -分离集中弧的最少数目。
定理1.30 设 G 是一个二分图， G 的一个匹配中边的最多数目记为 ρ （ G ），一个覆盖中顶点的最少数目记为 c （ G ），则 ρ （ G ）= c （ G ）。
图论思想应用于社交网络分析的原因有很多 [ 43 ] 。首先，图论提供了可以用于标记和表示许多社会结构属性的词汇表。这些词汇表为我们提供了一组基本的概念，使我们能够精准地了解这些属性。其次，可以利用图论提供的数学运算和观念对许多属性进行量化和测量 [ 44 ， 45 ] 。最后，图论为我们提供了关于图（以及背后所代表的社会结构）的定理的证明。与其他数学分支类似，图论允许研究者证明定理以及推断可检验命题。
除了作为一个数学系统工具，图论还为我们提供了一种以包含一组行动者及其联系的社会系统模型的方式来表示社会网络的方法。模型提供对某种情景简化的表示，包含该情景所代表的某些但不是全部要素 [ 46 ， 47 ] 。当一个图被用作社会网络模型时，点（被称为节点）用来代表行动者，而连接点的线用来代表行动者之间的联系。在这种情况下，一个图是一个社会网络模型。
Harary [ 48 ， 49 ] 以及一些其他人 [ 45 ， 50 ， 51 ， 52 ] 将图作为一种正式表示社会管理和量化重要社会结构属性的方法，并使其在社交网络分析中得到广泛应用。图论被大量应用于人类学 [ 53 ， 54 ] 、社会心理学 [ 55 ， 56 ] 、商业、组织研究和地理学 [ 57 ] 中。
图可以作为具有无向二元关系的社会网络的模型，“无向”是因为每对行动者之间的联系要么存在要么不存在。无向关系包括诸如是否为正式组织或一般群体的成员关系，与谁结婚、是谁的直系血亲等亲属关系，是否住在附近等远近关系，还可以是诸如“共事”一类的互动关系。在图中，节点代表行动者，连线代表行动者之间的联系。在图论中，节点也被称为顶点或点，连线也被称为边或弧。
一般而言，社交网络可表示为 G =（ V ， E ），其中 V ={ v 1 ， v 2 ， v 3 ，…， v n }表示节点元素集合， E ={ e 1 ， e 2 ， e 3 ，…， e m }表示节点之间的连接关系（边）集合。节点集 V 中的元素称为节点（node）或顶点（vertex），是构成社交网络的最基本元素。边集 E 中的元素称为边（edge）或弧（arc），描述社交网络各元素之间的相互作用。
图中的一个节点表示社交网络中的一个用户或一个社会团体。我们可以将社交网络看作一个系统，系统的主体是用户，用户可以公开或者半公开个人信息。社交网络是一个以“人”为中心的多维空间，简单来说，这个多维空间是通过“人”这一主体或者人的行为活动来建立的。因此图中的节点是社交网络最基本的元素。
图中的边是节点之间的连线，代表的是社交网络中的用户关系，例如，微博的互相关注，QQ、微信的互加好友。社交网络是一个系统，而系统中的用户能够创建和维护与其他用户间的连接关系，且用户可以通过连接关系来传播信息，或者与其他用户交流和共享信息。图中的边也是基本而重要的元素。
由于真实系统的复杂性，人们从不同的角度对复杂网络进行了分类。根据社交网络中的连边是否具有方向性，可将社交网络分为无向网络和有向网络。一个有向关系可以表现为一个有向图。一个有向图由代表行动者的一组节点和表现节点间有向联系的一组有向边组成。在有向网络中，需要考虑节点之间相互作用的方向性。而在无向社交网络中，节点对（ i ， j ）和（ j ， i ）对应同一条边。
图1.14给出了一个包含四个节点的无向图（图a）和有向图（图b）的例子。图的节点和边往往直接反映了实际网络中节点以及它们之间的关系。
图1.14 无向图和有向图示意