中文摘要：

网络的可靠性是衡量网络性能的重要方面，从而成为网络设计和分析必须考虑的重要因素之一。我们通常用一个连通的无向图或强连通有向图G=(V,E)作为网络的拓扑结构，图的连通度是度量网络可靠性的重要参数，它表明对应的网络可以容许多少个结点或多少条信息传输信道同时发生故障仍能保证剩余子网络中各结点之间的正常通信。 为了克服传统连通度在度量网络性能方面的缺陷，本项目研究能更精确度量网络实时可靠性的重要参数- - - - 条件连通度。该参数自上世纪八十年代提出以后，获得了计算机和数学科学理论工作者的广泛关注和研究兴趣。我们主要从组合论的角度，利用图论工具，对这个参数进行研究和优化1. 研究文献中较少涉及到的有向网络的条件连通度；2. 刻划其达到最优值的条件；3. 将理论结果应用到网络可靠性的优化设计中，结合现有的进化算法、智能算法构造满足一定约束条件的高可靠网络。

结论摘要：

21 世纪以来，以信息技术的飞速发展为基础，计算机网络、交通网络、复杂网络无时无刻不包围着我们。一旦网络出现故障,可能会造成重大甚至是灾难性的影响,网络可靠性成为了网络分析和设计中的重要问题。 网络可靠性是指网络在规定条件下和规定时间内，能在用户期望的时间范围内将物质、信息、能量按用户需求完整、正确地在网络中传输的能力。对于一个网络，是指至少需要破坏几个节点或几条链路才能中断部分节点之间的通信。可以通过两个确定测度——连通度κ和边连通度λ来表示。要使一个网络解体，至少需要去掉κ个节点或者λ条链路。这种解体，可能把一个网络分解为两个或多个子网络，也可能把一个节点从网络中分离出来。对于网络业务来说，前者比后者带来更严重的后果。传统连通度并不能做出区分。 考虑到实际应用，本项目重点研究能更精确度量网络可靠性的参数——条件连通度及其推广h 条件连通度，并将研究成果应用到网络可靠性的优化设计中。具体研究内容如下 1．条件连通度确定问题 2. 最优连通图的刻划问题这两类问题是相辅相成的，在研究过程中通常是同时考虑的。很多典型网络的条件连通度尤其是条件边连通度已经确定，但是在连通度方面的结论却很少。强积图是一种大规模网络的构造方式，并且保持其因子图的诸多性质，尤其是可靠性方面。我们主要结论是？？给出了以强积图网络可靠性的确切度量，并且刻画了其达到最优值的条件，即该类网络在不考虑其他要求时达到最可靠的条件。？？考虑到网络实际运行时与同一台处理器直接连接的各处理器同时发生故障的可能性很小，所以在强积图点可靠性达到最优值的基础上我们进一步分析该类网络的可靠性，我们给出了强积图的条件连通度的界及其达到最优值的条件。？？网络链路发生故障时的可靠性则需要用边连通度来度量，考虑实际意义，我们也研究了强积图的条件边连通度，给出了在网络链路发生故障的情况下网络达到最可靠的条件。　 3. 网络可靠性优化设计问题设计了算法以强积图方式构造满足一定约束条件下的高可靠性网络。　　 4. 高可靠性网络上的一些实际应用如交通网络上的距离查询、中国互联网的物理定位、社交网络上的问答系统等。