الفهرس 
contentsOnly 14 pages are availabe for public view
 |  | from | 16 |  |  |
| | | from | 16 | | |
Abstract
The minimum spanning tree (MST) problem is one of the most important funda-
mentaland classic problems in the eld of combinatorial optimization. It is concerned
with nding a spanning tree of an undirected, connected graph, such that the sum of the
weights of the selected edges is minimum. The importance of this problem derives from
its direct applications in the design of computer, communication, transportation, power
and piping networks; from its appearance as part of solution methods to other problems
to which it applies less directly such as network reliability, clustering and classi cation
problems and from its occurrence as a subproblem in the solution of other problems like
the travelling salesman problem, the multi-terminal ow problem, the matching problem
and the capacitated MST problem. For more applications and the polynomial algorithms
that solve the MST problem, see Ahuja[1] .
Multi-objective combinatorial optimization problems are special cases of the MOIP
problems that are distinguished due to their special structured constraint sets. Bi-
objective, tri-objective or multi-objective versions of scheduling, shortest path, assign-
ment, traveling salesman, minimum spanning tree are some note-worthy MOCO prob-
lems. Ehrgott and Gandibleux (2000) and Ehrgott and Gandibleux (2004) review the
MOCO literature on the exact and approximate methods, respectively. They address some special problem types and discuss their solution methodologies. Ehrgott and
Gandibleux (2002) survey some other Multi-criteria optimization problems including,
but not limited to, nonlinear programming, scheduling, multi-level programming [see[2]].
Many real world decision problems can be formulated as combinatorial optimization
problems with several conicting (cost) objectives. The multi-criteria MST problem is a
more realistic representation of the practical problems in the real world. Aneja[3] consider
two-criteria dynamic program and show that the optimal solution is a nondominated
solutionof the two criteria program.
Our problem is on a undirected connected graph with bi-objective functions on the
set of its edges has a minimum ratio of the cost function to the reliability functionC(T)
R(T) :
To solve the problem, we must rst know that what is graphs, what are these
qlassi cations and how extracte a subgraph and we will know that trees are subgraphs
of the graph. That is will introduce in the next section.
1.1 Preliminaries
In this section, we bring many basic de nitions of network and graph theory, and in
doing so, we set the notation that we will be using throughout this thesis.
A simple graph G = (V; E) consists of a non-empty nite set V of elements called
vertices (or nodes), and a nite set E of distinct unordered pairs of distinct elements of
V called edges. We call V the vertex set and E the edge set of G. An edge fv;wg
is said to join the vertices v and w. For example, Fig.(1-1(a)) represents the simple
graph G whose vertex set V is fu; v;w; zg, and whose edge set E consists of the edges
[fu; vg ; fu;wg ; fv;wg ; fw; zg].
In any simple graph there is at most one edge joining a given pair of vertices.
However, many results that hold for simple graphs can be extended to more general
objects in which two vertices may have several edges joining them. In addition, we may
remove the restriction that an edge joins two distinct vertices, and allow loops joining.