Theory and Application of Graphs
==========================================================================
Chapter
1
Basic
Concepts of Graphs
In many real-world situations, it is particularly
convenient to describe the specified relationship between pairs of certain given objects by means of a diagram, in which points
presents the objects and (directed or undirected) lines the relationship between pairs of the objects. For example, a national
traffic map describes a condition of the communication lines among cities in the country, where the points represent cities and the
lines represent the highways or the railways joining pairs of cities. Notice that in such diagrams one is mainly interested in
whether or not two given points are joined by a line; the manner in which they are joined is immaterial. A mathematical abstraction
of situations of this type gives rise to the concept of a graph.
In fact, a graph provides the natural structures from which to construct mathematical models that are appropriate to almost all
fields of scientific (natural and social) inquiry. The underlying subject of study in these fields is some set of ``objects" and one
or more ``relations" between the objects.
In this chapter, we will introduce basic concepts of a graph used in the remaining parts of the book, including several special
graphs, subgraphs of various types, walk, path, cycle, diameter, connection, Euler circuit, Hamilton cycle, adjacency and incidence
matrices, as well as the basic results closely related these concepts. At the end of this chapter we will present an
application of graphs to matrix theory.
It should, for the beginner specially, be worth noting that most graph theorists use personalized terminology in their books,
papers and lectures. Even the meaning of the word ``graph" varies with different authors. We will adopt the most standard
terminology and notation extensively used by most authors, with a subject index and a list of symbols in the end of the book.
|
