资源描述：
《graphtheory图论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、图论王涛Email:wtnk2006-paper@yahoo.com.cn河南大学数学与信息科学学院2010年7月16日王涛(河南大学)图论2010年7月16日1/25图的基本概念一个图?是一个有序对(?(?),?(?))，这里?(?)是图?的顶点集，?(?)是和?(?)不交的图?的边集，加上一个关联函数?,它使每条边对应图中的两个点(这两个点不需要是不同的)。如果?是图?的一条边，它关联的两个点是?,?，则称?连接点?和?,且?和?是边?的两个端点。王涛(河南大学)图论2010年7月16日2/25图的基
2、本概念?1?(?)={?1,?2,?3,?4,?5}?12??3?(?)={?1,?2,?3,?4,?5,?6,?7,?8}?2?3?(?1)={?1,?2};?(?2)={?1,?3}?4?5??7?(?3)={?2,?3};?(?4)={?2,?3}6?(?5)={?2,?4};?(?6)={?2,?5}?4??58?(?7)={?3,?5};?(?8)={?4,?5}王涛(河南大学)图论2010年7月16日3/25两个端点相同的边称为环(loop)，端点不同的边称为连杆(link)。如果两条或者多条
3、边的端点相同，则称这些边是平行边。例如：在上例中边?3和?4是一对平行边。一个没有环、没有平行边的图成为简单图（simplegraph）。一个无环，但是允许有平行边的图成为多重图。王涛(河南大学)图论2010年7月16日4/25与图相关的概念和约定一条边的两个端点称为与这条边是关联的(incident)若两个点与同一条边相关联,则称两个点是邻接点.关联于同一点的两条边叫邻接边.王涛(河南大学)图论2010年7月16日5/25与图相关的概念和约定一条边的两个端点称为与这条边是关联的(incident)若两个
4、点与同一条边相关联,则称两个点是邻接点.关联于同一点的两条边叫邻接边.?1?5?2?4?3Figure:例如,?3与?4"是邻接点王涛(河南大学)图论2010年7月16日5/25与图相关的概念和约定一条边的两个端点称为与这条边是关联的(incident)若两个点与同一条边相关联,则称两个点是邻接点.关联于同一点的两条边叫邻接边.?1?5?2?23?4?3?34Figure:例如,?23与?34"是邻接边王涛(河南大学)图论2010年7月16日5/25与图相关的概念和约定不与任何点相邻接的点,称为孤立点
5、.只有一个顶点的图称为平凡图(trivialgraph)，否则称为非平凡图(nontrivialgraph)。仅由孤立结点组成的图叫零图。?1?5?2?4?3(a)孤立点:?5王涛(河南大学)图论2010年7月16日6/25与图相关的概念和约定不与任何点相邻接的点,称为孤立点.只有一个顶点的图称为平凡图(trivialgraph)，否则称为非平凡图(nontrivialgraph)。仅由孤立结点组成的图叫零图。?1?′1?5?′2?2′?4?4?3?′3(a)孤立点:?5(b)零图王涛(河南大学)图论20
6、10年7月16日6/25Definition在图?=⟨?,?⟩中,与顶点?相关联的边数,称为该顶点的度数,记作deg(?).王涛(河南大学)图论2010年7月16日7/25Definition在图?=⟨?,?⟩中,与顶点?相关联的边数,称为该顶点的度数,记作deg(?).⃒称(?)=max{deg(?)⃒?∈?(?)}为图?的最大度;王涛(河南大学)图论2010年7月16日7/25Definition在图?=⟨?,?⟩中,与顶点?相关联的边数,称为该顶点的度数,记作deg(?).⃒称(?)=max{d
7、eg(?)⃒?∈?(?)}为图?的最大度;⃒称?(?)=min{deg(?)⃒?∈?(?)}为图?的最小度.王涛(河南大学)图论2010年7月16日7/25Definition在图?=⟨?,?⟩中,与顶点?相关联的边数,称为该顶点的度数,记作deg(?).⃒称(?)=max{deg(?)⃒?∈?(?)}为图?的最大度;⃒称?(?)=min{deg(?)⃒?∈?(?)}为图?的最小度.约定:每个环在其对应的顶点上,度数要计算两次.王涛(河南大学)图论2010年7月16日7/25Definition在图?=
8、⟨?,?⟩中,与顶点?相关联的边数,称为该顶点的度数,记作deg(?).⃒称(?)=max{deg(?)⃒?∈?(?)}为图?的最大度;⃒称?(?)=min{deg(?)⃒?∈?(?)}为图?的最小度.约定:每个环在其对应的顶点上,度数要计算两次.例如左图?中,各结点度数为:?deg(?)=2;deg(?)=3;??deg(?)=2;deg(?)=2;deg(?)=5.??王涛(河南大学)图论2010年7月16日7/25De
