图的st-编号算法研究与实现

摘要

随着数据库技术的成熟以及Internet的发展，数据的种类与数量不断增加，可视化技术将纷繁复杂的海量数据用直观的图形展示出来，有利于发现掩藏在数据背后的信息。可视化技术中除了绘制关注对象的可视属性以外，更重要的问题是如何把这些非空间抽象信息映射为有效的可视化形式。图是一种用来表示抽象信息的数据结构，它非常适合表示那些可以被看作实体及实体之间的关系的信息。用平面图表示抽象信息，可以更好地进行可视化展示，使它们更容易理解。然而，平面图的判定以及平面图绘制问题一直是平面图中的重要问题。
　　 本文主要对平面图判定以及平面图绘制中经常用到的st-编号进行了深入的分析和研究。图的st-编号是对平面图中节点的一组编号，图是否能够求解出st-编号是判定图是否为平面图的重要依据。根据st-编号对平面图进行绘制可以保证每个节点都可以映射到一个尽量不重叠的位置上。
　　 有唯一一个源点以及汇点的无环无向图的定向问题，即st-定向图的求解是许多平面图绘制算法以及应用中的核心问题。st-定向图可以通过图的st-编号转化得到，但由于图的st-编号并不是唯一的，因此，得到的有向图也是随机的没有任何特殊的要求。然而，图形绘制算法利用不同的有向图作为输入，可能会导致图形得到在美学和范围上不同的结果。因此，大多数在平面图领域的应用希望得到有向图的同时能够控制有向图的定向长度。本文通过对st-编号算法的研究并给出了一种新的线性算法，该算法不但可以直接计算出平面图的st-定向，而且还能够在确定边方向的同时控制路径长度。算法能够求解出拥有最短或者最长定向长度的st-定向图。
　　 论文对算法进行了深入的分析和研究，对实现算法进行了全面的测试和调试，不但从理论上阐述了这些算法，并在可视化界面中实现了这些算法。本文最后研究了st-编号与st-定向在网络路由中的应用，并与其它路由协议进行了比较。在公平网络负载情况下，st-路由协议提供多条路径帮助均衡网络中的负载，有更高的吞吐量。在给定的时间内，st-路由协议比其他网络路由协议可以传输更多的数据包。

目录

声明

摘要

第一章 绪论

1．1 课题研究的背景和意义

1．2 课题国内外研究现状

1．3 论文研究内容

1．4 论文组织结构

第二章 平面图的st-编号算法

2．1 概述

2．2 基础知识

2．3 st-编号的定义

2．4 st-编号生成树

2．5 计算st-编号的算法

2．6 本章小结

第三章 平面图的st-定向算法

3．1 概述

3．2 基础知识

3．3 st-定向

3．4 计算st-定向的算法

3．5 确定最长定向与最短定向

3．6 本章小结

第四章 st-编号算法可视化系统设计与实现

4．1 概述

4．2 系统结构

4．3 系统数据层设计

4．4 st-编号算法程序设计

4．5 st-定向算法程序设计

4．6 系统界面设计

4．7 系统界面可视化操作

4．7．1 画图大小的调整

4．7．2 节点布局的调整

4．8 本章小结

第五章 st-编号在路由协议中的应用

5．1 概述

5．2 st-路由协议(st-routing protocol)

5．3 动态st-路由协议

5．3．1 增加新的节点

5．3．2 删除现有节点

5．4 st-路由协议优点

5．5 本章小结

第六章 总结与展望

6．1 工作总结

6．2 展望

参考文献

致谢

攻读硕士学位期间发表的论文