关于六阶图与星的笛卡儿积交叉数

通过在完全图K4的某一条边上增加2个顶点得到一个六阶图F.分别连结F六个顶点与其他n个顶点得到一类特殊的图Hn.证明Hn的交叉数为Z(6,n)+n并由此确定且证明F×Sn的交叉数为Z(6,n)+2n.

一个六阶图与星的笛卡儿积交叉数(英文)

拓展了目前关于星与低阶图的笛卡儿积交叉数的某些结论,确定了1个特殊6 -阶图与星K1,n的笛卡儿积交叉数为z(6,n)+4n,并给出了1个有在K2,4,n中加入2条边分别联结K2,4,n中2对n+2度点得到的1个特殊图类Hn的交叉数.

G_7×S_n的交叉数

计算并证明了五阶图G7与星Sn的笛卡尔积交叉数cr(G7×Sn)=Z(5,n)+[n/2],这一结果填补了MriánKlesc关于五阶图与星的笛卡尔积交叉数的一处空白.

一个六阶图与星图的笛卡儿积的交叉数(英文)

图的交叉数已被证明是一个NP-完全问题,由于其难度,要知道图的确切交叉数是非常困难的.到目前为止,只知道少数图的交叉数,其中大部分是特殊图的笛卡儿积图的交叉数,比如路,圈以及星图与点数较"少"的图的笛卡儿积交叉数.在这些基础上,应用数学归纳法,把相关结果拓展到1个6-阶图G,并确定它与星的笛卡儿积交叉G×SnZ(6,n)+3[n/2].

图论及其算法在数学建模中的应用

图论从诞生至今已近300年,但很多问题一直没有很好地解决.随着计算机科学的发展,图论又重新成为了人们研究讨论的热点,这里通过提出实际问题、将问题转化并建立模型的方式简单介绍图论及其算法在数学建模中的一些应用.主要有求最短路径的Dijkstra算法、Floyd算法,求最佳匹配的匈牙利算法、KM（Kuhn-Munkres）算法,求最小生成树的Kruskal算法、Prim算法,求网络最大流的Ford-Fulkerson标号算法,求解图的色数的禁忌搜索算法,求平图的DMP平面性算法,求最优邮路的Edmonds-Johnson算法,求解TSP问题的Christofides近似算法等.

几个六阶图与星S_n的笛卡尔积交叉数

分别连结六阶图G1的6个顶点与其它n个顶点,得到一类特殊的图Hn.运用组合方法、归纳思想及反证法证明了Hn的交叉数为Z(6,n)+2「n/2」,并在此基础上证明G1与星K1,n的笛卡尔积的交叉数为Z(6,n)+2「n/2」;另外,证明了含子图S5的其它6个六阶图与星K1,n的笛卡尔积的交叉数都为Z(6,n)+4「n/2」.