图论基础：无向图、有向图与带权图解析

"NOIP普及讲座7-图的基本知识(C++版).pdf" 这篇讲座主要介绍了图论的基础知识，特别是与无向图、有向图和带权图相关的概念，适用于NOIP（全国青少年信息学奥林匹克竞赛）普及组的学习者。讲座首先通过欧拉解决的哥尼斯堡七桥问题引入图论，展示了图论在实际问题中的应用。 1. 图的表示：图通常由顶点（vertices）和边（edges）组成，可以用来表示各种关系。在讲座中提到了几种不同类型的图，包括无向图（Undirected Graph），其中边没有方向；有向图（Directed Graph），其中边具有方向；以及带权图（Weighted Graph），其中边附带有数值权重。 2. 顶点的度、入度和出度：在无向图中，顶点的度（degree）是指与其相连的边的数量。而在有向图中，顶点的入度（in-degree）是指指向该顶点的边数，出度（out-degree）是指从该顶点出发的边数。图论中有几个关于度的重要定理，如所有顶点的度数之和等于边数的两倍，无向图中所有顶点的度数之和总是偶数，有向图中所有顶点的入度之和等于出度之和。 3. 奇点和偶点：奇点是度为奇数的顶点，而偶点是度为偶数的顶点。根据欧拉定理，无向图中奇点的总数必须是偶数，因为每条边连接两个顶点，使得一个顶点的度数增加的同时，另一个顶点的度数也会增加。 4. 欧拉图和欧拉通路/回路：欧拉图是指存在欧拉通路或欧拉回路的图。欧拉通路是通过图中每条边一次且仅一次的路径，而欧拉回路则形成一个闭合路径。欧拉定理指出，存在欧拉回路的条件是图是连通的且没有奇点；若图有奇点，存在欧拉路的条件是图是连通的，且奇点数为0或2，且路径从一个奇点开始并以另一个奇点结束。 5. 哈密尔顿图和哈密尔顿通路/回路：哈密尔顿图是指存在哈密尔顿回路的图，即图中每个顶点恰好出现一次的闭合路径。哈密尔顿通路则是每个顶点只出现一次但不形成闭合路径的路径。尽管哈密尔顿回路的判定问题在图论中是著名的NP完全问题，目前没有找到确定性的、高效的算法来解决。 讲座还包含了几个小练习，例如判断哪些度数分布可能出现在无向图中，以及如何确定图中是否存在欧拉路径或哈密尔顿回路。这些问题旨在帮助学习者理解和应用所学的图论知识。 这份资料为学习者提供了图论基础的清晰介绍，涵盖了图的种类、顶点性质、欧拉图和哈密尔顿图的概念，以及它们在实际问题中的应用，对于参加NOIP普及组的学生来说是一份有价值的参考资料。