这个问题在18世纪被数学家欧拉解决了。他把这个 问题转化为图1—1右边所示的图。图上用A、B、C、D4 个顶点分别表示4个地区，用两点间的线段表示连接各地 的桥。这样原来的问题就转化为：从A顶点出发经过其中 每一条线段一次，而且仅一次，再回到A点的“一笔画” 问题。 欧拉对柯尼斯堡问题作出了否定的结论。因为对于 每一个顶点，不论如何经过，必须有一条进路和一条出 路，所以对每一个顶点(除起点和终点)来说与它有关的线 段(称为边)必须是偶数条。而图1-1(右)的顶点有关的线段 都是奇数条，因此不可能一笔画出。而如图4—12中的图 形是可以一笔画出的。
哪些图是有向图？哪些图是无向图？
a a a a a a
b
b
c b
c b
d
e b
e b
e
c
e
d
d
c

d
c d
c d
(G1 )
( G2 )
( G3 )
(G4 )
( G5 )
( G6 )
无向图与有向图：边的表示方式是用该边的两 个顶点来表示的，如果边的表示无方向，那么， 对应的图就是无向图，否则称为有向图，如下 图所示：
在无向图中，边的两个顶点在边的表示中可以互换，如边 （V1,V4）与边（V4,V1）是等价的，表示的是同一条边。 （无向图中边的表示用圆括号） 在有向图中，边的走向不同就认为是不同的边。如在边 的集合E={&;,< 5,3 >,< 2,1 >,< 5,5 >}(见右上图)中，其中< 1,4 >表示该边是由顶点1出发， 到顶点4结束，即边< 1,4 >表明了该边的方向性，且两个 顶点的顺序不能颠倒。（有向图中边的表示用尖括号）
• 顶点的度：与顶点关联的边的数目，有向图顶 点的度等于该顶点的入度与出度之和。 入度——以该顶点为终点的边的数目和 出度——以该顶点为起点的边的数目和 图的阶：图中顶点的个数。例如图1—3中 分别是6和3。 度数为奇数的顶点叫做奇点，度数为偶数 的点叫做偶点。
• [定理1] 图G中所有顶点的度数之和等于 边数的2倍。因为计算顶点的度数时。每 条边均用到2次。 [定理2] 任意一个图一定有偶数个奇点。
• 连通：如果顶点u，v属于G，u，v之间有一条 从u通过若干条边到达v的通路，则认为顶点u 和v是连通的。 连通图：如果对于图G中每一对不同顶点u， v都有一条(u，v)通路，则称G是连通图。 通路指u-->边1-->顶点1-->边2-->顶点 2-->……-->v，点和边交替相接，且互不相 同。
图的基本概念
• 定义：图G定义为一个偶对(V，E)，记作G： (V，E)。其中 1)V是一个非空有限集合，它的元素称为顶 点； 2)E也是一个集合，它的元素称为边 例如 图1-4中的图有4个顶点，4条边。 或者定义：图G（Graph）是由顶点的集合 V和边的集合E所组成的二元组，记作：G = （V，E） • 其中V是顶点的集合，E是边的集合。
欧拉通过对柯尼斯堡桥问题的研究，于1736年发表了 著名的关于图论的论文，从而创立了图论的学说。图1—2一 类的问题就是图论中所指的图。
又如，有6个足球队之间进行循环赛，他们比 赛的场次可以用图1-3(1)来表示。有3个人相 互写信，可以用图1—3(2)来表示。
• 从上面两个例子可看出，我们这里所说的图(graph)， 与人们通常所熟悉的图，如圆、四边形、函数图象等 是很不相同的。是指某些具体事物和这些事物之间的 联系。如果我们用点来表示事物(如地点、队)，用线 段来表示两事物之间的联系，那么一个图就是表示事 物的点集和表示事物之间联系的线段集合所构成。其 中线段仅表示两点的关系，它的长短与曲直是无关紧 要的。例如图1-4中3个图，被认为是同一个图。
数据结构-图的基本知识
什么是图
•
什么是计算机中所说的图?请先看下面的 “柯尼斯堡桥问题”。传说在东普鲁士境内， 有一座柯尼斯堡城，希雷格尔河流经这个城市 的克奈霍福岛后，就将这个城市一分为二，形 成如图1—1（左）的A、B、C、D 4个地区。 人们建造了7座桥将这4个地区连起来。在游 览中有人提出，是否可以从A地出发，各座桥 恰好通过一次，最后又回到原来出发地呢?