单循环赛赛程安排的一个图论方法

利用图论的边着色理论建立了一个赛程安排的数学模型 .首先建立 n支球队与完全图 Kn的 n个顶点间的一一对应 ,把球队 Ai和 Aj间的比赛关系抽象成 Kn的顶点 i和 j间的边 ( i,j) .然后分别构造出了图K2 m- 1和 K2 m的正常 2 m-1边着色 .从而给出了各球队每两场比赛间得到的休整时间最均等 ,休整的间隔场次数达到上限值 n2 的一个赛程安排方案     

关于图的L(3,2,1)-标号问题

图G的L( 2 ,1 )标号是一个从顶点集V(G)到非负整数集的函数f(x) .使得若d(x ,y) =1 .则｜f(x) -f(y) ｜≥ 2 ;若d(x ,y) =2 ,则｜f(x) -f(y)｜≥ 1 .图G的L( 2 ,1 )标号数λ(G)是使得G有max{f(v) ∶v∈V(G) }=k的L( 2 ,1 )标号中的最小数k .本文将L( 2 ,1 ) 标号问题推广到更一般的情形即L( 3,2 ,1 ) 标号问题 .我们首先定义了图G的顶点 3 着色及图的 3 色数 χ3 (G)等有关概念 ,并推导出 3 色数 χ3 (G)的上界 ;然后根据 χ3 (G)与λ3 (G)的关系 ,得出了对一般图G ,有λ3 (G) ≤ 3maxH Gδ(H) (Δ2 -Δ 1 )这一一般关系式 ;最后证明了对一般平面图G ,有λ3 (G)≤ 1 5(Δ2 -Δ 1 ) ,并得出了其它几类平面图的λ3 (G)的上界 .     

图的树宽的结构性结果

图G的树宽是使得G成为一个k-树的子图的最小整数k．树宽的算法性结果在图子式理论及有关领域中已有深入的研究．本文着重讨论其结构性结果，包括拓扑不变性、子式单调性、可分解性、刻画问题、与其它参数的关系及由此引伸出的性质．     

两类图簇的伴随多项式的因式分解及色性

令Sk 1表示k 1阶星图,φ^*(2k,n)表示2Sk 1的两个k度点分别与路Pn的两个1度点重迭后得到的图．对于1≤i≤2k n=1,用Srq 2^*(i)表示rφ^*(2k,n)的每个分支的第i个顶点依次与Sr 1的r个1度点重迭后得到的新图；Гpq 1^*(i)表示pφ^*(2k,n)的每个分支的第i个顶点及其对称点依次与S2p 1的2p个1度点配对且重迭后得到的新图．我们通过研究这两类新图与一定数目的孤立点组成的并图的伴随多项式的因式分解，证明了上述并图的补图的色等价图的结构定理．     

组合计数的群论与计算机方法

本文综述组合数学和图论中解决计数问题的群论与计算机方法及其最新发展。传统的计数方法得到有限的计数公式或递推公式等，然而许多复杂的问题很难得到有限的表达式，即使能得到，公式也往往非常复杂。由于计算机技术的发展不仅使复杂的计数公式有了实际意义，而且可以设计恰当的计算方法进行数值计算，使计数问题有更为广阔的发展领域。另一方面，为了计算不同构的图或组合结构，最有效的方法是群论方法，因此把群论方法与计算机方     

矩阵对角相似的图论判别法

本文证明了任意两个ｎ阶复矩阵Ａ和Ｂ为对角相似的充要条件是：它们有相同的伴随有向图，并且以此有向图为基础有向图，以Ａ和Ｂ的对应非零元素比值为弧权值的赋权有向图满足“无向圈平衡条件”。我们还给出了矩阵对角相似条件在非负矩阵谱理论研究中的一个应用。     

覆盖数不超过3的图上渡河问题

1000多年前,英国著名学者Alcuin曾提出一个古老的渡河问题,即狼、羊和卷心菜的渡河问题。2006年,Prisner把该问题推广到任意的冲突图上,考虑了一类情况更一般的渡河运输问题。所谓冲突图是指一个图G=(V,E),这里V代表某些物品的集合,V中的两个点有边连结当且仅当这两个点是冲突的,即在无人监管的情况下不允许留在一起的点。图G=(V,E)的一个可行运输方案是指在保证不发生任何冲突的前提下,把V的点所代表的物品全部摆渡到河对岸的一个运输方案。图G的Alcuin数定义为它存在可行运输方案时所需船的最小容量。本文讨论了覆盖数不超过3的连通图的Alcuin数,给出了该类图Alcuin数的完全刻画。     

有向S—回路和有向S—迹

本文给出了有向生成回路和有向生成迹的几个充分条件。 设G为强连通1—图,无环,n阶。对于G的任两不相邻顶点x,y。①如果 d(x)+d(y)≥2n+1。那么对于G的任两顶点u和v,或有u-v有向S-迹,或有v-u有向S-迹。②如果 d(x)+d(y)≥2n-3。那么G含有向S-回路。     

数学基础课程图论的课程思政探索与实践

全面推进课程思政建设是落实立德树人根本任务的战略举措,新时代的大学教育更加注重专业教育和拔尖创新人才的培养,更加凸显课程思政的重要性.作为一门专业基础课程,图论具有重要的理论研究价值和广阔的应用价值.以研究生图论课程为例,介绍了如何将思政元素引入课堂教学,培养学生数学核心素养的探索与实践的能力.