Handbook of Graph Theory, 2nd Edition

Chapter 1

Introduction to Graphs

Section 1.1 Fundamentals of Graph Theory

Jonathan L. Gross

Columbia University

Jay Yellen

Rollins College

Introduction

Configurations of nodes and connections occur in a great diversity of applications. They may represent physical networks, such as electrical circuits, roadways, or organic molecules. They are also used in representing less tangible interactions as might occur in ecosystems, sociological relationships, databases, or in the flow of control in a computer program.

1.1.1 Graphs and Digraphs

Any mathematical object involving points and connections between them may be called a graph. If all the connections are unidirectional, it is called a digraph. Our highly inclusive definition in this initial section ...