图的概念和基本术语
- 一、图的概念
- 二、基本术语
- 1、顶点（Vertex）
- 2、边（Edge）
- 3、无向图（Undirected Graph）
- 4、有向图（Directed Graph）
- 5、加权图（Weighted Graph）
- 6、多重图（Multigraph）
- 7、度（Degree）
- 8、路径（Path）
- 9、简单路径（Simple Path）
- 10、环（Cycle）
- 11、连通图（Connected Graph）
- 12、强连通图（Strongly Connected Graph）
- 13、子图（Subgraph）
一、图的概念
在数学和计算机科学中，图是由顶点（节点）和边（连接）组成的一种数据结构，用于描述对象之间的关系。图是一种广泛应用于许多领域的数学概念，包括计算机科学、网络分析、运筹学、社交网络分析等。
图可以用于表示各种现实世界中的问题，如社交网络中的用户关系、道路网络中的交通流量、电子电路中的连接关系等。它提供了一种灵活和直观的方式来描述对象之间的关联性和结构。
一个图由两个主要要素组成：
1. 顶点（Vertex）
2. 边（Edge）
图可以分为以下几种类型：
1. 无向图（Undirected Graph）
2. 有向图（Directed Graph）
3. 加权图（Weighted Graph）
4. 多重图（Multigraph）
图论是研究图及其性质和应用的数学分支，它提供了许多用于解决与图相关的问题的算法和技术。通过分析图的结构和运用图算法，我们可以解决路径查找、最短路径、最大流、最小割、图匹配等各种实际问题。
二、基本术语
1、顶点（Vertex）
顶点（Vertex）：也被称为节点或结点，是图的基本元素。在图中用圆圈或方框表示，并用唯一的标识符来表示。
2、边（Edge）
边（Edge）：也被称为弧或线，是图中连接顶点的连接线。边可以有方向（有向图）或没有方向（无向图），有权重或无权重。
3、无向图（Undirected Graph）
无向图（Undirected Graph）：图中的边没有方向。如果顶点 A 和顶点 B 之间存在一条边，那么顶点 A 和顶点 B 互相是相邻的。
4、有向图（Directed Graph）
有向图（Directed Graph）：图中的边有方向。如果顶点 A 到顶点 B 之间有一条有向边，那么 A 是 B 的前驱，B 是 A 的后继。
5、加权图（Weighted Graph）
加权图（Weighted Graph）：图中的边有权重或权值。权重可以表示两个顶点之间的距离、代价、容量等概念。
6、多重图（Multigraph）
多重图（Multigraph）：图中允许有多条相同顶点之间的边。这意味着可以存在平行边，即两个顶点之间有多条边。
7、度（Degree）
度（Degree）：表示一个顶点与其相邻顶点之间的连接数。
在无向图中：度是指与顶点相连的边的数量。
在有向图中：分为入度和出度。入度是指指向该顶点的边的数量，出度是指从该顶点指出的边的数量。
8、路径（Path）
路径（Path）：图中的路径是由顶点和边按照一定顺序组成的序列。
路径的长度：是指路径中边的数量。
9、简单路径（Simple Path）
简单路径（Simple Path）：路径中不包含重复顶点的路径。
10、环（Cycle）
环（Cycle）：
在无向图中，环是指至少包含3个顶点，并且第一个顶点和最后一个顶点是相同的路径。
在有向图中，环是指一个顶点到自身的路径。
11、连通图（Connected Graph）
连通图（Connected Graph）：在无向图中，如果两个顶点之间至少存在一条路径，则称这两个顶点是连通的。如果图中的任意两个顶点都是连通的，那么图被称为连通图。
12、强连通图（Strongly Connected Graph）
强连通图（Strongly Connected Graph）：在有向图中，如果任意两个顶点之间都存在双向的路径，则称这个有向图是强连通图。文章来源：https://uudwc.com/A/Evk10
13、子图（Subgraph）
子图（Subgraph）：图的子集，子图中的顶点和边都是原图中的元素。文章来源地址https://uudwc.com/A/Evk10
