图论网络(上)

一、 图与网络

网络：“事物”+“联系”

为了讨论网络的共性，发明了“图”(graph)的概念

“图”graph包括：节点和边。  故网络可以如图1所示，由节点和边构成。

图1. 网络

如果我们对两个看起来不一样的图，能够给予某种编号，使得它们这个相邻的节点都是一致的，那么这两个图本质上是同一个图。用图论的术语，它们称为“同构”。同构，画法不一样，但结构上是相同。如图2所示两个网络，但是同一个。

图2

二、 路径与连通

 图3

如图3，F和L之间路径：

F-H-J-K-L，F-H-L，F-G-J-K-L，F-H-J-G-I-K-L，...

F和L之间最短路径：F-H-L

最短路径长度称为两个节点之间的距离，故F和L之间的距离为2

---

如果在一个图中，每两个节点之间都有路径通达，我们就说，这个图是连通的

图4

如图4所示，由节点A到M这些节点一起组成的图是不连通的。那么不连通的图自然地是由几部分组成。这样的每一部分或每一组称为连通分量。图4是由三个连通分量构成。

连通分量：节点之间存在路径；不包含在其他的连通分量中。

例如，A-B这两个节点，它们构成了一个连通分量，但是H-L-M不构成，因为还有更大的将其包括F-G-I-K-L-M-H

三、 二部图与广度优先搜索

很多情况下，一个图所表达的关系可能使节点自然被分成两组，所有的关系都是存在于这两组之间，组内互相没有关系。

图5

如图5所示，男性与女性若存在婚姻关系，则他们之间存在一条边，同理，学生和某大学存在隶属关系，则他们之间存在一条边。类似于这样的图，组内的节点之间就没有边，所有的边就在这两组之间，称为二部图。

举几个例子，如图6所示：

图6

(A)中，若把1和3看作一组，2和4看作一组，则(A)写成(B)形式，明显得(A)和(B)都为二部图

(D)中，若把节点1、3、5看作一组，2、4、6看作一组，则(D)写成(E)的形式，即都为二部图

---

对于一个复杂的网络图，判断其是否为二部图

一个图是二部图的充分必要条件是它没有长度为奇数的圈

如何判断一个图是否包含长度为奇数的圈？

在计算机科学中，提供一种方法，即图上的广度优先搜索（遍历）

基本要点：从一个节点开始，沿着相连的边，将图的节点一一列举出来的一种过程（算法）

以上图3为例，从F节点开始（这可以从任何节点开始），可画成图7所示。

图7

从F开始画，第一步把和它直接相连的邻居， 连起来。即为G和H，这是直接和F有关系。 接着选取和G、H 直接有关系的节点。共有I、J、L、M，（注意，H 跟J是有关系的，这个后面再谈）。最后连接K，K和I、J、L有关。这样一个做法就叫广度优先搜索。

这样其实是把每个节点分成了层结构，F为一层（第0层），G、H为一层（第1层），I、J、L、M为一层（第2层），K为一层（第三层）。

现在画出来的边都是在相邻的两个层之间的。

对于上面遗漏的L和M之间的连接，称为层内边，如图8所示。

图8

 故能够得出，如果任何层内有一条边，则这个图中存在着一个长度为奇数的圈。

---

要点小结：

1.许多社会现象或状态结构，都呈现二部图的形式

2.是否有长度为奇数的圈，是判断一个图是否为二部图的充分必要条件

3.广度优先搜索，是考察一个图是否存在长度为奇数的圈的有效方法