如何定义图这个数学概念？ What we have drawn in Figure 1.1 is called a graph.Formally,a graph G consists of a finite nonempty set V of objects called vertices(the singular is vertex)and a set E of 2- element subsets of V called edges.The sets V and E are the vertex set and edge set of G, G=V,E) 如果要定 E={u,v}u,v∈Vy 义有向图？
如何定义图这个数学概念？ G (V ,E ) E {{u,v}| u,v V } 如果要定 义有向图？
有向图和无向图之间的本质区别是什么？ D Figure 1.37:Digraphs 无向图是有向图的特殊类，简化表达为无向图
有向图和无向图之间的本质区别是什么？ 无向图是有向图的特殊类，简化表达为无向图
如何用图进行问题建模？ ·构造图节点 ·确定什么作为图节点？ ·构造图中的边 ·确定什么作为图中的边？ ·用图中数学语言重述待解问题 ·从自然语言到形式（数学）语言
如何用图进行问题建模？ • 构造图节点 • 确定什么作为图节点？ • 构造图中的边 • 确定什么作为图中的边？ • 用图中数学语言重述待解问题 • 从自然语言到形式（数学）语言
Theorem 1.6 If a graph G contains a u-v walk of length l,then G contains a u-l path of length at most I. Proof.Among all u-v walks in G,let P=(u=0,1,,k= 图中定 be a u-vwalk of smallest length k.Therefore,k s I.We claim that P is a u-v path. Assume,to the contrary,that this is not the case.Then some vertex of Gmust be repeated 理的证 in P,sayu=;for some iandjwithik.If we then delete the verticesu 明，多 from P,we arrive at the u-vwalk 用如此 的构造 (=0,41,,41-1,4=j,4j+1,…,4= 法 whose length is less than k,which is impossible.Therefore,as claimed,P is a uvpath of lengthk≤l. ■
图中定 理的证 明，多 用如此 的构造 法