# Graph Theory and Combinatorics Winter 2022 GTU Paper Solution | 3171611

Here, We provide Graph Theory and Combinatorics GTU Paper Solution Winter 2022. Read the Full GT&C GTU paper solution given below.

Graph Theory and Combinatorics GTU Old Paper Winter 2022 [Marks : 70] : Click Here

(a) Define: Simple Graph, Pseudo Graph, Bipartite Graph.

In graph theory, a graph is a set of vertices or nodes connected by edges or arcs. Here are the definitions of simple graph, pseudograph, and bipartite graph:

1. Simple graph: A simple graph is an undirected graph that does not contain any loops or multiple edges. Loops are edges that connect a vertex to itself, while multiple edges are edges that connect the same pair of vertices.
2. Pseudograph: A pseudograph is a graph that allows loops and multiple edges. In other words, a pseudograph is a graph that may have edges that connect a vertex to itself or more than one edge connecting the same pair of vertices.
3. Bipartite graph: A bipartite graph is a graph whose vertices can be divided into two disjoint sets such that no two vertices within the same set are adjacent. In other words, a bipartite graph is a graph whose vertices can be colored using only two colors such that no two adjacent vertices have the same color. Bipartite graphs are often used to model relationships between two different types of objects, such as employees and projects or students and courses.

(b) List properties of Tree.

(c) Are the graphs shown in the following figure isomorphic? Justify your answer.

(a) How many nodes are necessary to construct a graph with exactly 8 edges in which
each node is of degree 2?

Let n be the number of nodes in the graph.

Each node has degree 2, which means that there are 2 edges coming out of each node. Therefore, the total number of edges in the graph is half the sum of the degrees of all the nodes:

``````total number of edges = (sum of degrees) / 2
``````

Since each node has degree 2, the sum of the degrees of all the nodes is just 2n:

``````sum of degrees = 2n
``````

Substituting this into the previous equation, we get:

``````total number of edges = (2n) / 2 = n
``````

Therefore, for a graph with exactly 8 edges, we need n = 8.

(b) What is graph coloring? Explain Greedy coloring.

(c) Obtain minimum spanning tree using Primâ€™s algorithm.

(c) Describe KÃ¶nigsberg Bridge Problem with respect to graph theory.

(a) Differentiate Permutation & Combination with proper example.

Permutation and combination are the two basic concepts of combinatorics used to count the number of possible outcomes. The main difference between permutation and combination lies in the order of selection of objects.

Permutation: A permutation is an arrangement of objects in a specific order. It is denoted as P(n, r) and defined as the number of ways of selecting r objects from a set of n distinct objects, where the order of the selection is important.

For example, let us assume that there are 4 students named A, B, C, and D, and we want to select 2 students from them to form a team. The possible permutations of selecting 2 students from a set of 4 students are AB, AC, AD, BA, BC, BD, CA, CB, CD, DA, DB, and DC. Here, the order of selection is important, so AB and BA are counted as two different permutations.

Combination: A combination is a selection of objects from a set without regard to the order of the objects. It is denoted as C(n, r) and defined as the number of ways of selecting r objects from a set of n distinct objects, where the order of the selection is not important.

For example, using the same set of 4 students named A, B, C, and D, the possible combinations of selecting 2 students from the set are AB, AC, AD, BC, BD, and CD. Here, the order of selection is not important, so AB and BA are counted as one combination.

The formula for permutation and combination are as follows:

• Permutation: P(n, r) = n!/(n-r)!
• Combination: C(n, r) = n!/r!(n-r)!

In summary, permutation and combination are two basic counting principles of combinatorics that have distinct differences in the order of selection of objects.

(b) What is Rook Polynomial? Explain expansion formula of it.

(c) Explain the stable matching problem.

OR

(a) In how many ways a hockey team of eleven can be elected from 16 players?

This problem involves selecting 11 players out of 16, where order does not matter. This can be solved using the combination formula:

nCk = n! / (k! * (n-k)!)

Where n is the total number of players (16) and k is the number of players to be selected (11).

Plugging in the values, we get:

16C11 = 16! / (11! * (16-11)!) = (16 * 15 * 14 * 13 * 12 * 11!) / (11! * 5 * 4 * 3 * 2 * 1) = 8008

Therefore, there are 8,008 ways to select a hockey team of 11 players from 16 players.

(b) There are 350 farmers in a large region. 260 farm beetroot, 100 farm yams, 70
farm radish, 40 farm beetroot and radish, 40 farm yams and radish, and 30 farm
beetroot and yams. Let B, Y, and R denote the set of farms that farm beetroot,
yams and radish respectively. Determine the number of farmers that farm
beetroot, yams, and radish.

(c) Describe Hallâ€™s marriage theorem.

(a) Write applications of Transport Network.

Transport networks, which are a type of graph, have various applications in different fields. Here are some examples:

1. Transportation and logistics: Transport networks are used in transportation and logistics to model and optimize the flow of goods, people, and vehicles. They help in designing efficient transportation routes, minimizing travel time and distance, and reducing transportation costs.
2. Telecommunications: Telecommunication networks use transport networks to model and optimize the flow of data traffic through communication channels. This helps in designing efficient communication networks, minimizing network congestion, and maximizing data transfer rates.
3. Power grids: Power grids are complex networks that use transport network concepts to model and optimize the flow of electricity through transmission lines, transformers, and distribution networks. This helps in designing efficient and reliable power grids, minimizing power outages, and reducing energy consumption.
4. Water distribution systems: Water distribution systems use transport networks to model and optimize the flow of water through pipes, pumps, and reservoirs. This helps in designing efficient water distribution systems, minimizing water losses, and ensuring equitable water distribution.
5. Social networks: Social networks can be modeled as transport networks, where individuals or groups of individuals are connected by social ties. This helps in understanding the structure and dynamics of social networks, identifying key influencers and opinion leaders, and predicting the spread of information or ideas.
6. Biological networks: Biological systems, such as food webs, metabolic networks, and gene regulatory networks, can be modeled as transport networks. This helps in understanding the complex interactions and dependencies between different biological entities, predicting the effects of perturbations or interventions, and designing effective treatments for diseases.

(b) Give an example of following :
1) A graph that has an Eulerian circuit but no Hamiltonian Circuit
2) A graph that has a Hamiltonian circuit but no Eulerian circuit.

(c) Explain the Exponential Generating Function.

OR

(a) Solve the recurrence relation an+1 = 4*an for n>=0, a0=3.

We can solve the recurrence relation using iteration or substitution method.

Using iteration method: a1 = 4a0 = 43 = 12 a2 = 4a1 = 412 = 48 a3 = 4a2 = 448 = 192 a4 = 4a3 = 4192 = 768

So, the pattern is an = 4^n * a0 = 4^n * 3.

Using substitution method: an+1 = 4*an => an = 4^(n-1) * a0

Using a0 = 3, we get: a1 = 4a0 = 43 = 12 a2 = 4a1 = 443 = 4^2 * 3 a3 = 4a2 = 44^2 * 3 = 4^3 * 3 a4 = 4a3 = 4*4^3 * 3 = 4^4 * 3

So, an = 4^n * a0 = 4^n * 3.

(b) Describe Binomial Theorem.

(c) Explain Catalan numbers with suitable examples.

(a) Explain de Bruijn graph.

A de Bruijn graph is a directed graph that is widely used in the field of bioinformatics to assemble DNA sequences. It is named after the Dutch mathematician Nicolaas Govert de Bruijn who introduced the concept in 1946.

In a de Bruijn graph, each node represents a k-mer (a string of length k) that is a substring of the DNA sequence. The edges in the graph represent the overlap between two k-mers. Specifically, a directed edge connects two nodes if the k-1 suffix of the first node matches the k-1 prefix of the second node. The resulting graph is a compact representation of all possible k-mers that occur in the DNA sequence, along with their overlaps.

The de Bruijn graph is useful for genome assembly because it allows for the reconstruction of the original DNA sequence from short reads. Given a set of short reads, the de Bruijn graph can be constructed, and then the original sequence can be reconstructed by traversing a path through the graph that covers all nodes exactly once.

(b) What is recurrence relation? Explain different types of recurrence relation.

(c) For the following set of weights construct an optimal binary prefix code. For each
weight in the set give corresponding code word. 5,7,8,15,35,40.

OR

(a) Which trees are complete bipartite graphs?

Complete bipartite graphs are not trees because they contain cycles. However, there is a special type of tree called a “bipartite tree” that is a subgraph of a complete bipartite graph.

A bipartite tree is a tree in which the nodes can be partitioned into two disjoint sets such that no two nodes in the same set are adjacent, and all edges connect a node in one set to a node in the other set.

So, in a complete bipartite graph, any spanning tree that preserves the bipartition of the nodes is a bipartite tree.

(b) How summation operator used in generating function?

(c) Solve the recurrence relation an = an-1 + n with the initial term a0 = 4.

â€œDo you have the answer to any of the questions provided on our website? If so, please let us know by providing the question number and your answer in the space provided below. We appreciate your contributions to helping other students succeed.”