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

"二部图举例-图的基本概念" 图论是离散数学的一个重要分支，主要研究由顶点和边构成的各种结构。本章节主要介绍的是图的基本概念，包括无向图、有向图、完全图、正则图、子图以及补图等。 首先，我们来理解“图”的定义。图可以被形式化地表述为一个有序的二元组，即一个无向图G=<V,E>，其中V是非空集合，称为顶点集，而E是V与V的无序积的多重子集，称为边集。每条边是顶点对的形式，如(a,b)。无向图中的边没有方向，因此(a,b)等价于(b,a)。而有向图D=<V,E>的边集E是V与V的笛卡尔积的多重子集，边是有方向的，如<a,b>表示从顶点a指向顶点b的边。 在图的表示中，通常用圆圈代表顶点，无向边用连接圆圈的线表示，有向边则用带箭头的线表示。例如，例14.1给出了一无向图G和一有向图D，它们的顶点和边集被具体定义，并要求画出它们的图形。 在图的一些基本概念中，我们关注的是顶点的度数，它是指一个顶点与其他顶点相连的边的数量。握手定理指出，图中所有顶点的度数之和等于边数的两倍，因为每条边连接了两个顶点，贡献了两次度数。如果每个顶点的度数都相同，那么这个图被称为正则图。 完全图K_n是具有n个顶点的图，其中任意两个不同的顶点之间都有边相连。例如，K6是含有6个顶点的完全图，而K3,3则是特定类型的图，它有3个顶点集，每组内部无边，而不同顶点集之间完全连接，形成3对边。K2,3是另一个例子，它由2个顶点集构成，每组内部无边，不同顶点集间有3条边连接。 子图是原图中的一部分，包含原图的部分顶点和这些顶点间的部分边。补图是通过去掉原图中所有存在的边而形成的新图，或者在没有边的地方添加边，使得原图中相邻的顶点在补图中不再相邻，反之亦然。 学习图的基本概念对于理解和应用图论至关重要，这涉及到网络、算法、数据结构等多个领域。通过深入研究图的性质，我们可以解决诸如最短路径、最大流最小割等问题，这些都是计算机科学和数学中的核心问题。