同态

如果两个图G 1和G 2是同构的,则可以通过将G的某些边除以更多的顶点而从同一图'G'中获得每个图。看下面的例子-

同态

通过添加一个顶点将边缘“ rs”划分为两个边缘。

同态1

下面显示的图形与第一个图形同构。

同态与第一个图

如果G 1与G 2同构,则G与G 2同胚,但是反之则不必成立。

  • 具有4个以下顶点的任何图形都是平面的。

  • 任何具有8个以下边缘的图形是平面的。

  • 当且仅当n≤4时,完整图K n是平面的。

  • 当且仅当m≤2或n≤2时,完整的二部图K m,n是平面的。

  • 具有最小顶点数的简单非平面图是完整图K 5

  • 边数最少的简单非平面图是K 3,3

多面图

如果每个顶点的度数≥3,即deg(V)≥3∀V ∊ G,则简单的连接平面图称为多面体图。

  • 3 | V | ≤2 | E |

  • 3 | R | ≤2 | E |