图的基本概念：无向图与有向图

"本资源主要介绍了图的基本概念，包括无向图、有向图的定义，顶点的度数，图的同构，完全图，正则图，子图和补图的概念，以及图的图形表示。" 在离散数学中，图是一个重要的概念，它在计算机科学和网络分析等领域有着广泛应用。本章节详细阐述了图的基本概念。首先，图被定义为一个有序的二元组<V，E>，分为无向图和有向图两种类型。无向图的边集E是顶点集V与自身无序积的多重子集，而有向图的边集E则是V的笛卡尔积的多重子集。在无向图中，边没有方向，而在有向图中，边具有明确的起点和终点。 例如，一个五顶点的无向图G，其顶点集V={v1, v2, v3, v4, v5}，边集E包含了一些自环和重复的边，如(v1, v1)、(v2, v3)、(v2, v5)等。另一方面，一个四顶点的有向图D，其顶点集V={a, b, c, d}，边集E包含了多个重复的有向边，如<a, b>和<a, d>。 图的表示通常通过图形化，用顶点（小圆圈或实心点）代表顶点，无向边用线段连接，有向边则用带箭头的线段表示。图的某些特定属性，如顶点的度数，是指与一个顶点相连的边的数量。握手定理指出，无向图中所有顶点的度数之和等于边数的两倍。 图的同构是指两个图在结构上是相同的，即存在一个一一对应的顶点映射，保持边的关系不变。完全图是指图中任意两个不同的顶点间都有边相连，而正则图是指图中每个顶点的度数都相同。子图是原图的一个部分，包含原图的部分顶点和这些顶点间的边，补图则是通过去掉原图中所有边而形成的图。 在描述中提到了图的可图化问题，这涉及到哈密顿路径和欧拉路径的概念。定理14.3指出，某些边数配置（如(3,3,2,1)和(3,2,2,1,1)）是无法形成无环遍历的，因此是不可图化的；而其他配置（如(3,3,2,2)和(3,2,2,2,1)）则是可以形成无环遍历的，因此是可图化的。 此外，本章还涵盖了图的矩阵表示和图的运算等内容，这些都是图论研究的基础。通过学习这些基础知识，可以更好地理解和解决涉及图的复杂问题，如网络路由、社交网络分析、数据结构设计等。