Mobility Models for Next Generation Wireless Networks

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.

B.1 Asymptotic Notation

Definition B.1 (Big-O notation)

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₀ 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.

Definition B.2 (Big-Omega notation)

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₀ such that

The big-Omega notation ...