图的线性荫度及线性2-荫度.pdf

THELINEAR YTICIRANDoBRA EHT 2一 of arboricitygraphs． Let the1ine8r the linear f口(G)，fa2(G)，盯ld△(G)denote8rboricityI 2．盯茎sg!二!中 ^壤l互；矗i善i耋晷荸苎妻毒；墨雩i一千扫笼霎?≤量囊矗l副l耋窜氅垂薹il一辇鼻IIh莲!；妻§_葶蓬三钉世!} 疆二弼 RAENIL 2-ARBoRICITYoF GRAPHS In this thesi8，we the1inear arboricityan 一、 绪论 (一)、基本概念 在本节中，我们定义一些本文要用到的图论的基本术语与符号．我们用lSi 表示集合s中的元素个数．用f01，101分别表示不小于$的最小整数和不大于z 的最大整数． 一个尤向图是一个有序对G=(KE)，其中矿是一个有限集合，E是y中的 _i同冗素的无序对的集合．y中的元素叫做图G的顶点，E中的元素叫做图G 的边我们通常用y(G)，E(G)分别表示图G的顶点集合和边集合．没有重边和 环的图叫做简单图．除非特别指出，本文研究的图均指有限简单无向图．通常称 含有n个顶点的图为n阶图．对于图G中的顶点u和，若边e=伽∈E(G)，则 称u和u相邻，¨和互为邻点；称u和是e的端点，u和分别与e关联．若G 的边e和，有一个公共端点，则称e和，相邻．在图G中与顶点札相邻的顶点的 全体叫作u的邻域，记作Ⅳ＆(让)．称l|ⅣG(u)I为顶点Ⅱ的度数，记作dG(钍)．称度数 为％的顶点为％一点．G中顶点的度中最大者和最小者分别称为G的最大度和最 小度，分别记作△(G)和6(G)．度数为O的顶点称为孤立点，度数为1的顶点称 为悬挂点(叶子)，与悬挂点相关联的边称为悬挂边．在不产生混淆的情况下，我 的一个予图．对ry’∈y(G)，我们把图G中属于y’的顶点以及与y’中的点关 联的边都删除所得到的图记作G＼∥或G一∥．对于，口∈y(G)，伽譬F(G)，我 们把在图G中连接顶点u，所得到的图记作G+{伽)．对于∥∈y(G)，我们把 I=|!{y’作为顶点集，E={eI e=up∈E(G)，u，∈y‘)作为边集的图叫做G中由 顶点子集y’导出的子图，记作G【y’】．设Gl=(K，置)，G2=(％，易)是两个图，称 u 图G=(Ⅵuy2，ElE2)为图Gl和图G2的并，记作Gu日． 图G的一条途径是一个有限非空的点边交替序列叫=咖8l”l印…ek饥，使得 对l≤t≤≈，et=饥一l叫．若途径掣上的顶点％，”l，吨，…，％互不相同，则称为 一条路，记作R．称如，％分别为路R的起点和终点．称起点和终点相同的路 为圈．称路(圈)上的边数为路(圈)的长度，常用只，Q表示点数为≈的路和圈． 称图G中最短圈的长度为G的围长，记作9(G)．图G中两顶点u和的距离是 指G中从u到的最短路的路长，记作如(u，口)，简记为d(u，)．任何两个顶点间 都有一条路连接的图称为连通图，否则称为不连通豳．一个图G的极大连通分 支称为G的分支．连通图的连通分支是1，记G，的分支个数为u(G)．对于顶点 大连通分支为G的块．若G连通且不含圈，则称此图为一棵树，常用死表示顶 点数为n的一棵树．对于连通图G=(KE)，y’￡y使得G一∥不连通，则称∥ 是G的点割集．若I∥I=≈，则称∥为舡点割集．对于G≠‰，称图G中顶点数 最少的点割集的点数为图G的连通度，记作K(G)．定义‰的连通度为礼一1，不 连通图的连通度为0．若G满足K