Graphs and Trees

Question 1

What is a graph (undirected)?

Answer 1

A graph G is simply a way of encoding pairwise 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 represent an edge e -> E as a two-element subset of V: e = {u, v} for some u, v ->V, where we cal! u and v the ends of e.

Question 2

What is a Directed Graph?

Answer 2

Each e’ -> E’ is an ordered pair (u, v); in other words, the roles of u and v are not interchangeable,

• we call u the tail of the edge and v the head.
• we say that edge e’ leaves node u and enters node v.

Question 3

Paths and Connectivity: Path?

Answer 3

# define a **_path_** in an undirected graph G = (V, E) to be a sequence P of nodes v1, v2 ..... v<sub>k1</sub>, v<sub>k</sub> with the property
 that each consecutive pair v<sub>i</sub>, v<sub>i+1</sub> is ioined by an edge in G.

• P is often called path from v₁ to v_k, or a v₁-v_k path

Question 4

Paths and Connetivity: Type of Paths

• Simple Path
• Cycle

Directed Graph refinement.

Answer 4

Simple:

A path is called simple if all its vertices are distinct from
one another.

Cycle:

A cycle is a path v₁, v₂ ….. v_k-1, v_k in which k > 2,

• the first k - 1 nodes are all distinct,
• and v_l = v_k – in other words, the sequence of nodes “cycles back” to where it began.

Directed Graph:

• in a directed path or cycle, each pair of consecutive nodes has the property that (v_i, v_i+l) is an edge.
• In other words, the sequence of nodes in the path or cycle must respect the directionality of edges.

Question 5

Paths and Connectivity: Connected?

Strongly Connected?

Answer 5

Undirected graph:

• an undirected graph is connected if, for every pair of nodes u and v, there is a path from u to v.

Directed graph:

• a directed graph is strongly connected if, for every two nodes u and u, there is a path from u to v and a path from v to u.

Question 6

Path and Connectivity: Distance?

Answer 6

we define the distance between two nodes u and v to be the minimum number of edges in a u-v path.

• The term distance here comes from imagining G as representing a communication or transportation network;
• if we want to get from a to u, we may well want a route with as few “hops” as possible.

Question 7

Trees - undirected graph?

Answer 7

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

Thestructure of a tree T:

• it is useful to root it at a particular node r. Physically, this is the operation of grabbing T at the node r and letting the rest of it hang downward under the force of gravity.
• More precisely, we “orient” each edge of T away from r;
• for each other node v, we declare the parent of v to be the node u that directly precedes v on its path from r;
• we declare w to be a child of v if v is the parent of w.
• More generally, we say that w is a descendant of v (or v is an ancestor of w) if v lies on the path from the root to w;
• we say that a node x is a leaf if it has no descendants

Question 8

Trees: Rooted Tree?

Answer 8

Rooted trees are fundamental objects in computer science, because they encode the notion of a hierarchy.

• roofing a tree T can make certain questions about T conceptually easy to answer
• For example, given a tree T on n nodes, how many edges does it have? Each node other than the root has a single edge leading “upward” to its parent; and conversely, each edge leads upward from precisely one non-root node

Question 9

Trees: Treeness Theorem

Answer 9

(3.1) Every n-node tree has exactly n - I edges.

In fact, the following stronger statement is true, although we do not prove it here.

(3.2) Let G be an undirected graph on n nodes. Any two of the following statements implies the third.

1. G is connected.
2. G does not contain a cycle.
3. G has n - 1 edges.

Question 10

Graph: Directed Def

Answer 10

A directed graph (or digraph) G is a pair (V;E), where V is a finite set and E is a binary relation on V .

The set V is called the vertex set of G, and its elements
are called vertices (singular: vertex).

The set E is called the edge set of G, and its
elements are called edges.

Note that self-loops—edges from avertex to itself—are possible.

Question 11

Graph: Undirected Defn

Answer 11

In an undirected graph G = (V;E), the edge set E consists of unordered pairs of vertices, rather than ordered pairs. That is, an edge is a set {u,v}, where u, v-> V and u != v .

By convention, we use the notation (u,v) for an edge, rather than the set notation {u,v}.

Note: In an undirected graph, self-loops are forbidden, and so every edge consists of two distinct vertices

Question 12

Graph: Edge Terminology

Answer 12

Directed Graph:

If .(u, v) is an edge in a directed graph G = (V, E),

• we say that (u, v) is incident from or leaves vertex u
• (u,v) is incident to or enters vertex .

Undirected Graph:

If (u,v) s an edge in an undirected graph G = (V;E),

• we say that (u, v) is incident on vertices u and v.

Adjacency:

If .(u,v) is an edge in a graph G = (V,E), we say that vertex is adjacent to vertex u.

• When the graph is undirected, the adjacency relation is symmetric.
• When the graph is directed, the adjacency relation is not necessarily symmetric.
• If v is adjacent to u in a directed graph, we sometimes write u –> v.

Question 13

Graph: Degree?

Answer 13

Undirected graph:

The degree of a vertex in an undirected graph is the number of edges incident on it.

• A vertex whose degree is 0, is isolated.

Directed graph:

In a directed graph,

• the out-degree of a vertex is the number of edges leaving it, and
• the _in-degre_e of a vertex is the number of edges entering it.

The degree of a vertex in a directed graph is its in-degree plus its _out-degre_e

Question 14

Tranversal Algorithm: BFS

Breadth-first search

Answer 14

Breadth-first search:

BFS systematically explores the edges of G to “discover” every vertex that is “reachable from s.

• BFS computes the distance (smallest number of edges) rom s toeach reachable vertex s.
• BFS produces a BFS tree with root s that contains all reachable vertices
• BFS discovers Shortest Path - for any vertex v reachable from s the path s–>v cooresponds to the shortest path from s to v in G.
• BFS expands the frontier uniformly; that is the algorithm discovers all vertices at distance K from s before discovering any vertices at distance K+1 from s.