目录
一笔画问题
一笔画问题是图论中一个著名的问题。一笔画问题起源于柯尼斯堡七桥问题。数学家欧拉在他1736年发表的论文《柯尼斯堡的七桥》中不仅解决了七桥问题，也提出了一笔画定理，顺带解决了一笔画问题Janet Heine Barnett, 。一般认为，欧拉的研究是图论的开端。 与一笔画问题相对应的一个图论问题是哈密顿问题。.
查看 图的遍历和一笔画问题
广度优先搜索
广度优先搜索算法（Breadth-First-Search，縮寫為BFS），又譯作寬度優先搜索，或橫向優先搜索，是一種圖形搜索演算法。簡單的說，BFS是從根節點開始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。广度优先搜索的实现一般采用open-closed表。.
查看 图的遍历和广度优先搜索
哈密顿图
哈密顿图（Hamiltonian path，或Traceable path）是一個無向圖，由天文学家哈密顿提出，由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次。在图论中是指含有哈密顿回路的图，闭合的哈密顿路径称作哈密顿回路（Hamiltonian cycle），含有图中所有顶点的路径称作哈密顿路径。 哈密尔顿图的定义： G.
查看 图的遍历和哈密顿图
图
图可以指：.
查看 图的遍历和图
图论
图论（Graph theory）是组合数学的一个分支，和其他数学分支，如群论、矩阵论、拓扑学有着密切关系。图是图论的主要研究对象。图是由若干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物，连接两顶点的边则用于表示两个事物间具有这种关系。 图论起源于著名的柯尼斯堡七桥问题。该问题于1736年被欧拉解决，因此普遍认为欧拉是图论的创始人。 图论的研究对象相当于一维的单纯复形。.
查看 图的遍历和图论
邮递员问题
邮递员问题（也称邮路问题，Route Inspection Problem，或中国邮路问题,China Route Inspection Problem，或中国邮递员问题Chinese Postman Problem）是一个图论问题。此問題為在一個連通的無向圖中找到一最短的封閉路徑，且此路徑需通過所有邊至少一次。 簡單來說，邮递员问题就是在一個已知的地區，郵差要設法找到一條最短路徑，可以走過此地區所有的街道，且最後要回到出發點， 此問題是圖遍歷問題的一種。无向图的中国邮路问题是容易解决的，是P问题；而有向图的中国邮路问题是NP完全问题。中国邮递员问题由管梅谷教授在1960年提出，而美國國家標準和技術研究院（NIST）的 Alan Goldman 首先將此問題命名为中国邮路问题。.
查看 图的遍历和邮递员问题
欧拉图
欧拉图，部分文稿也称欧氏图，是类似文氏图的一种图，但是不必须包含所有的区（这里的区定义为两个或更多轮廓线的交集区域）。所以欧拉图可以定义论域，就是说它可以定义一个系统，其中有特定交集是不可能的或不考虑的。 所以，包含“动物”、“矿石”和“四足”这些性质的文氏图，必须包含在其中有同时是动物、矿石和四足的某种东西的那个交集。因此文氏图展示了所有可能的合取组合。 可以构造出欧拉图，使得在其中这些无意义的交集不存在，以此为这个主题定义了论域。换句话说，欧拉图可以表示简并之后的那些合取。 对欧拉图的一个现代扩展是蜘蛛图，它向欧拉图增加了可以连接的存在点。这给予欧拉图析取特征。欧拉图原先已有合取特征（就是说区定义了，在該区中存在的对象，都有着合取起来的那些性质）。所以蜘蛛图允许使用欧拉图配備逻辑或的条件。.
查看 图的遍历和欧拉图
深度优先搜索
深度优先搜索算法（Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。 深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。 因发明“深度优先搜索算法”，約翰·霍普克洛夫特与罗伯特·塔扬共同获得计算机领域的最高奖：图灵奖。.
查看 图的遍历和深度优先搜索
旅行推销员问题
旅行推销员问题（最短路径问题）（Travelling salesman problem, TSP）是这样一个问题：给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。它是组合优化中的一个NP困难问题，在运筹学和理论计算机科学中非常重要。 TSP是与的一种特殊情况。 在计算复杂性理论中，TSP的做决定版本（其中，给定长度 L，任务是决定图中是否有路径比 L 还要短）属于NP完全问题。因此随着城市数量的增多，任何TSP算法最坏情况下的运行时间都有可能随着城市数量的增多超多项式（可能是）级别增长。 问题在1930年首次被形式化，并且是在最优化中研究最深入的问题之一。许多优化方法都用它作为一个基准。尽管问题在计算上很困难，但已经有了大量的启发式和精确方法，因此可以完全求解城市数量上万的实例，并且甚至能在误差1%范围内估计上百万个城市的问题。 甚至纯粹形式的TSP都有若干应用，如企划、物流、芯片制造。稍作修改，就是DNA测序等许多领域的一个子问题。在这些应用中，“城市”的概念用来表示客户、焊接点或DNA片段，而“距离”的概念表示旅行时间或成本或DNA片段之间的相似性度量。TSP还用在天文学中，观察很多源的天文学家希望减少在源之间转动望远镜的时间。许多应用（如资源或时间窗口有限）中，可能会加入额外的约束。.
查看 图的遍历和旅行推销员问题