计算机问题求解-论题3.5 图的基本概念 陶先平 2022年10月12日
计算机问题求解 -论题 3.5 图的基本概念 陶先平 2022年10月12日
Konigsberg-七桥问题 ·问题的抽象： ·用顶点表示对象-“地块” ·用边表示对象之间的关系“有桥相连” D B B
Königsberg七桥问题 • 问题的抽象： • 用顶点表示对象-“地块” • 用边表示对象之间的关系-“有桥相连” C D A B A C B D
图建模：在一个中国象棋棋局中： ·进攻方：马如何才能以最快的速度去将军？ ·防守方：如何才能进行有效的防守？ 湘深
图建模：在一个中国象棋棋局中： • 进攻方：马如何才能以最快的速度去将军？ • 防守方：如何才能进行有效的防守？
如何定义图这个数学概念？ 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∈V 义有向图？
如何定义图这个数学概念？ G = (V ,E ) E = {{u,v}| u,v V } 如果要定 义有向图？
如何用图进行问题建模？ ·构造图节点 ·确定什么作为图节点？ ·构造图中的边 ·确定什么作为图中的边？ ·用图中数学语言重述待解问题 ·从自然语言到形式（数学）语言
如何用图进行问题建模？ • 构造图节点 • 确定什么作为图节点？ • 构造图中的边 • 确定什么作为图中的边？ • 用图中数学语言重述待解问题 • 从自然语言到形式（数学）语言