学位论文 > 优秀研究生学位论文题录展示
化学及网络中的某些图论问题的研究
作 者: 潘向峰
导 师: 徐俊明
学 校: 中国科学技术大学
专 业: 应用数学
关键词: Randi(?)指数 匹配 树 单圈图 下界 直径 容错路由选择 幸存路径图 笛卡尔乘积
分类号: O157.5
类 型: 博士论文
年 份: 2006年
下 载: 260次
引 用: 0次
阅 读: 论文下载
内容摘要
正如我们所知道的,图论中的图代表很多含义。因此,图论有很多方面的应用,例如,如果一个简单无向图G=(V,E)的每个顶点代表分子中的一个原子,每条边代表原子之间形成的化学键,这种图就叫分子图。分子拓扑指数以及分子图的不变量的研究是现代化学图论中最活跃的研究领域之一。它们能够被用来描述有机化合物的物理化学特性尤其是药理特性。自从1947年H.Wiener提出第一个分子拓扑指数即Wiener指数以来,数百种分子拓扑指数,包括Randi(?)指数以及广义Randi(?)指数,在数学和化学文献中被研究。这里,图G的广义Randi(?)指数定义为 Wα(G)=sum from=(u,v)∈E[d(u)d(v)]α其中d(u)表示顶点u的度并且α为不等于0的实数.特别地,w-1/2(G)称为图G的Randi(?)指数. 除此之外,我们也通常用一个连通的(有向或无向)图G=(V,E)作为互连网络的拓扑结构,这时图G的顶点代表网络中的组件,组件之间的通信联系用相应顶点之间的连线来表示。网络中的容错路由选择的研究是网络中图论问题的研究的一个重要方向。设x和y是(强)连通(有向)图G=(V,E)中不同的顶点,PG(x,y)是G中(x,y)-路之集,P(G)={PG(x,y):x,y∈V,x≠y),B=V×V\{(x,x):x∈V}。G中路由选择定义为映射ρ:B→P(G),(x,y)→ρ(x,y)∈PG(x,y)。也就是说,映射ρ给B中的每一点对(x,y)都指定了一条(x,y)-路ρ(x,y)。ρ(x,y)称为路径,网络中的路由选择ρ是预先设计好的,因而必须通过ρ指定的那些路径来传输所有的数据。因此,当容错网络的某些结点和(或)连线发生故障时,通过那些包含这些结点(作为内部点)和(或)连线的路径来传输数据就不可能。但仍可以通过一系列幸存的路径传输数据。为了使数据传输的时间不至于太长,经过的幸存路径应该尽可能地少。对于具有给定路由选择ρ且顶点和边(或弧)故障F可能发生的通信网络G。幸存路径图的直径D(R(G,ρ)/F)是一个重要的网络容错参数,它直接反映数据传输延迟时间。 本文主要研究化学图论中的Randi(?)指数和广义Randi(?)指数以及网络中的容错路由选择问题。全文共分为五章。 第一章除了介绍一些图论术语外,还介绍了我们所研究的问题的背景以及一些已知结果。
|
全文目录
摘要 5-7 Abstract 7-9 常用记号表 9-11 第一章 预备知识 11-25 1.1 图论术语的介绍 11-15 1.1.1 图的基本概念 11-13 1.1.2 笛卡尔乘积图 13-15 1.2 Randi(?)指数的介绍 15-20 1.2.1 分子图的拓扑指数 15-18 1.2.2 Randi(?)指数及其推广 18 1.2.3 一些已知结果 18-20 1.3 网络容错路由选择的介绍 20-25 1.3.1 网络与图 20 1.3.2 网络的路由选择 20-22 1.3.3 容错网络的路由选择 22-25 第二章 树的广义Randi(?)指数 25-53 2.1 一些已知结果 25-27 2.2 几个引理 27-35 2.3 主要结果 35-53 2.3.1 -1/2≤α 35-39 2.3.2 α>0 39-53 第三章 单圈图的广义Randi(?)指数 53-75 3.1 具有k个悬挂点的单圈图的Randi(?)指数 53-60 3.2 具有给定边数的最大匹配的单圈图的Randi(?)指数 60-68 3.3 一般单圈图的广义Randi(?)指数的下界 68-75 第四章 笛卡尔乘积图中的容错路由 75-85 4.1 准备 75-77 4.2 我们的结果 77-85 第五章 结束语 85-89 5.1 本文的主要结果 85-87 5.2 有待研究的问题 87-89 参考文献 89-95 作者攻读博士学位期间完成论文目录 95-97 致谢 97
|
相似论文
- 基于巨磁阻抗效应磁测传感器及地磁匹配算法研究,P318
- 卫星光通信粗瞄控制系统的设计及故障诊断,V443.1
- 病险水库溃坝概率分析方法研究,TV697
- 开关磁阻发电机供电系统仿真分析,TM31
- 支持XML数据查询的F&B索引结构的研究,TP311.13
- 图像拼接技术研究,TP391.41
- 高效精确字符串匹配算法的研究与实现,TP391.41
- 多邮件自动文摘的关键技术研究,TP391.1
- 基于串核的蛋白质分类算法的研究与实现,TP301.6
- 红外图像匹配技术研究,TP391.41
- 基于支持向量机的故障诊断方法研究,TP18
- 机器人自动巡检系统中图像配准与图像匹配问题的研究,TP242.62
- 紫金山树木菌根多样性的调查分析,S718.81
- 新疆油田地面工程造价指标和管理信息系统的研究与应用,F284
- 鸡传染性支气管炎病毒河南地方株分离鉴定及HN104株与HN091株全基因组序列测定,S852.65
- 树鼩和猕猴精子冷冻保存工艺的创建和优化的研究,S865.1
- φ38脉冲筛板柱液滴直径分布的研究和模拟,TQ028.3
- 果胶高效降解菌株的紫外诱变选育、生物特性及其生物脱胶应用研究,TS713
- 梨树枝梢处理及高接换种技术研究,S661.2
- 古树名木综合价值评价研究,S788
- 树突状细胞在多柔比星诱导的大鼠肾纤维化模型中的作用,R692.5
中图分类: > 数理科学和化学 > 数学 > 代数、数论、组合理论 > 组合数学(组合学) > 图论
© 2012 www.xueweilunwen.com
|