O'Reilly logo

Advanced Graph Theory and Combinatorics by Michel Rigo

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

1A First Encounter with Graphs

1.1. A few definitions

There is not much fun in listing basic definitions about graphs (this is quite a bad introduction to start with!) but if we seek a rigorous presentation of results and proofs, then we cannot avoid giving accurate definitions of the objects that we will manipulate, but hopefully nice examples will also come quickly. In this book, we assume that the reader has a basic (or, at least a naive) knowledge of sets and operations on them.

As usual in mathematics, a pair (u, v) made up of two elements is implicitly assumed to be ordered: it has a first component u and a second component v. It has to be compared with a set with two elements u and v denoted by {u, v}. A set does not carry any ordering information about its elements. In particular, if uv, then we can build two pairs but a single set: (u, v) ≠ (v, u) and {u, v} = {v, u}. If S is a finite set, we will write #S to denote the number of elements in S, i.e. the cardinality of S. We can also find the notation |S| but we will use it to denote lengths of paths.

1.1.1. Directed graphs

DEFINITION 1.1.– Let V be an arbitrary set. A directed graph, or digraph, is a pair G = (V, E) where E is a subset of the Cartesian product V × V, i.e. E is a set of pairs of elements in V. The elements of V are the vertices of G – some authors also use the term nodes – and the elements of E are the edges, also called oriented edges or arcs1, of G. An edge of the form (v, v) is a loop on v. Another ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required