Reference: Bearman, Moody and Stovel, 2004 image by Mark Newman
Reference: Adamic and Adar, 2004
Protein interaction network
Reference: Jeong et al, Nature Review | Genetics
5. 链与圈
给定一个图G=（V，E），G中的一个点、边交错
序列（vi1，ei1，vi2，ei2，…，vik-1，eik-1，vik），如果
满足eit=[vit，vit+1]（t=1，2，…，k-1），则称为一条联
接vi1和vik的链，记为=（vi1，vi2，…，vik）。
链（vi1，vi2，…，vik）中，若vi1=vik ，称之为一 个圈，记为C= （vi1，vi2，…，vik-1， vi1 ） 。
Power transmission grid of Western US
The Internet
The Internet as mapped by The Opte Project
More Applications

Hypertexts

网页包含到其他网页的超链接。整个Web是一个图. 搜 索引擎需要图处理算法。 职位招聘，如何有效将职位与应聘者匹配？ 工程项目的任务安排，如何满足限制条件，并在最短时 间内完成？ 大型软件系统，函数（模块）之间调用关系。编译器分 析调用关系图确定如何最好分配资源才能使程序更有效 率。
例：有甲、乙、丙、丁、戊五个球队，各队之间比赛
情况如表：
甲 甲 乙 丙 丁 戊 × 负 胜 负 负 乙 胜 × 负 丙 负 胜 × 负 胜 × 胜 负 × 丁 胜 戊 胜
点：球队； 连线：两个球队之间比赛过，如甲胜乙，用 v1 v2表示。
v5 v1 v2
v3
v4
图的定义
定义1：一个图，是由非空集合V(G)={vi} 和V(G)中 元素的有序对（或无序对）的集合E(G)={ek}
i
vVe
vV0
必为偶数。即在一个图中奇点的个数必为偶数。
4. 节点度与悬挂点、孤立点
图G中以点v为端点的边的数目，称为v在G中的度， 记为d（v）。
v1
e1 v2 e2 e3 v3
v4
e4 e5
d(v1)=2 d(v2)=3 d(v3)=4 d(v4)=1
度为1 的点为悬挂点，悬挂点的关联边称为悬挂边， 度为零的点称为孤立点。
初等链：链中点都不同。（边能否相同？）
简单链：链中边都不同。（点能否相同？）
v1 e3
e1 v3 e4
e2 v5
v7 e6 e7
e5
v2
e8
v4 e9
v6
v8
简单链：1=（v2，v1，v3，v6，v4，v3，v5） 初等链：2=（v2，v1，v3，v5） 简单圈：C1=（v1，v2，v4，v3，v5，v6，v3 ，v1 ） 初等圈：C2=（v1，v2，v4，v6，v5，v3 ，v1 ） 有向图中，不考虑弧的方向，有类似链（圈）的定义。 当链（圈）上弧的方向一致时，称为路（回路）。
的两倍， 即
vV
3. 奇点与偶点
d(v) 2m
次为奇数的点称为奇点，否则称为偶点。
定理2 任一图中奇点的个数为偶数。
证明：设v0和v e分别是G中的奇点和偶点的集合， 由定理1，有
vV0
d(v ) d(v) d(v) 2m
i vVe vV
因
vV
d(v) 是偶数， d(v) 也是偶数，故 d(v )

Matching


Schedules


Program structure

Graph Applications
Graph Problems and Algorithms
哈密頓（Hamilton） 周遊世界问題
正十二面体有二十个顶点 表示世界上20个城市 各经每个城市一次 最后返回原地
投影至平面
tree A connected graph G Spanning trees of G
图术语回顾
点：研究对象（陆地、路口、国家、球队）；
点间连线：对象之间的特定关系（陆地间有桥、路口 之间道路、两国边界、两球队比赛及结果)。
对称关系：桥、道路、边界； 用不带箭头的连线表示，称为边。 非对称关系：甲队胜乙队，用带箭头的连线表示， 称为弧。 图：点及边（或弧）组成。
二分图（偶图） Bipartite graphs

A graph that can be decomposed into two partite sets but not fewer is bipartite It is a complete bipartite if its vertices can be divided into two non-empty groups, A and B. Each vertex in A is connected to B, and viceversa
Planar:
=
NOT Planar:
平面图实例

8个顶点(V=8) 12条边 (E=12) 6个面 (F=6) 8-12+6=2
更多平面图实例
树 Trees

树(tree):连通无简单回路无向图


若有n个顶点，則有n-1条边 任两点之间仅有一条路径

生成树 (spanning tree):包括图中所有的顶点，并 且是一棵树
所组成的二元组（V(G)，E(G)）所构成。
记为 简记 其中 G= （ V(G)， E(G) ） G= （V，E） V= {vi} 称为点集，vi为点 。
E={ek}称为边集， ek为边（或弧）。
当V，E为有限集时，称G为有限图。 否则，称G为无限图。
无向图：由点及边构成 ，边[vi，vj]
有向图：由点及弧构成，弧（ vi，vj）
一些特殊图类
1. 平凡图 3. 连通图 给定图G=（V，E），任何两点间至少有一条链，则 称G是连通图，否则为不连通图。 若G是不连通的，它的每个连通部分称为G的连通分 图。 节点数n=1,边数m=0的图。
2. 零图 边数m=0的图。
4.树
无圈连通图。
5. 完备图 无向图的完备图：任何两点之间有一条边； 有向图的完备图：任何两点u与v之间有两条有向边 （u，v）及（v，u）。 基本图：把有向图的每条边除去方向得到的无向图。 6.二分图
v3
e5
2. 相邻与关联 若边e=[u，v]∈E，称u，v是e的端点，也称u，v是 相邻的。称e是点u（及点v）的关联边。
若两条边有一个公共的端点，则称这两条边相邻接。
vi
e
vj
点与点 相邻
边与边相邻接
vi，vj相邻 e 与vi，vj关联
vi
e1
vk e2
vj
点与边关联
定理1 图G=（V，E）中，所有点的次之和为边数
一直往前走 碰壁就回头換条路找 沿途要记录下走过的路线
老鼠走迷宮深度优先搜索
Some graph-processing problems
Path. Is there a path between s to t? Shortest path. What is the shortest path between s and t? Longest path. What is the longest simple path between s and t? Cycle. Is there a cycle in the graph? Euler tour. Is there a cycle that uses each edge exactly once? Hamilton tour. Is there a cycle that uses each vertex exactly once? Connectivity. Is there a way to connect all of the vertices? MST. What is the best way to connect Байду номын сангаасll of the vertices? Biconnectivity. Is there a vertex whose removal disconnects the graph? Planarity. Can you draw the graph in the plane with no crossing edges? First challenge: Which of these problems is easy? difficult? intractable?
若V(G)=X ∪ Y,X ∩ Y= Ф，X 、Y中的任两顶点不 相邻，则G称为二分图，记为（S,X,Y）。
7.完全二分图 若V(G)=(S,X,Y),如果任意μ∈X、ν∈Y，都有[μ， ν]∈E，则称G是完全的二分图。 8.正则图 如果G中每个点的次数都相同，则G叫做正则图。 9.网络 若对图G=（V，E）中每条边[vi，vj]赋予一个数 wij，则称wij为边[vi，vj]的权，并称图G为网络（或赋 权图）。 网络：无向网络、有向网络。
图G中点集V的顶点个数，记为p (G) ； 边数记为q(G), 简记 p，q。
二、图论中常用术语
1. 简单图与多重图 某条边两个端点相同，称这条边为环。 若两点之间有多于一条的边，称这些边为多重边。
v1 e1 e2
v4 e4
无环、无多重边的 图称为简单图。 多重图：无环、但 允许有多重边。
v2
e3