Elements of Graph Theory

Graph theory has become a primary tool for detecting numerous hidden structures in various information networks. The theory is intimately related to many branches of mathematics including group theory, matrix theory, probability, topology, and combinatorics. This chapter discusses the essential aspects of graph theory that enables us to understand Bayesian networks, Boolean networks, and random networks. A random graph is a finite set of vertices where edges connect vertex pairs in a random manner. The chapter considers three classes of random graphs: Bernoulli random graphs, geometric random graphs, and Markov random graphs. Several properties of a graph can be demonstrated via the matrix representation of the graph. One of the matrix representations of a graph is the adjacency matrix. Other matrix representations include connection matrix, path matrix, and Laplacian matrix. The chapter provides a brief discussion on these representations. Controlled Vocabulary Terms binomial distribution; geometric distribution; graphical model; Markov random field; matrix diagram; probability; Random graph