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

No credit card required

2.1 Graphs and Routing Protocols

The most important function of the network layer is routing. A tool used in the design and analysis of routing protocols is graph theory. Networks can be represented by graphs where mobile nodes are vertices and communication links are edges. Routing protocols often use shortest path algorithms. In this section we provide a simple review of the most important principles in the field which provides a background to study the routing algorithms.

• Elementary Concepts: A graph G(V,E) is two sets of objects, vertices (or nodes), set V and edges, set E. A graph is represented with dots or circles (vertices) interconnected by lines (edges). The magnitude of graph G is characterized by the number of vertices |V| (called the order of G) and the number of edges |E|, size of G. The running time of algorithms is measured in terms of order and size.
• Directed Graph: An edge e ∈ E of a directed graph is represented as an ordered pair (u,v), where u, v ∈ V. Here u is the initial vertex and v is the terminal vertex. Also assume here that u ≠ v. An example with  is shown in Figure 2.1.1.
• Undirected Graph: An edge eE of an undirected graph is represented as an unordered pair (u,v) = (v,u), where u, v ∈ V. Also assume that u ≠ v. An example ...

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

No credit card required