图对现实世界问题的建模起着非常重要的作用。例如，可以使用图寻找两座城市之间最短距离的问题进行建模，其中顶点代表城市，边代表两座相邻城市之间的路径和距离。找寻两座城市之间的最短距离的问题就简化为寻找图中两个顶点之间最短路径的问题。
先聊聊哥尼斯堡的七孔桥问题，位于普鲁士的哥尼斯(现俄罗斯的加里宁格勒)被普雷格河分开，该河流经两座岛，这座城市和岛由七座桥相连，问题在于，如何经过每座桥一次且只经过一次，然后返回起点？
首先通过删除所有的街道来提取出哥尼斯堡的地图，然后，将每一块陆地用一个点来代替，这个点称为顶点或者结点，并且将每一座桥用一条线来替换，这条线称为边，这种有顶点和边的称为图。
当看见图的时候，我们会询问是否存在一条从任意顶点出发的路径，这条路径遍历所有的边一次且只有一次，然后返回起始顶点。欧拉证明了这种路径存在的条件是，每个顶点必须拥有偶数条边。因此，哥尼斯堡的七孔桥问题没有解决的方法。
一个图包含了非空的顶点、结点或者点，以及一个连接顶点的边的集合。
图可以是有向的，也可以是无向的。
在有向图中，每条边都有一个方向，表明可以沿着这条边将一个顶点移动到另一个顶点。可以使用有向图来对父/子之间的关系进行建模，其中从顶点A到B的边表示A是B的父亲。
在无向图中，可以在顶点之间双向移动他们。
网友评论