图论基础

参考 https://blog.csdn.net/Karen_Yu_/article/details/78776354

顶点&边

“一笔画问题”：有一个简单图，有4个顶点，7条边，问：能否遍历所有的边最后回到起点且不会重复经过同一条边。

顶点（Vertex）边（Edge）图（Graph）所以，一个图常常写作G=(V,E) 我们还可能看到这样的形式

V={v1, v2, v3……}

E={e1, e2, e3……}

V是有限非空集合，称为顶点集，其元素称为顶点或结点。 E是有限集合，称为边集，E中每个元素都有V中的结点对与之对应，称为边。

边e既可以是有向的，也可以是无向的。有向边与有序结点对对应，这时称u为e的起点，v为e的终点。无向边与无序结点对对应，u，v称为e的两个端点。

采用图这一名称，是因为他们可以用图形来表示，而这种图形表示有助于人们理解图的许多性质。图论中的大多数定义和概念是根据图形表示提出来的。

如果顶点v是边e的一个端点，则称边e和顶点v相关联（Incident)，反之亦然。

对于顶点u和v，若（u，v）∈E，则称u和v是邻接或相邻（Adjacent）的；

若两条边有共同的顶点，则也称这两条边是相邻的。

两个端点重合的边（度=2），称为环（Loop），端点不重合的边称为连杆（Link）。关联于同一对顶点的两条或两条以上的边称为多重边（Multiple Edge）。

同构 // ?

同构要求：

• 点数一样多，边数一样多

• 度序列相同

各种各样的图