图论_3_矩阵+习题.ppt

图 论 图——基本概念 图、路与连通、最短路、有向图、图的矩阵 Euler图与Hamilton图 树 树、生成树、有向树 平面图　图的着色 平面图、对偶图、顶点着色、面着色 网络　匹配　独立集 图的矩阵表示 定义1　设G是一个无自环的图，υ×ε矩阵 A(G)＝(aij) 称为G的关联矩阵，其中 图G的关联矩阵有下列性质： G中每一边关联两个顶点，所以A(G)中每一列恰好有两个1； 每一行中1的个数是对应顶点的度数； 平行边对应的列全同； 若G有两个分支G1，G２，则适当调整顶点及边的顺序，可使关联矩阵呈块对角形 定义２　设G是无平行边的图，υ×υ矩阵Ｘ(G)＝(xij)称为图G的邻接矩阵，其中 Ｘ(G)是对称矩阵。 定理1　 设G是一个简单图，Ｘ是G的邻接矩阵， 令 Xk＝( )。则 等于顶点vi，vj之间 长度为k的路径数目。 定义３　 设G是一个无平行边的图，υ×υ矩阵 P(G)＝(pij)称为G的路径矩阵，其中 G是连通图 ? P(G)中元素全为1。 定义４　 设D是一个无自环的有向图，υ×ε矩阵A(Ｄ)＝(aij)称为Ｄ的关联矩阵，其中 定义５ 设D是一个无平行弧的有向图，υ×υ矩阵Ｘ(D)＝(xij)称为D的邻接矩阵，其中 习题 证明　空间中不可能有这样的多面体存在，它有奇数个面，而每个面又有奇数条边。 证明　简单图必满足ε≤ 。 证明　在两个或更多个人组成的人群中，总存在这样两人，他们在该人群中的朋友数相同。 写出具有四个顶点的所有非同构简单图。 2n个电话交换台，每个台至少与n个台有直通线路，证明其中任意两台之间可以通话。 图中只有两个奇顶点，则它们必连通。 证明　每顶点皆２度的连通图是圈。 证明　在简单图中，必存在长为δ的路。 证明　G是连通图，当且仅当对于V(G)的任意划分｛V1,V2｝，总存在边e使得e的一个端点在V1中，另一端点在V2中。 证明　若G是简单图，且ε＞ ，则G连通。找出一个边数为 的不连通简单图(υ＞1)。 证明　若G不连通，则～G连通。 证明　若e∈E(G)，则 ω(G)≤ω(G－e)≤ω(G)＋1， 其中，G－e表示从G中去掉边e得到的图。 证明　连通图中，任意两条最长路必有公共顶点。 证明　若e在G的某回路中，则e在G的某圈中。 一个简单图G具有多少个定向图？ 证明定理1。 设D是没有有向圈的有向图， (a)证明　δ－＝0； (b)证明　存在V的一个有序顶点列v1，v2，…，vυ，使得对于1≤i≤υ，D的每条以vi为头的弧在｛v1，v2，…，vυ-1｝中都有它的尾。 设D1，D２，…，Dm是D的双向分支，D的凝图是指 一个有m个顶点w1，w２， …，wm的有向图 ，“ 中存在一条以wi为尾wj为头的弧” 当且仅当 “D中存在 尾在Di中而头在Dj中 的 弧”。 证明 D的凝图不包含有向圈。 *