Page 186 - DCAP407_DATA_STRUCTURE

Unit 10: Trees

10.1.1 Representation of Tree in Graphs
A graph G consists of a set of objects V = {v1, v2, v3 …} called vertices (points or nodes) and a set of
objects E = {e1, e2, e3 ….} called edges (lines or arcs).
The set V (G) is called the vertex set of G and E (G) is the edge set.
The graph is denoted as G = (V, E)
Let G be a graph and {u, v} an edge of G. Since {u, v} is 2-element set, we write {v, u} instead of {u, v}.
This edge can be represented as uv or vu.
If e = uv is an edge of a graph G, then u and v are adjacent in G and e joins u and v.
Consider the graph in figure 10.2.

Figure 10.2: Graph

This graph G is defined by the sets:
V (G) = {u, v, w, x, y, z} and E(G) = { uv, uw, wx, xy, xz}
Every graph has a diagram associated with it. The vertex u and an edge e are incident with each other
as are v and e. If two distinct edges e and f are incident with a common vertex, then they are adjacent
edges.
Figure 10.3 depicts three examples of graphs. Graphs, unlike trees, can have sets of nodes that are
disconnected from other sets of nodes.

Figure 10.3: Examples of Graph

LOVELY PROFESSIONAL UNIVERSITY 179