1、图的基本概念

1、图的定义

• 图$G$G是由两个集合$V$V和$E$E组成(记做$G = (V, E)$G=(V,E))：
  $V =$V= {$v_1,v_2,v_3,...v_n,$v1​,v2​,v3​,...vn​,}是由$G$G的结点($vertex$vertex)组成的集合
  $E =$E= {$e_1,e_2,e_3,...e_n$e1​,e2​,e3​,...en​} 是由连接两个结点的边($edge$edge)组成的集合

• (无向图) 若边$e$e(唯一的边)连接结点$v_1$v1​和$v_2$v2​, 则表示为 $e = (v_1,v_2)$e=(v1​,v2​)或 $e = (v_2,v_1)$e=(v2​,v1​)，表示连接结点$v_1$v1​和结点$v_2$v2​的边

• (有向图) 若边$e$e(唯一的边)连接有序结点对$v_1$v1​和$v_2$v2​, 则表示为 $e = (v_1,v_2)$e=(v1​,v2​)，表示一条从结点$v_1$v1​到结点$v_2$v2​的边

(有向图和无向图) $G$G中的一条边连接结点$v_1$v1​和结点$v_2$v2​，则称结点$v_1$v1​和结点$v_2$v2​相关联，结点v1和结点v2是相邻结点

(有向图和无向图) 一般情况下，$E$E和 $V$V都是有限的集合，且 $V$V为非空

完全图

偶图（或二部图、二分图）

补图
设$G$G为简单图，H是一个以$V(G)$V(G)为顶点集的图，且两个顶点在$H$H中邻接当且仅当它们在$G$G中不邻接，则称$H$H为$G$G的补图（$complement\ graph$complement graph）

子图

• 图的生成子图：如果图$G$G的一个子图包含$G$G的所有顶点，称该子图为G的一个生成子图

2、顶点的度

顶点的度及其性质

• 如果一个图的每个顶点都具有相同的度，则称这个图是正则的（$regular$regular）。每个顶点的度均为$k$k的正则图。则称k-正则图($regular \ graph$regular graph)。

握手定理

图的度序列及其性质

3、图的同构

4、图运算

超立方体

5、道路和回路

道路



链（chian）:边均不相同的通道称为链
迹（trail）：边互不相同的链称为迹
道路（path）:顶点均不相同（从而所有的边也不相同）的通道称为道路（$path$path）

回路

• 回路：起点与终点重合的道路叫做回路（$circuit$circuit）或称为圈($circlc$circlc)

6、E图

七桥问题

• 将问题转换为是否为$Euler$Euler图
  
  
  
  

7、H图

解决环球航行问题

举例