Appendix B

Elements of Graph Theory, Asymptotic Notation, and Miscellaneous Notions

In this appendix, we start by introducing the asymptotic notation, and then report basic definitions and concepts from graph theory that have been used in this book. We will also formally define miscellaneous notions used in the book, such as linearity of operators, convexity and concavity, and so on. Most of the material presented in this appendix are based on Bollobàs (1985) and Bollobàs (1988), on Appendix B of Santi (2005), and on online resources such as Wikipedia and Wolfram MathWorld.

Let *f*(*n*) and *g*(*n*) be two functions defined on . One can write *f*(*n*) = *O*(*g*(*n*)) if and only if there exist a positive real number *c* and a real number *n*_{0} such that

The big-O notation is used to express the fact that, as the argument *n* of the function grows larger, function *f*(*n*) is *upper bounded* by function *g*(*n*), up to a constant factor.

Let *f*(*n*) and *g*(*n*) be two functions defined on . One can write *f*(*n*) = Ω(*g*(*n*)) if and only if there exist a positive real number *c* and a real number *n*_{0} such that

The big-Omega notation ...

Start Free Trial

No credit card required