3.1 Basic Definitions and Applications

A graph consists of a collection V of nodes and a collection E of edges, each of which joins two of the nodes. Edges indicate a symmetric relationship between their ends. Directed graphs express asymmetric relationships, and consist of a set of nodes V and a set of directed edges E'. With an ordered pair e'= (u,v) in E', u is called the tail of the edge, and v is head. Graphs serve as important models in several contexts. In transportation networks for instance, we can imagine the map of routes served by an airline as graphs: the nodes are airports, and there is an edge from u to v if there is a non-transit flight from u to v. In this case, it also is safe for us to describe the edge as coming from v to u, and treat the graph as an undirected one. In communication networks as well, we can describe a collection of computers connected though a communication network as a graph.In this kind of graph, a node would represent any computer, and we have an edge from u to v if there is a physical link connecting the two computers. If we think in terms of the internet, a node could represent a set of all computers controlled by a single service provider, and an edge from u to v would be defined if there is a direct peering relationship between the two computers. In information networks, the World Wide Web can be described as a directed graph in which nodes are Web pages, and an edge from u to v exists if there is a hyperlink from u to v. The reason why we describe information networks as directed graphs is that some sites may link to some big(or popular) websites, while those big sites don't link back to them. If we consider social networks, we can view them as graphs with people as nodes, and there is an edge joining u and v if u is friends with v.There are many options we can choose to represent the social network graphs. Another example of an application of graphs is the dependency networks, where graphs capture the interdependency among a collection of objects. For example in a food web, we can represent different species as nodes, and say that there is a node between u and v if u consumes v.

• A path in an undirected graph G = (V,E): A sequence P of nodes v₁,v₂,…,v_k-1,v_k, with the property that each consecutive pair v_i,v_i+1 is joined by an edge in G.P is called a v_k-1 to v_k. path.
• A cycle: a path v₁,v₂,…,v_k-1,v_k in which k>2, the first k-1 nodes are all distinct,and v₁ = v_k. Both of the above definition are kept in the context of directed graphs, with the only difference being the fact that we must respect the directionality of edges.
• An undirected graph is connected: If for every pair of nodes u and v, there is a path from u to v.A directed graph is strongly connected if, for every two nodes u and v, there is a path from u to v and a path from v to u.
• Distance between two nodes u and v: the minimum number of edges in a u-v path.
• An undirected graph is a tree : If it's connected and doesn't contain a cycle.
• A node w in a tree is a descendant of w if v lies on the path from the root to w
• A leaf node: a node that has no descendants.

Rooted trees express the notion of hierarchy. Every n-node tree has exactly n-1 edges. For an undirected graph G,any two of the statements below imply the third:

• G is connected
• G doesn't contain a cycle
• G has n-1 edges

In brief, graphs are a very fundamental notion in the Computer Science field and requires attention from everyone interested in the field.

Reading this section was pretty straightforward, as there aren't any confusing material in it. I definitely give it a 9/10.