图论入门

图论基本知识对于网络的研究，最早是从数学家开始的，其基本的理论就是图论，它也是目前组合数学领域最活跃的分支。

我们在复杂网络的研究中将要遇到的各种类型的网络，无向的、有向的、加权的……这些都可以用图论的语言和符号精确简洁地描述。

图论不仅为物理学家提供了描述网络的语言和研究的平台，而且其结论和技巧已经被广泛地移植到复杂网络的研究中。

图论，尤其是随机图论已经与统计物理并驾齐驱地成为研究复杂网络的两大解析方法之一。

考虑到物理学家对于图论这一领域比较陌生，我在此专辟一章介绍图论的基本知识，同时将在后面的章节中不加说明地使用本章定义过的符号。

进一步研究所需要的更深入的图论知识，请参考相关文献[1-5]。

本章只给出非平凡的定理的证明，过于简单直观的定理的证明将留给读者。

个别定理涉及到非常深入的数学知识和繁复的证明，我们将列出相关参考文献并略去证明过程。

对于图论知识比较熟悉的读者可以直接跳过此章，不影响整体阅读。

图的基本概念图G 是指两个集合(V ，E)，其中集合E 是集合V×V 的一个子集。

集合V 称为图的顶点集，往往被用来代表实际系统中的个体，集合E 被称为图的边集，多用于表示实际系统中个体之间的关系或相互作用。

若{,}x y E ，就称图G 中有一条从x 到y 的弧（有向边），记为x→y ，其中顶点x 叫做弧的起点，顶点y 叫做弧的终点。

根据定义，从任意顶点x 到y 至多只有一条弧，这是因为如果两个顶点有多种需要区分的关系或相互作用，我们总是乐意在多个图中分别表示，从而不至于因为这种复杂的关系而给解析分析带来困难。

如果再假设图G 中不含自己到自己的弧，我们就称图G 为简单图，或者更精确地叫做有向简单图。

以后如果没有特殊的说明，所有出现的图都是简单图。

记G 中顶点数为()||G V ν=，边数为()||G E ε=，分别叫做图G 的阶和规模，显然有()()(()1)G G G ενν≤-。

图2.1a 给出了一个计算机分级网络的示意图，及其表示为顶点集和边集的形式。

第6章图论一、内容提要1.图的定义定义1.(图的定义一)图G = (V, E)是一个系统，其中(1)V≠∅是一个有限集合；V中的每一元素v∈V都称为图G的一个结点；V称为图G 的结点集；(2)E是一个有限集合；E中的每一元素e∈E都称为图G的一条边；E称为图G的边集。

定义2. (图的定义二)图G = (V, E)是一个系统，其中(1)V ≠∅是一有限集合；V中的每一元素v∈V都称为图G的一个结点；V称为图G的结点集；(2)E⊆V⨯V是一有限集合，一个V上的关系；E中的每一元素(u,v)∈E都称为图G的一条边(这里u, v∈V)；E称为图G的边集。

定义3. (图的定义三)图G= (V,∑, E)是一个系统，其中(1)V ≠∅是一有限集合；V中的每一元素v∈V都称为图G的一个结点；V称为图G的结点集；(2)∑是一有限集合；∑中的每一元素σ∈∑都称为图G中的一个标号；∑称为图G的标号集；(3)E ⊆V⨯∑⨯V是一有限集合，一个三元关系；E中的每一元素(u,σ ,v)∈E都称为图G的一条边或弧,此边起自u而终于v；称u是此边的起点，称σ是此边的标号，称v是此边的终点，起点和终点统称为边的端点(这里u, v∈V , σ∈∑)；E称为图G的边集。

定义4. (图的定义四)图G=(V,E, γ)是一个系统，其中(1)V ≠∅是一有限集合；V中的每一元素v∈V都称为图G的一个结点；V称为图G 的结点集；(2)E是一个有限集合；E中的每一元素e∈E都称为图G的一条边；E称为图G的边集。

(3)γ是边到结点集的一个关联函数，即γ:E→2V(无向图) 或γ:E→ V⨯V (有向图) 。

一般来说，它将E中的每条边e∈E与结点集V中的一个二元子集{u,v}∈2V (或{u,v}⊆V)相关联或与结点集V上的一个二元组(u,v)∈V⨯V相关联，即γ(e)={u,v} (无向图) 或γ(e)= (u,v) (有向图) ，称u是此边的起点，称v是此边的终点，结点u和v统称为边的端点。