从图论角度看网格

网格 图论

网格的简单分类

数值计算中通常要把物理区域分解为很多简单区域的集合, 这个集合称为网格. 网格中的简单区域称为网格单元, 简称单元. 根据单元的类形不同, 网格的分类如下:

1. 2D 网格
   
   • 三角形网格
   • 四边形网格
   • 多边形网格
2. 3D网格
   
   • 四面体网格
   • 六面体网格
   • 多面体网格

同一个网格中可以存在不同的单元类型, 这类网格称为混合网格.

网格是一种特殊的图

如果以图来描述网格节点之间的连接关系, 则:

1. 这样的图有什么样的特点或性质?
2. 这个图对应的邻接矩阵或Laplacian 矩阵满足什么样的条件?
3. 给定一 $N$ 个节点, 以及节点度的要求和节点之间的连接关系, 能否构造一个算法快速生成一个可以做为网格的图.

三角形网格图

给定一个三角形网格 $T$, 其所有节点的集合记为 $V$, 所有边的集合记为 $E$, 则可得到一个图 $G =(V,E)$.

• 两个相邻的节点, 至少有一个, 最多有两个共同的邻居节点.
• 两个不相邻的节点, 最多有一个共同的邻居节点.