1. **Define with example:** (i) Finite and Infinite graphs: - A finite graph has a finite number of vertices and edges. - An infinite graph has infinitely many vertices or edges. Example: A triangle graph with 3 vertices is finite. (ii) Complement of graphs: - The complement of a graph G has the same vertices as G but edges where G does not have edges. Example: If G has edge (a,b), complement does not have (a,b). (iii) Union and Intersection of graphs: - Union of graphs G1 and G2 has vertices and edges from both. - Intersection has only vertices and edges common to both. 2. **Algorithm for shortest path (Dijkstra's Algorithm):** - Initialize distances from source to all vertices as infinity except source itself (0). - Set all vertices as unvisited. - While unvisited vertices remain: - Select unvisited vertex with smallest tentative distance. - Update distances to neighbors if shorter path found. - Repeat until destination is visited. **Apply to given graph from a to z:** Vertices: a,b,c,d,e,z Edges and weights: (a-b)=1, (b-d)=7, (b-c)=2, (a-c)=4, (c-e)=1, (d-e)=6, (d-z)=3, (a-z)=5, (e-z)=2 Stepwise distances: - Start: dist(a)=0, others=∞ - From a: update b=1, c=4, z=5 - Next min dist: b=1 - From b: update c=min(4,1+2=3)=3, d=1+7=8 - Next min dist: c=3 - From c: update e=3+1=4 - Next min dist: e=4 - From e: update z=min(5,4+2=6)=5 - Next min dist: z=5 (destination reached) Shortest path: a → b → c → e → z with total weight 1+2+1+2=6 3. **Adjacency matrix for given graph:** Vertices: v1,v2,v3,v4,v5,v6,v7 Edges: v1-v6, v1-v5 v5-v4 v3-v4, v3-v2 v7 self-loop v4 self-loop Matrix (rows and columns in order v1 to v7): $$\begin{bmatrix} 0 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix}$$ 4. **Hasse Diagram for \( \leq \) on \( A=\{0,2,5,10,11,15\} \):** - Draw elements as nodes. - Draw edges from smaller to larger elements without intermediate elements. Edges: 0 → 2 → 5 → 10 → 15 5 → 11 → 15 5. **Show that in lattice L, \( a \wedge b = a \) iff \( a \vee b = b \):** - If \( a \wedge b = a \), then \( a \leq b \) by definition of meet. - By lattice properties, \( a \leq b \) implies \( a \vee b = b \). Hence, \( a \wedge b = a \iff a \vee b = b \).