Small information releated to graph.

Graph G is simply a way of encoding pair wise relationships among a set of objects: it consists of a collection V of nodes and a collection E of edges, each of which “joins” two of the nodes. We thus

represent an edge e ∈ E as a two-element subset of V: e = {u, v} for some

u, v ∈ V, where we call u and v the ends of e.

One of the fundamental operations in a graph is that of traversing a sequence of nodes connected by edges.

An undirected graph is a tree if it is connected and does not contain a cycle.

Rooted trees are fundamental objects in computer science, because they

encode the notion of a hierarchy.

Every n-node tree has exactly n − 1 edges.

Let G be an undirected graph on n nodes. Any two of the following

statements implies the third.

(i) G is connected.

(ii) G does not contain a cycle.

(iii) G has n − 1 edges.

Properties of DFS :

For a given recursive call DFS(u), all nodes that are marked “Explored”

between the invocation and end of this recursive call are descendants of u

in T.

Let T be a depth-first search tree, let x and y be nodes in T, and let

(x, y) be an edge of G that is not an edge of T. Then one of x or y is an ancestor

of the other.

Connected Components : For any two nodes s and t in a graph, their connected components are

either identical or disjoint.

The adjacency matrix representation of a graph requires O(n2) space,

while the adjacency list representation requires only O(m + n) space.

The adjacency list data structure is ideal for implementing breadth-first search.

The algorithm examines the edges leaving a given node one by one. When we

are scanning the edges leaving u and come to an edge (u, v), we need to

know whether or not node v has been previously discovered by the search.

To make this simple, we maintain an array Discovered of length n and set

Discovered[v]= true as soon as our search first sees v.

Similarly for DFS : we first add all of the nodes

adjacent to u to our list of nodes to be considered, but after doing this we

proceed to explore a new neighbor v of u. As we explore v, in turn, we add

the neighbors of v to the list we’re maintaining, but we do so in stack order,

so that these neighbors will be explored before we return to explore the other

neighbors of u. We only come back to other nodes adjacent to u when there

are no other nodes left.

If a graph G is bipartite, then it cannot contain an odd cycle.

If u and v are mutually reachable, and v and w are mutually reachable,

then u and w are mutually reachable.

For any two nodes s and t in a directed graph, their strong components

are either identical or disjoint.

Given a set of tasks with dependencies, it would be natural to seek

a valid order in which the tasks could be performed, so that all dependencies

are respected. Specifically, for a directed graph G, we say that a topological

ordering of G is an ordering of its nodes as v1, v2, . . . , vn so that for every edge

(vi , vj), we have i < j. In other words, all edges point “forward” in the ordering.

A topological ordering on tasks provides an order in which they can be safely

performed; when we come to the task vj, all the tasks that are required to

Precede it have already been done. If G has a topological ordering, then G is a DAG. In every DAG G, there is a node v with no incoming edges. If G is a DAG, then G has a topological ordering.