图论是离散数学的一个重要分支，主要研究的是图这种数据结构。图论在计算机科学中扮演着核心角色，因为它可以用来模型化和解决各种实际问题，如电路设计、网络优化、路径查找、数据结构设计等。在本课件中，我们将深入探讨无向图和有向图的基本概念。
无向图是一个由顶点和边组成的三元组 `<V,E,φ>`，其中`V`是非空集合，表示顶点集，`E`是与`V`无交的集合，代表边集，而`φ`是将`E`映射到`V`上无序对的关联函数。无向图的边没有方向性，意味着它们连接的两个顶点之间可以双向通行。例如，一个无向图可能包含四个顶点`{u, v, w, x}`和六条边，这些边通过`φ`函数定义了顶点之间的连接。
无向图可以直观地用图形表示，顶点通常用圆圈表示，边用连接圆圈的线段描绘。在实际应用中，无向图常用于描绘不区分方向的关系，比如社交网络中人与人之间的朋友关系。
接下来，我们讨论有向图，它也是由顶点和边组成的三元组 `<V,A,φ>`，但这里的`A`是弧集，边是有方向的，即每个边（弧）都有一个起点和终点。`φ`函数将弧映射到`V`上的有序对。有向图的图形中，边会带箭头指示方向，如从`u`到`v`的弧表示只能单向通行。例如，一个有向图可能包含三个顶点`{u, v, w}`和六条弧，定义了特定的起点和终点。
有向图广泛应用于需要考虑方向性的问题，比如在计算机网络中表示数据包的传输方向，或者在逻辑设计中描述电路信号的流动。
此外，课件还提到了定向图和基础图的概念。定向图是指将无向图的每条边赋予方向，形成有向图；而基础图则是从有向图中去除所有边的方向，得到一个无向图。这对于分析图的性质和转换非常有用。
赋权图是图论中的一个重要扩展，它为图的边或弧分配了权重，通常为实数值。赋权无向图和有向图分别对应于无向边和有向弧的权重。权重可以代表成本、距离、容量等，用于优化问题，如最短路径问题、最小生成树问题等。
图论是理解和解决复杂问题的强大工具，无论是无向图还是有向图，它们都是现实世界问题的抽象模型。通过学习图论，我们可以更好地理解和设计算法，解决计算机科学和其他领域中的诸多挑战。
