无向图与有向图的概念及子图解析

本资源主要介绍了图的基本概念，包括无向图和有向图的定义、图的表示方法、子图和补图的概念，以及图的一些基本术语和规定。重点讲解了无序积与多重集合的概念，并给出了两个具体的图示例。 在离散数学中，图是一种重要的数据结构，用于描述对象之间的关系。无向图是一个由顶点集V和无序边集E组成的二元组G=<V,E>，其中边集E是无序积V&V的多重子集。有向图则是由顶点集V和有向边集E组成的二元组D=<V,E>，这里的边集E是笛卡尔积V×V的多重子集。无向图中的边没有方向，而有向图中的边具有方向性。 图可以用图形方式表示，顶点通常用圆圈或点表示，无向边用线段连接，有向边则用带箭头的线段表示。例如，给定了一个无向图G，其顶点集V={v1,v2,v3,v4,v5}，边集E包含(v1,v1)、(v1,v2)、(v2,v3)等多条边；另一个有向图D，顶点集V={a,b,c,d}，边集E包含<a,a>、<a,b>等有向边。 图的某些关键概念包括顶点的度数，即一个顶点与其他顶点相连的边的数量。在无向图中，握手定理指出所有顶点的度数之和等于边数的两倍。图的同构是指两个图在结构上是相同的，只是顶点和边的标记不同。完全图是每个顶点都与其他所有顶点相连的图，正则图是所有顶点具有相同度数的图。 子图是原图中的一部分，包含原图的部分顶点和这些顶点之间的一些边。在例子中，取顶点集V1={a,b,c}，则V1的导出子图G[V1]包含了V1中的所有顶点及它们之间的边。而取边集E1={e1,e3}，则E1的导出子图G[E1]只包含边e1和e3及其相关的顶点。 补图是原图中所有可能的边（不包括已有的边）构成的图。如果在原图中两个顶点之间没有边，那么在补图中它们之间有一条边，反之亦然。 此外，无序积和多重集合的概念被引入来描述边集的构成。无序积允许元素对中的顺序不同，且允许重复，多重集合则是允许元素重复出现的集合，其中元素的重复度表示元素出现的次数。 这个资源提供了图论的基础知识，涵盖了图的定义、性质、表示方法以及子图和补图的概念，对于理解图的理论和应用有着重要的作用。