0:00
在本课程的第一周啊我们介绍了
一些图论的基本概念，或者说呢是一些术语的含义。
它们为我们讨论社会网络结构的方方面面问题呢提供了便利。在那些讨论中啊，
我们没有强调图中这个边的方向性。
也就说在一个关系中两端的节点是对称的。 例如在这个社会网络的情况下，
我们实际上假设了如果A认识B，那么B就认识A。
但是在现实中呢， 有些事物和情况也可以看成是一些节点
以及节点之间的一类关系。但是那些个关系呢，
它不是对称的。比方文章之间的引用关系，
微博账号之间的粉丝关系。文章引用A引用B，
B通常不会引用A。
微博之间的关系呢，A是B的粉丝，B不一定是A的粉丝。 还有网络信息之间的链接关系。
网页A中有一个链接啊指向了网页B，
但是B呢它不一定指向A。 人们之间的认识或者说了解的关系，也可以看成是有方向性的。
我认识某个明星而且相当了解他的情况，
但是呢，他不一定认识我。为了表示这种情况呢，
人们发展出了所谓有向图的概念。
其中的边哪是带有箭头的。通常呢，
会有比方有个A，节点A，啊比方有个节点B，
啊，这个时候呢，那么就要有个箭头表示这种啊不对称的这样一个关系。
那么如果这类关系中的某两个节点恰好互相都有关系，
比方说两个微博他们互粉。 那么我们就在他们之间画两条不同方向的边。比方说也有可能是
这个A，啊比方这个B，啊，可以说它们互相之间
都有这样一个关系。这就是我们这里要讨论的情况。
有几个和无向图中的一些基本概念
对应的概念。首先一个节点的度数。
无向图中呢，它就是和它直接相连的那些个节点或者说它们邻居的个数。
在有向图中，我们讲出度和入度， 出向邻居和
入向邻居。例如这个右边这个图，我们看这个B，
啊，这个B这个节点，它的出度呢，出度。
我们说这个B的这个出度，啊，它应该是等于
2，等于2。因为它有两个出向邻居，一个是C，一个是
D。那么它的入度呢，在这个图里头，它的入度，它的入度，啊，
我们让它就是等于1。
因为只有一个啊这个A啊指向它。
有向图中我们常常会关心
两个节点之间是否有一个有向路径。
有向路径啊就是这个有向路径。 强调其中边的方向的一致性。
我们很容易看到啊在这个
1这个里头，X 到Y有一条有向路径，
不一定就有从Y到X的路径。
第二，即使从X到Y有，
从Y到X也有，但这两条路径经过的节点集合可能完全不同。
你比方我们现在来看，
这个啊A到B，它是有有向路径的。
呃B到A有没有有有向路径呢？ 它是有的，但是呢不是这么直接回去，而是经过这么一个大圈。
啊我们看到这个回去，就是说呢，这个和无向的情况就不是一样的。
有时候我们也会谈到有向图中的
有向圈，哈，有时候我们也会说有向圈。
有向圈啊。
它呢是有向路径的一种特别的情况，也就是首尾相连的。
还是在右边这个图中啊，A,B,D,E,F,A，就是A,B,D,E,F,A，我们把它连起来。
其实就是这个样子的。啊它们就是构成了这么一个
啊一个有方向的，它们形成了这么一个圈的情况。
通常啊，为了这个叙述简单， 在已知有向图的场合，
我们经常谈到路径啊、圈啦，指的就是有向路径、有向圈。
最后一点呢，在我们的讨论中，如果不特别说明，
谈到的图呢，都是有穷的，就是它的节点数是有限的。
连通是无向图中的一个重要概念。
在有向图中呢最对应的就叫强连通。
一个有向图它被称为是强连通的，
当且仅当它的任意两个节点之间在两个方向上
都存在有向路径。 例如，
啊我们左边这个图。它不是强连通的。
因为这个从这个C，啊这个C节点
到这个A，它没有边，啊它没有路径，啊没有路径。
D到A也没有路径。
但是如果我们适当的加上一条边，比方说这个图加上这么一条边，啊加上这么一条边。
就可能使这个图呢变成强连通的了。
注意尽管这个原本可能有多个节点之间都没有
有向路径，但是可能添加一条边就解决了问题。
我们这个就是，你看加了一条边，那么就使得C到
A有有向路径了。这就是这个直接的边。 那么D到A实际上也有了有向路径。那么啊就是这个路径。
走过来啊。也就有了有向路径。所以呢一条边有可能解决多个问题。
右边这个也是，啊右边这个也是。本来它不是
这一个强连通的。因为从这个，比方说
这个我们没有办法从A到G，
这个G呢它只有往外出的，它没有往里进的。所以谁也不能到它，通过有向路径。
但是如果我们加了一条边以后，比方说加了这么一条边。我们就看到了从任何节点 都可以到G，
啊到G。而且仔细看呢，它每两个节点之间都有有向路径。比方说我们怎么从F
走到G啊。它它就应该是这样子的啊。比方说，它就应该是这么走，这么走啊，跟着这个有向的边
来走。这就是这么一个一个。 但是，
并不是随便添加一条边就可以把不强强连通的变成
强连通的。假如刚才我们没有注意，啊是添的不是从D到G的，
而是从G到D的，那么这个事就无济于事。
那么对应这个无向图中的
连通分量的概念，啊这是一个很重要的概念，
有向图中呢它叫做强连通分量。它是
由一个节点子集和它们之间的边构成，但是要满足两个要求。
第一呢，如果它有两个或者更多的节点，那么其中任意两个节点之间
都要存在两个方向的有向路径。啊就是要存在两个方向的有向路径。
啊这个路径可以不一样，但是两个方向都应该有。第二条
也是要同时满足才行。也就是，
那些个节点要不被包含在一个更大的 并且满足这个第一个
要求的节点集合中。
这第二个要求啊对于我们初学者来说，常常是容易感到
困扰的。这样的说法也隐含着，
如果只有一个节点并且没有包含它的强连通分量的话，那么这个节点
自己就是一个强连通分量。 那么这里呢是一个例子啊。
这个9，啊这个节点9，
还有e，还有这个f，啊这三个节点，
它们能构成强连通分量吗？加上它们之间的边。
我们看到它们之间都是有双向路径的。但不是强连通分量。
为什么呢？因为它们不满足刚才说的条件的第二条，
有一个更大的包含它们三个节点的集合。
其中每个节点对之间都有双向路径，啊就这么一个大的集合。
这个是不是强连通分量呢，
i就是由1,4,3,8,9,d,e,f,i是不是呢？
是的，啊如果我们仔细看看就会发现它们两两之间 都有双向的路径。好，我们再看，
这边四个 节点是不是一个强连通分量呢？那更不是了，因为它连第一条都不满足。
比方说在这个里头我们没有办法从2到b，啊没有办法做到这一点。
好，那么这个节点7是不是？
这个节点7还真的就是。
因为它满足我们前面说的两条。
于是我们可以想象一个有向图会有许多强连通分量。 一个可以问的问题就是，
有没有可能某一个节点属于两个不同的强连通分量呢？
答案是不可能。同学们自己可以思考证明。
这个认识意味着强连通的概念将有向图的节点集合
做了一个划分。 那做了一个划分，划分是经常
呃有用的一个概念，啊有用的概念。
那么这是小结。我们谈到有向图，
它是描述具有方向性的关系的有用的工具。
与无向图的几个最基本的概念，
我们这有向图都有对应的概念。那就是节点就是节点。啊但是这个边呢，我们现在叫做有向边。
路径也好，圈也好，在这里就叫有向路径，
啊强调的是它方向性，以及有向圈。连通变成了强连通。
啊连通分量对应的这里是强连通分量。
李晓明 （Li Xiaoming）教授（Professor）
邱泽奇 （Qiu Zeqi）教授 (Professor)
王卫红（Wang Weihong）lecturer
