Graph Theory And Combinatorics

Three boys B₁ , B₂, B₃, and four girls G₁, G₂, G₃, G₄ are such that i) B, is a cousin of G₁, G₃, G₄

ii) B, is a cousin of G₂ and G₄ iii) B₃ is a cousin of G2 and G₃.

If boys must marry a cousin girl, find the possible sets of such couples.

Find and solve a recurrence relation for the number of binary sequences of length n 1 that have no consecutive O's. 

The number of virus affected files in a system is 1000 ( to start with) and this increases 250% every two hours. Using a recurrence relation determine the number of virus affected files in the system after one day.

Solve the recurrence relation.

Using exponential generating function, find the number of ways in which four of the letter sin the word ENGINE be arranged.

A bag contains a large number of red, green, white and black marbles, with atleast 24 of each colour. In how many ways can one select 24 of these marbles, so that there are even number of white marbles and atleast six black marbles.

Using the generating functions, find the number of i) non negative, and ii) positive, integer solutions of the equation X₁+ X₂ +X₃ + x₄ = 25. 

An apple, a banana, a mango, and an orange are to be distributed to four boys B₁, B₂, B₃, B₄. The boys B₁ and B₂ do not wish to have apple, the boy B; does not want banana or mango, and BA refuses orange. In how many ways the distribution can be made so that no boy is displeased? 

In how many ways can the integers 1, 2, 3, ... 10 be arranged in a line so that no even integer is in its natural place?

In how many ways can the 26 letters of the English alphabet be permuted so that none of the patterns CAR, DOG, PIN, and BYTE occurs?

State and prove the principle of Inclusion - Exclusion for n sets.

In how many ways can one distribute eight identical balls into four distinct containers so that i) no container is left empty? ii) the fourth container gets an odd number of balls? 

Find the co-efficient of

ii) a²b³c²d⁵ in the expansion of (a + 2b-30-20+5)¹⁶

Find the co-efficient of

i) x⁹y³ in the expansion of (2x - 3y)¹² 

In how many of these arrangements

A and G are adjacent?

All the vowels are adjacent? 

How many arrangements are there for all letters in the word SOCIOLOGICAL?

Define:

i) Complete Bipartite Graph

Using Prim's algorithm, find a minimal spanning tree for the weighted graph shown below.

Explain the steps in Dijkstra's shortest path algorithm.

Explain prefix codes. Obtain an optimal prefix code for the message MISSION SUCCESSFUL. Indicate the code for the message.

Define:

iii) Full Binary Tree.

Define:

ii) Rooted Tree and

Define:

i) Spanning Tree

Define Trees. Prove that a tree with n- vertices has n-1 edges.

Find the chromatic polynomial for the following graph. If 5 colors are available, in how many ways can the vertices of this graph be properly colored? 

State and explain Kuratowski's theorem. Show that the graphs K₅ and K_3.3 are non-planar byre-drawing them. 

Prove that a connected planar graph G with n vertices and m (m-n2) regions in every one of its diagrams. 

Write a note on Konigsberg's seven Bridge problems.

Show that the following graph is isomorphic to Kuratowski's second Graph (K_3.3)

For a graph with n vertices and m edges, if  is minimum and  is maximum of the degrees of vertices show that 

Define:

iii) Induced Subgraph.

Define:

ii) Regular Graph and