联树模型在亏格等式证明中的应用

应用联树模型,把图浸入平面,获得这个图的关联曲面,从而获得这个图的嵌入曲面的亏格.应用这个方法,我们证明了2个著名的亏格等式.第1如果e是图G的一条割边,G-e有2个分支G1,G2,那么,g(G1) g(G2)=g(G).其中g(G)表示图G的亏格.第2用H*vK表示图H与K在点v处的结合,即V(H)∩V(K)=v,E(H)∩E(K)=φ.γ(G)表示图G的最小可定向亏格.那么,γ(H*vK)=γ(H) γ(K).     

The Further Results of the Chromatic Uniqueness of Certain Bipartite Graphs K （m,n）- A

With its comprehensive application in network information engineering （e. g. dynamic spectrum allocation under different distance constraints ） and in network combination optimization （e. g. safe storage of deleterious materials）, the graphs＇ cloring theory and chromatic uniqueness theory have been the forward position of graph theory research. The later concerns the equivalent classification of graphs with their color polynomials and the determination of uniqueness of some equivalent classification under isomorphism. In this paper, by introducing the concept of chromatic normality and comparing the number of partitions of two chromatically equivalent graphs, a general numerical condition guarenteeing that bipartite graphs K （ m, n） - A （A belong to E（K （m, n） ） and ｜ A ｜≥ 2） is chromatically unique was obtained and a lot of chromatic uniqueness graphs of bipartite graphs K（m, n） - A were determined. The results obtained in this paper were general. And the results cover and extend the majority of the relevant results obtained within the world.     

因子与奇偶性

本文推广了(g,f)一因子的概念,对次限制子图进一步加进了次的奇偶性限制。主要结果是-个图含有这种奇偶性限制子图的充分必要条件。这个条件推广了Tutte和Lovasz关于f-因子和(g,f)-因子的有关定理。     

两个古老的回路问题

许多人把图论归人应用数学，这种看法很有道理。有些数学领域，例如拓扑学和数论，你得花费不少口舌才能说动别人相信，它们是多么多么重要，与老百姓的生活如何密切相关。图论可不是这样，最没有文化的人也能理解图论的问题，这些问题十分贴近老百姓的日常生活，可能是数字和简单算术之外，群众最熟悉的数学了。     

扩展Meadows模型分析Ad Hoc网络路由协议安全性

目前,Ad hoc网络安全路由协议缺乏有效的形式化分析方法.通过添加基于图论的路由描述和分析方法,文章扩展了Meadows模型的分析能力.使用扩展后的Meadows模型对Ad hoc网络安全路由协议Ariadne进行了分析,分析结果显示Ariadne协议存在产生虚假路由的漏洞,从而也说明了扩展后的Meadows模型能够用于Ad hoc网络安全路由协议的安全性分析.     

基于用户等待时间和带宽需求的改进CSGC算法

从频谱资源紧缺的现状出发,通过对图论着色模型的分析,提出了基于用户等待时间和带宽需求的改进颜色敏感的图论着色(color sensitive graph coloring,CSGC)算法.该算法兼顾用户等待时间和实际带宽需求,使用户在趋于平等的机会获得频谱资源同时,最小化未满足需求总量,保证了系统的公平性,提高了系统的...     

基于有向图的管线网GIS一体化数据模型

针对城市管线网GIS领域特色，引入图论代数相关理论、改进GIS现有网络结构模型组织与表达，提出城市管线网GIS一体化空间数据模型，并实现该模型支持下的强大的地理计算和空间分析功能，最后在“数字城市”管线网GIS共享集成平台和专业管线GIS系统中实现了模型的功能应用。     

树枝状铁路专用线取送车问题的数学模型及算法

对于树枝状铁路专用线直达列车取送车问题，为了尽可能缩短车辆在站停留时间，本文就调机送后等取或单送和送后再取分别研究。通过建立图论和排序论数学模型，给出了树枝状铁路专用线取送车问题的上述两种情况下的简单快速算法。