Unit 5: Graphs Theory II - Subjective Questions

Planar graph: A graph is called planar if it can be drawn in a plane so that no two edges intersect except at their common endpoints.

Plane graph: A particular crossing-free drawing of a planar graph is called a plane graph.

Faces:

• The edges of a plane graph divide the plane into connected regions called faces.
• The unbounded region outside the graph is called the outer face.
• The other regions are called interior faces.

Degree of a face: The degree of a face is the number of edge occurrences on its boundary. An edge is counted twice if it appears twice on the boundary of the same face.

For example, a triangle drawn without crossings is planar. It has vertices, edges, and faces: one interior face and one outer face. Each face has degree .

Euler's formula: If a connected planar graph has vertices, edges, and faces, then

Derivation:

1. Consider a spanning tree of the connected planar graph.
2. A tree with vertices has edges and only one face, namely the outer face.
3. Therefore, for the tree,
   
4. Now add each remaining edge of the original graph to the spanning tree.
5. Every added edge creates exactly one new face. Thus, both and increase by .
6. Consequently, the value of remains unchanged.

Hence, for the complete connected planar graph,

For a planar graph with connected components, the generalized formula is

Let a simple connected planar graph have vertices, edges, and faces.

General planar graph:

• Every face has degree at least .
• Since every edge belongs to the boundaries of two faces,
  
• Euler's formula gives
  
• Since ,
  
• Therefore,
  

Bipartite planar graph:

• A bipartite graph contains no odd cycle, so every face has degree at least .
• Hence,
  
  which gives .
• Using Euler's formula,
  
• Therefore,
  

These inequalities are necessary, but not sufficient, conditions for planarity.

For :

• The graph has vertices and
  
  edges.
• A simple planar graph with must satisfy
  
• For , this gives
  
• Since , is non-planar.

For :

• It has vertices and edges.
• It is bipartite, so if it were planar, it would satisfy
  
• For , this gives
  
• Since , is non-planar.

Thus, both and are non-planar graphs.

Let . Every vertex has degree .

By the handshaking lemma,

Therefore,

so

Using Euler's formula,

Substituting and ,

which gives

Thus, the graph has:

• Number of edges:
• Number of faces:

Proper vertex colouring: A proper vertex colouring of a graph is an assignment of colours to its vertices such that no two adjacent vertices receive the same colour.

Chromatic number: The chromatic number of a graph , denoted by , is the minimum number of colours required for a proper vertex colouring of .

-colourable graph:

• A graph is -colourable if it can be properly coloured using at most colours.
• Its chromatic number satisfies .

-chromatic graph:

• A graph is -chromatic if its chromatic number is exactly .
• Thus, .

For example, a square is -colourable because three colours can be used, but it is actually -chromatic because two colours are sufficient and one colour is not.

The chromatic numbers of standard graph families are as follows:

• Complete graph : Every pair of vertices is adjacent, so every vertex requires a different colour.
  

• Path : For , alternate two colours along the path.
  
  For a single vertex, .

• Cycle :
  

• Tree: Every nontrivial tree is bipartite and can be coloured according to even and odd distances from a selected vertex.
  
  for a tree with at least two vertices.

• Complete bipartite graph : The two vertex partitions can be assigned two different colours.
  
  when .

Greedy colouring algorithm:

1. Select an ordering of the vertices.
2. Assign the first vertex the first colour.
3. Process the remaining vertices in the selected order.
4. Assign each vertex the lowest-numbered colour not already assigned to any of its coloured neighbours.

If the maximum degree of the graph is , the greedy method uses at most colours.

Why it may not be optimal: The result depends on the order in which the vertices are processed. A poor ordering may cause the algorithm to use more colours than the chromatic number.

For example, a bipartite graph has chromatic number at most , but an unsuitable ordering can make the greedy algorithm use more than two colours.

Applications of graph colouring include:

• Examination scheduling
• Frequency assignment
• Register allocation in compilers
• Map colouring
• Conflict-free resource allocation

A tree is a connected graph containing no cycles.

(i) implies (ii):

• Since is connected, a path exists between every pair of vertices.
• If two distinct simple paths existed between the same pair, their union would contain a cycle.
• This contradicts the acyclic property. Hence, the path is unique.

(ii) implies (i):

• The existence of a path between every pair shows that is connected.
• If contained a cycle, two vertices on that cycle would have two distinct paths between them.
• This contradicts uniqueness. Therefore, is acyclic and hence a tree.

(i) implies (iii):

• A one-vertex tree has edges.
• Every tree with at least two vertices has a leaf.
• Removing a leaf and its incident edge produces a smaller tree.
• By induction, a tree with vertices has edges.

(iii) implies (i):

• A connected graph contains a spanning tree with edges.
• Since the graph itself has only edges, it must equal that spanning tree.
• Therefore, it has no cycles and is a tree.

Thus, all three statements are equivalent.

Proof by induction:

For , a tree has no edges, and

Assume every tree with vertices has edges. A tree with vertices has at least one leaf. Remove a leaf and its incident edge. The remaining graph is a tree with vertices, so it has edges. Restoring the removed edge gives

edges. Therefore, a tree with vertices has exactly edges.

Adding an edge:

• There is already a unique path between the endpoints of the new edge.
• Adding the edge creates exactly one cycle.

Removing an edge:

• Every edge of a tree is a bridge.
• Removing any edge disconnects the tree into exactly two components.

Thus, a tree is minimally connected and maximally acyclic.

A rooted tree is a tree in which one vertex is distinguished as the root.

• Root: The distinguished vertex at the top of the tree.
• Parent: If a vertex immediately precedes on the path from the root to , then is the parent of .
• Child: The vertex is a child of its parent .
• Siblings: Vertices having the same parent.
• Ancestor: A vertex lying on the path from the root to a given vertex.
• Descendant: A vertex below another vertex in the rooted structure.
• Leaf: A vertex with no children.
• Internal vertex: A vertex having at least one child.
• Level or depth: The number of edges in the unique path from the root to the vertex. The root has level .
• Height: The maximum level of any vertex in the rooted tree.
• Subtree rooted at : The tree consisting of , all descendants of , and the edges connecting them.

• A rooted tree is a tree with one vertex designated as the root.
• An -ary tree is a rooted tree in which every internal vertex has at most children.
• A full -ary tree is a rooted tree in which every internal vertex has exactly children.
• A binary tree is a -ary tree, so every internal vertex has at most two children.

Suppose a full -ary tree has internal vertices, leaves, and total vertices.

Every internal vertex contributes parent-child edges, so the number of edges is . Since every tree with vertices has edges,

As ,

Therefore,

and

For a full binary tree, , so and .

A spanning tree of a connected graph is a subgraph that:

• Contains every vertex of .
• Is connected.
• Contains no cycles.

Construction by deleting cycle edges:

1. Begin with the connected graph .
2. If the graph contains a cycle, remove one edge from that cycle.
3. Removing a cycle edge does not disconnect the graph.
4. Repeat until no cycles remain.
5. The resulting connected, acyclic subgraph is a spanning tree.

Construction by adding edges:

1. Start with all vertices and no edges.
2. Add edges that connect different components without forming a cycle.
3. Stop when all vertices become connected.

Properties:

• A spanning tree of a graph with vertices has exactly edges.
• A connected graph always has at least one spanning tree.
• A graph may have several different spanning trees.
• A graph is connected if and only if it has a spanning tree.

For a connected weighted graph, a minimum spanning tree, or MST, is a spanning tree whose total edge weight is minimum among all spanning trees of the graph.

Comparison:

• A spanning tree is defined for a connected graph and contains all vertices with no cycles.
• An MST additionally requires edge weights and minimizes their total.
• Every MST is a spanning tree, but every spanning tree need not be minimum.
• An MST need not be unique if some edge weights are equal.
• If all edge weights are distinct, the MST is unique.

Cut property: For any cut of a connected weighted graph, a minimum-weight edge crossing that cut belongs to at least one MST. If it is the unique minimum-weight crossing edge, it belongs to every MST.

Cycle property: In any cycle, a maximum-weight edge can be excluded from some MST. If it is the unique maximum-weight edge in the cycle, it cannot belong to any MST.

These properties justify greedy MST algorithms such as Prim's and Kruskal's algorithms.

Kruskal's algorithm: Select edges in nondecreasing order of weight, rejecting any edge that creates a cycle.

The ordered edges are:

Selection:

1. Select .
2. Select .
3. Reject because it would create the cycle .
4. Select .
5. Reject because and are already connected.
6. Select .

There are vertices, so the process stops after selecting edges.

The minimum spanning tree is

Its total weight is

Prim's algorithm starts with one vertex and repeatedly selects the minimum-weight edge connecting the current tree to a vertex outside it.

Starting at :

1. From , choose rather than .
2. The available crossing edges include and . Choose .
3. The tree now contains . To connect or , choose rather than or .
4. The tree contains . Choose to connect .

Thus, one minimum spanning tree is

The total weight is

Prim's algorithm grows one connected tree at every stage, whereas Kruskal's algorithm may temporarily maintain several disconnected trees.

A decision tree is a rooted tree used to represent the sequence of decisions or comparisons performed by an algorithm.

• Each internal vertex represents a test, question, or comparison.
• Each edge represents a possible outcome of the test.
• Each leaf represents a final result or solution.
• A path from the root to a leaf represents one possible execution of the algorithm.
• The height of the tree represents the worst-case number of decisions.

Finding the larger of and :

• At the root, test whether .
• If the answer is yes, move to a leaf that returns .
• If the answer is no, move to a leaf that returns .

Only one comparison is needed, so the decision tree has height . Decision trees are especially useful for analysing comparison-based searching and sorting algorithms.

A comparison-based sorting algorithm can be represented by a binary decision tree.

• Each internal vertex represents a comparison between two elements.
• The two outgoing edges represent the two possible outcomes.
• Each leaf represents a possible final ordering of the elements.

For distinct elements, there are possible input permutations. Therefore, a correct sorting decision tree must have at least leaves.

A binary tree of height has at most leaves. Hence,

Taking base- logarithms,

Since is an integer,

Using the growth of the factorial,

Therefore, every comparison-based sorting algorithm requires

comparisons in the worst case. Algorithms such as merge sort achieve comparisons and are therefore asymptotically optimal in this model.

Infix notation: The operator is written between its operands. Example: .

Prefix notation: The operator is written before its operands. Example: .

Postfix notation: The operator is written after its operands. Example: .

The given expression is interpreted as

Conversion:

• becomes prefix and postfix .
• becomes prefix and postfix .
• Multiplying them gives prefix and postfix .
• Dividing by gives the final forms.

Prefix:

Postfix:

Prefix and postfix forms do not require parentheses because the operator position determines the evaluation order.

The prefix expression is

Its structure is

Evaluation:

Therefore, the value is

Equivalent infix form:

Equivalent postfix form:

Expression-tree relation:

• The root is the subtraction operator.
• Its left subtree represents .
• Its right subtree represents .
• Preorder traversal gives prefix notation.
• Inorder traversal with suitable parentheses gives infix notation.
• Postorder traversal gives postfix notation.