多处理机系统的互联网拓扑通常以有向图或无向图为数学模型,用（有向图或无向图）中的顶点集来表示多处理机系统中的所有处理机,用边集或弧集来表示系统中处理机之间的通信线路.对互联网的性能一个关键要求是希望网络的可靠性（容错性）好,这对应于图论的术语来说,就是希望图的连通度和边连通度尽可能的大.在第一章第一节,我们给出本文将用到的图论方面的主要术语、记号.在第二节,我们介绍了本文将要用到的基本的概念和结论.本文第二章的主要研究了一类特殊的有向图-定向图连通度的下界,给出了定向图、定向二部图的连通度的下界:（1）设D是一个n阶定向图,连通度为κ,度序列为（d₁,d₂,…,d_n）.若κ≤δ-k（1≤k≤δ.且k为整数）,则（2）设D是一个n阶定向二部图,连通度为κ,度序列为（d₁,d₂,…,d_n）.若κ≤δ-k（1≤k≤δ,且k为整数）,则（3）设D是一个团数ω（D）≤p的n阶定向图,连通度为κ,它的度序列为（d₁,d₂,…,d_n）.若κ≤δ-k（1≤k≤δ,且k为整数）,则第三章主要是给出了有向图连通度的下界:（1）设D是一个n阶的有向图,连通度为κ,它的度序列为（d₁,d₂,…,d_n）.若κ≤δ-k（1≤k≤δ,且k为整数）,则（2）设D是一个n阶有向二部图,连通度为κ,它的度序列为（d₁,d₂,…,d_n）.若κ≤δ-k（1≤k≤δ,且k为整数）,则第四章主要研究了有向图边连通度的下界:（1）设D是一个团数为ω（D）≤p的n阶定向图,边连通度为λ,最小度为δ,度序列为（d₁,d₂,…,d_n）.若λ＜δ,则（2）设D是一个n阶有向图,边连通度为λ,最小度为δ,度序列为（d₁,d₂,…,d_n）.若λ＜δ,则