Discrete Structures · Unit 6 · 12 hrs
Relations and Graphs
Exam-focused notes for Relations and Graphs (Discrete Structures, CSC165): what the TU syllabus asks and how it has actually been tested, with 25 solved past questions from this unit.
What this unit covers
- Relations
- Relations and their Properties
- N-ary Relations with Applications
- Representing Relations
- Closure of Relations
- Equivalence Relations
- Partial Ordering
- Graphs
- Graphs Basics
- Graph Types
- Graph Models
- Graph Representation
- Graph Isomorphism
- Connectivity in Graphs
- Euler and Hamiltonian Path and Circuits
- Matching Theory
- Shortest Path Algorithm (Dijkstra's Algorithm)
- Travelling Salesman Problem
- Graph Coloring
- Trees
- Introduction and Applications
- Tree Traversals
- Spanning Trees
- Minimum Spanning Trees (Kruskal's Algorithm)
- Network Flows
- Graph as Models of Flow of Comodities
- Flows
- Maximal Flows and Minimal Cuts
- The Max Flow-Min Cut Theorem
Euler and Hamiltonian Path and Circuits
What are the necessary and sufficient conditions for graphs to have Euler path only and Euler circuit? Let $R$ be a relation defined on set of natural numbers $N$, such that $a,b \in N, aRb \leftrightarrow ab = 2k$, where $k \in {0,1,2,...}$. Show that $R$ is a partial ordering relation on $N$ [10]
--- - Euler Path: A path in a graph that visits every edge exactly once (but may start and end at different vertices). - Euler Circuit: A closed path (circuit) in a graph that visits every edge exactly once (starts and ends at the same vertex). --- Theorem:...
Full solved answer →Give an example of fallacy. State the necessary and sufficient conditions for a graph to have Euler path and Euler circuit. [5]
--- A fallacy is an error in reasoning where a conclusion is drawn incorrectly from given premises, even though the argument appears valid on the surface. Example: Consider the following argument: Premise: If a graph is Eulerian, then every vertex has even ...
Full solved answer →Define Euler circuit with suitable example. Find the maximal flow s to t from the given network flow.[10]
Part 1 (Euler Circuit): Purely definitional; requires a self-constructed example. No numeric data supplied. Part 2 (Maximum Flow): - A network with source $s$ and sink $t$ is referenced. - The actual network diagram (vertices, directed edges, and edge capac...
Full solved answer →Define Euler path and Hamilton path. Give examples of both Euler and Hamilton path. [5]
Definition: An Euler path (also called an Eulerian trail) is a path in a graph that traverses every edge exactly once. The initial and terminal vertices of the path need not be the same. If the initial and terminal vertices are the same, it is called an Eul...
Full solved answer →Define Euler path and Hamilton path with examples. Draw the Hasse diagram for the divisibility relation on the set {1,2,5,8,16,32} and find the maximal, minimal, greatest and least element if exist. [5]
Definition: An Euler path is a walk in a graph that traverses every edge exactly once (vertices may repeat). If it starts and ends at the same vertex, it is an Euler circuit. Existence condition: A connected graph has an Euler path iff it has exactly 0 or 2...
Full solved answer →Minimum Spanning Trees
Define chromatic number. How does Kruskal's algorithm find Minimum Spanning Tree? [5]
--- The chromatic number of a graph G is the minimum number of colors required to color the vertices of G such that no two adjacent vertices (vertices connected by an edge) share the same color. It is denoted by χ(G) (chi of G). Examples: - A complete graph...
Full solved answer →State Generalized Pigeonhole principle. Find the MST from following graph using Kruskal Algorithm. [5]
- Part 1: Requires the statement of the Generalized Pigeonhole Principle (theory, no numeric data). - Part 2: Requires finding the MST using Kruskal's Algorithm "from the following graph." Missing data: The actual graph (vertices, edges, and edge weights) f...
Full solved answer →What are the significance of Minimum Spanning Tree? Describe how Kruskal's algorithm can be used to find the MST. [5]
A Minimum Spanning Tree of a weighted connected graph is a spanning tree with the minimum total edge weight. Its significance includes: 1. Network Design: Used in designing minimum-cost communication networks, electrical grids, and road networks connecting ...
Full solved answer →What is minimum spanning tree? Explain Kruskal's algorithm for finding minimum spanning tree. [5]
Let G be a connected weighted graph. The weight of a spanning tree of G is the sum of the weights of the edges included in that spanning tree. A Minimum Spanning Tree (MST) of G is a spanning tree of G with the minimum possible weight among all possible spa...
Full solved answer →The Max Flow-Min Cut Theorem
State max flow min cut theorem. Find the value of maximal flow in the graph below:[10]
The question asks to: 1. State the Max Flow Min Cut Theorem. 2. Find the value of maximal flow "in the graph below." Missing data: The actual flow network graph (vertices, directed edges, and edge capacities) is not provided in the text. No image, adjacency...
Full solved answer →Graph Isomorphism
State the necessary conditions for two graphs to be isomorphic. How many different words from 'MANAGER' can be generated with or without meaning? [5]
Two graphs $G1 = (V1, E1)$ and $G2 = (V2, E2)$ are isomorphic if there exists a bijection (one-to-one and onto mapping) $f: V1 \to V2$ such that any two vertices $u$ and $v$ are adjacent in $G1$ if and only if $f(u)$ and $f(v)$ are adjacent in $G2$. For two...
Full solved answer →List all the necessary conditions for the graph to be isomorphic with an example. Find the maximal flow from the node SOURCE to SINK in the following network flow.[10]
Part 1: Conceptual question. No numeric data required. Part 2: The network diagram (the actual figure with its specific capacities) is not reproducible from the text provided, and no capacity matrix or edge list was supplied with the question. The original ...
Full solved answer →Closure of Relations
Define symmetric closure. What is the symmetric closure of the relation R = {(1,1), (1,2), (2,2), (2,3), (3,1), (2,1)} on the set A = {1,2,3}? [5]
- Set $A = \{1, 2, 3\}$ - Relation $R = \{(1,1),\ (1,2),\ (2,2),\ (2,3),\ (3,1),\ (2,1)\}$ --- The symmetric closure of a relation $R$ on a set $A$ is the smallest symmetric relation on $A$ that contains $R$. It is formed by adding to $R$ the reverse pair $...
Full solved answer →Define reflexive closure and symmetric closure. Find the remainder when $4x^2 - x + 3$ is divided by x + 2 using remainder theorem. [5]
- Polynomial: $f(x) = 4x^2 - x + 3$ - Divisor: $x + 2$ --- The reflexive closure of a relation $R$ on a set $A$ is the smallest reflexive relation on $A$ that contains $R$. It is formed by adding all pairs $(a, a)$ for every $a \in A$ that are not already i...
Full solved answer →Graph Representation
Represent following graph using adjacency matrix. [5]
Given data: - The question asks to represent "following graph" using an adjacency matrix. - The actual graph figure (vertices, edges, directedness, weights) is NOT provided in the text given to me. Missing data: The specific graph image is not visible. With...
Full solved answer →Equivalence Relations
Show that the relation R = {(a, b): |a-b| is even} is an equivalence relation in the set of integers. Given the following transport network with the edges called with their capacities find all S-D cuts and their capacities and what the minimum capacity?[10]
--- To prove R is an equivalence relation, we verify reflexivity, symmetry, and transitivity. For any integer $a$: $$a - a = 0 = 0$$ Since $0$ is even, $(a, a) \in R$ for all $a \in \mathbb{Z}$. R is reflexive. ✓ Suppose $(a, b) \in R$, so $a - b$ is even. ...
Full solved answer →Let us assume that R be a relation on the set of ordered pair of positive integers such that ((a,b),(c,d))∈R((a, b), (c, d)) \in R((a,b),(c,d))∈R if and only if ad = bc. Is R an equivalence relation? [5]
A relation R on a set A is an equivalence relation if and only if it satisfies three properties: 1. Reflexivity: (a, a) ∈ R for all a ∈ A 2. Symmetry: If (a, b) ∈ R then (b, a) ∈ R 3. Transitivity: If (a, b) ∈ R and (b, c) ∈ R then (a, c) ∈ R Here, R is def...
Full solved answer →Graph Types
Define bipartite graph with an example. State the necessary conditions for the graphs to be isomorphic. [5]
--- A graph G = (V, E) is called a bipartite graph if its vertex set V can be partitioned into two disjoint non-empty subsets V1 and V2 (called partition sets) such that: - Every edge in E connects a vertex in V1 to a vertex in V2. - No edge exists between ...
Full solved answer →Shortest Path Algorithm
Illustrate the Dijkstra's Algorithm to find the shortest path from source node to destination node with an example. [5]
Dijkstra's Algorithm, discovered by E.W. Dijkstra, finds the shortest path between two vertices in a weighted graph. The length of a path is the sum of the weights of its edges, and the shortest path is the minimum length path between two vertices. --- 1. A...
Full solved answer →What is shortest path problem? Use Dijkstra's shortest path algorithm to find the shortest path between vertices a and z in the weighted graph below:[10]
Question requirements: - Define the shortest path problem. - Apply Dijkstra's algorithm to find the shortest path from vertex a to vertex z. Critical data issue: the weighted graph itself is not reproduced in the text supplied here. The working below theref...
Full solved answer →Partial Ordering
Which of the following are possets? a. $(Z, =)$ b. $(Z, \neq)$ c. $(Z, \leq)$ [5]
A partially ordered set (poset) is a set $S$ together with a binary relation $R$ that satisfies all three of the following properties: Property Meaning ------ Reflexivity $\forall a \in S,\; a\, R\, a$ Antisymmetry $\forall a, b \in S,\; a\, R\, b \text{ an...
Full solved answer →Graph Coloring
List any two applications of graph coloring theorem. Prove that 'A tree with n vertices has n-1 edges'. [5]
--- 1. Frequency/Channel Assignment: Graph coloring is used to assign frequencies or channels to television and radio stations. Each station is represented as a vertex, and an edge is drawn between two stations if they are close enough to interfere with eac...
Full solved answer →Maximal Flows and Minimal Cuts
What is S-D cut? For the following network flow find the maximal flow from S to D.[10]
Definition part: No numeric data required. Network flow part: The problem states "the following network," but the actual network diagram (nodes, directed edges, and edge capacities) is NOT reproduced in the text provided to me. Without the diagram, the spec...
Full solved answer →Spanning Trees
Define spanning tree and minimum spanning tree, mention the conditions for two graphs for being isomorphic with ean example [5]
--- A spanning tree of a connected graph G is a subgraph T of G that: - Contains all the vertices of G - Is a tree (connected and acyclic) - Has exactly n - 1 edges, where n is the number of vertices In other words, a spanning tree is a minimal connected su...
Full solved answer →Representing Relations
Explain the matrix representation of relations with example. [5]
Let R be a relation from set A = {a₁, a₂, ..., aₘ} to set B = {b₁, b₂, ..., bₙ}. The matrix representation of R is an m × n zero-one matrix MR = [mij] where: $$m{ij} = \begin{cases} 1 & \text{if } (ai, bj) \in R \\ 0 & \text{if } (ai, bj) \notin R \end{case...
Full solved answer →Make Unit 6 stick
Practice CSC165 with flashcards & quizzes