7
ELEMENTS OF GRAPH THEORY
7.1 INTRODUCTION
Graph theory has become a primary tool for detecting numerous hidden structures in various information networks, including the Internet, social networks, and biological networks. It is a mathematical model of any system that involves a binary relation. The theory is intimately related to many branches of mathematics including group theory, matrix theory, probability, topology, and combinatorics. The intuitive appeal of graphs arises from their diagrammatic representation. They are widely used in physics, chemistry, computer science, electrical engineering, civil engineering, architecture, genetics, psychology, sociology, economics, linguistics, and operations research. In this chapter we discuss the essential aspects of graph theory that will enable us to understand Bayesian networks, Boolean networks, and random networks that are discussed in the next three chapters.
7.2 BASIC CONCEPTS
A graph is a set of points (or vertices) that are interconnected by a set of lines (or edges). For a graph G we denote the set of vertices by V and the set of edges by E and thus write G = (V, E). The number of vertices in a graph is |V| and the number of edges is |E|. The cardinality |V| is called the order of the graph, and the cardinality |E| is called the size of the graph. An edge is specified by the two vertices that it connects. These two vertices are the endpoints of the edge. Thus, an edge whose two endpoints are vi and vj is denoted by eij = ...
