Definition: (1) Matrix, (2) Term rank of a matrix, (3) Chromatic Function, (4) Chromatic Index of G, (5) MAP.

Answer:

a) Matrix: The mxn matrix A = (aij) in which aij = 1 if ei (( si, and aij = 0 otherwise we call such a matrix, in which each entry is 0 or 1, a (0, 1) matrix.

b) The Term Rank of A Matrix: The term rank of A is the number of elements in a partial transversal of largest possible size.

For the figure, the term rank is 4.

c) Chromatic function: Let G be a simple graph and Let PG (K) be the number of ways of coloring the vertices of G with K colors so that no two adjacent vertices have the same color. PG is called the chromatic function of G.

For example, if G is the free, shown in the figure then PG (k) = K (K-1)2

d) Chromatic Index of G: if G is K colorable (e) but not (K-1) colorable (e) we say that the chromatic index of G is K and write X` (G) = K.

For example, the figure shown for which X’ (G) = 4.

e) MAP: A map is defined as a representation, usually on a flat surface of a whole or part of an area. The job of a map is to describe spatial relationships of specific features that the map aims to represent.

Define

A flow of a network: A flow in a network is a function p that assigns to each are a non-negative real number p(a), called the flow in a, in such a way, that,

i) For each are - a, p(a) ≤(( (a);

ii) The out-degree and in-degree of each vertex, other than v or w, are equal.

What is edge-disjoint paths?

Edge-disjoint paths: The maximum number of paths from v to w, no two of which have an edge in common such path are called edge-disjoint paths.

For this figure, the edge-disjoint paths is E1 = {ps, qs, ty, tz} and E2 = {uw, xw, yw, zw}.

1) Matrix representation of a graph 2) The eight circle problem 3) Six people at a party.

Discuss the application domain of
Explain that any simple graph with in vertices has ……… edges is connected.
Prove that the ………. of spanning trees at ……..
Brooks algorithm.

Matrix Representation of a graph?

Answer:

If G is a graph with vertices labelled {1, 2, ….. , n} its adjacent matrix A is the nxn matrix whose ij-th entry is the number of edges joining vertex I and vertex j. in addition, the edges are labelled {1, 2, ….., m} its incident matrix M is the nxm matrix whose ij-th entry is 1 if vertex i is incident to edge j, and o otherwise.

The Eight Circles Problem?

Answer:

Place the letters A, B, C, D, E, F, G, H into the eight circles in figure, in such a way that letter is adjacent to a letter is next to it in the alphabet.

There are 8! = 40320 ways of placing eight letters into eight circles. The move systematic approach –

1) The easiest letters to place are A and H because each has only one letter to which it cannot be adjacent.

2) The hardest circles to fill are those in the middle as each is adjacent to others.

This suggest that we place A and H is in the middle circles. If we place A to the left of H, then the only possible for B and G are shown in figure.

The letter C must now be place on the left-hand side of the diagram, and F must be placed on the right-hand side. Then the figure –

Describe application domains?

Answer:
Application domains are – - Computer graphics - Robotics - Geographic information systems - CAD/CAM

Computer Graphics: Computer graphics is concerned with creating images of modeled seems for display on a computer screen, a printer, or other output device. The scenes vary from simple two-dimensional drawings, 3-dimentional scenes including light, tenures etc. it also includes over a million polygons or curved surface patterns.

Because, scenes consist of geometric objects, geometric algorithms play an important role in computer graphics.

Robotics: As robots are geometric objects that operate in a 3-dimensional space the real world, the geometric problems arise at many places.

Other geometric problems occur in the design of robots and work cells in which the robot has to operate.

Geographic Information Systems: A geographic information system, or GIS for short, stores geographical data like the shape of countries, the height of mountains, population density or rainfall.

The combination of different types of data is one of the most important operations in a GIS. So geometric algorithm plays important role.

CAD/CAM: CAD concerns itself with the design of products with a computer. CAM involves many geometric problems. CAD answer different types of questions which require geometric algorithm.

Others applications –

- Molecular modelling

- Pattern recognition

Convex Hulls:

A subset S of the plane is called Convex if and only if for any pair of points p, q ( s the line segment pq is completely contained is S. The convex hull CH (s) of a set S is the smallest convex set that contains S, it is the intersection of all convex sets that contain S.

Describe Six People at a Party

Answer:

Problem: Show that in any gathering of six people, there are either three people who all know each other or three people none of whom knows either of the other two.

Solution: To solve this, we draw a graph in which represent each person by a vertex, and join two vertices by a solid edge if the corresponding people known each other, and by a dotted edge if not we must show that there is always a solid triangle or a dotted triangle.

Let V be any vertex. Then there must be exactly five edges includes with v, either solid or dashed and so at least three of these edges must be of the same type.

Let us assume that there are three solid edges, the case of at least three dashed edges is similar.

If the people corresponding to the vertices w and x, know each other, then v, w and x from a solid triangle similarly, if the people corresponding to the vertices w and y, or to the vertices x and y, know each other, then we again obtained a solid triangle.

Finally, it no two of the people corresponding to the vertices w, x and y know each other, then w, x, and y form a dotted triangle.

Define: 1) Chromatic Polynomial, 2) K-colorable, 3) K-chromatic graph

Answer:

K – Colorable: if G is a graph without loops, then G is k-colorable if we can assign one of k-colors to each vertex so that adjacent vertices have different colors.

K – Chromatic graph: if the graph G is k-colorable, but not (K-1) colorable, we say that G is K-chromatic or the chromatic number of G is k and write X (G) = K.

Chromatic Polynomial: The chromatic polynomial is a polynomial studied in algebraic theory, it counts the number of graph colorings as a function of the number of colors. So we can write that,

The chromatic polynomial of a graph G counts the number of its proper vertex colorings. It is commonly denoted by PG (k).

For, example, for the figure, PG (K) = K (K – 1) (K – 2)

Graph Theory

Definition

Graph: A graph is a representation of a set of points and of how they are joined up and any metrical properties are irrelevant.

Simple Graph: Graphs with no loops or multiple edges are called simple graphs.

Directed Graph: A Graph with direction is called directed graph.

Walk: A walk is a ‘way of getting from one vertex to another; and consists of a sequence of edges, one following after another.

For example: P ( Q ( R is a walk

Eulerian Graphs: A connected graph G is Eulerian if there exists a closed trail containing every edge of G,

Or,

A connected graph G is Eulerian if and only if the degree of each Vertex of G is even.

Hamilton Graph: A Hamilton cycle is a cycle that visits each vertex exactly once. A graph that contains a Hamilton cycle is called a Hamilton graph.

Convex Polygon: A convex polygon is a simple polygon cohose interior is a convex set. In convex polygon –

• Every internal angel is less than or equal to 180 degrees.

• Every line segment between two vertices remains inside or on the boundary of the polygon.

Concave Polygon: A concave polygon is a polygon that have an interior angle that is greater than 1800

Given for cubes whose faces are colored red, blue, Green and Yellow …. Figure below can ………… colors appear on each side of the resulting 4(1 stack? Solve.

Answer: We solve this problem by representing each cube by a graph with four vertices, R, B, G and Y. one for each color. In each of these graphs, two vertices are adjacent if and only if the cube in question has the corresponding colors on opposite face. The graphs corresponding to the cubes are shown in fig.

Now superimpose these graphs to form a new graph G.

A solution of the puzzle is obtained by finding two sub-graphs H1 and H2 of G. The sub-graph H1 tells us which pair of colors appear on the front and back each cube, and the sub-graph H2 tells us which pair of colors appears on the and right. To this end, the sub-graphs H1 and H2 have the following properties –

• Each sub-graph contains exactly one edge from each cube.

• The sub-graphs have no edges in common.

• Each sub-graph is regular of degree 2.

Describe Gift-Wrapping Algorithm
Answer: In Gift-wrapping algorithm we can start with an extreme point, find its neighbors in the hull by finding the supporting lines and continue from these neighbors in the same way. This algorithm is known as the gift wrapping algorithm.

We start with one vertex of the gift and wrap with hull around the gift by finding neighbor after neighbor.

Algorithm Gift Wrapping (P1, P2, .…, Pn)

Input: P1, P2, .…, Pn (a set of points in the plane)

Output: P (the convex hull of P1, P2, .…, Pn)

Begin

Set P to be the empty set

Let P be the point in the set with the largest x co-ordinate.

Add p to P;

Let L be the line containing P which is parallel to the x axis;

While P is not complete do.

Let q be the point such that the angle between the line –p-q and L is minimal among all points.

Add q to P;

L: = line –p – q –

P: = q

End.

Complexity: To add the Kth point ot the hull, we find the minimum and maximum angles among n-k lines. Therefore, the gift-wrapping algorithm complexity is O(n2).

Definition of Property loss? write Graham’s Sean algorithm.

Answer:

Graham’s Sean Algorithm

Algorithm Graham’s Sean (P1, P2, .…, Pn)

Input: P1, P2, .…, Pn (a set of points in the plane)

Output: P (the convex hull of P1, P2, .…, Pn)

Begin

Let P1 be the point in the set with the largest x coordinate (and smallest y coordinate if there are several points with the same largest x coordinate);

Use algorithm simple-polygon to arrange the points around P1 in sorted order; let the order be P1, P2, .…, Pn;

q1: = p1;

q2: = p2;

q3: = p3;

m: = 3;

for k: = 4 to nd:

while the angle between –qmT and –qm-pk+1- is less than or equal to 1800 do m: = m-1;

m: = m+1

qm: = p;

End.

Id count is odd then Inside: = true

Else Inside := false

Determine whether a point is inside a polygon and write algorithm?

To determine whether a point is inside or outside the polygon, the first intuitive approach to try to reach the outside boundary of the polygon from the given point. When we try this approach, we count the number of intersections with edges of the polygon until the outside is reached. In general the point is inside the polygon if and only if the number of intersections is odd, and outside the polygon if and only if the number of intersections is even.

In the figure, for the point P1 the number of intersections is 2, so the point is outside from the polygon and for point P2 the number of intersections is 1. So the point is inside of the polygon.

Algorithm

Algorithm point in polygon (P, 1)

Input: P (a simple polygon with vertices P1, P2, .…, Pn and edges e1, e2, …, en) and p (a point).

Output: Inside (A Boolean variable)

Begin

Pick an arbitrary point s outside the polygon;

Let L be the line segment q – s;

Count: = 0;

For all edges es of the polygon do

If e1 intersect L then

Increment count;

If count is odd then inside: = true

Else inside: = false

End

Describe how to construct a simple polygons & write down Sean Algorithm.

Answer: To construct a simple polygon, consider a large circle c that contains all the points. Sean the area of C by a rotating line originally originating from the center of C. Let’s assume that the rotating line never touches more than one point from the set at a time. Then the rotating line connect the points in the order they are encountered in the Sean and we get a simple polygon.

However, there is a problem. We solve this problem by sort the points according to their position in the circle centered at? These position can be computed by sorting the angles between a fixed line and the lines from Z to the other points. If two points have the same angle, they are further sorted according their distance from z. we then connect to the point the smallest angle and to the point with the largest angle, and connect the other points in order.

Here, we also calculate slopes because it is easier to calculate slopes than angles.

Algorithm

Algorithm simple polygon (P1, P2, .…, Pn);

Input: P1, P2, .…, Pn (points in the plane)

Output: P (a simple polygon)

Begin

For i = 2 to n do

Compute the angle xi between the line –P1-Pi and the x axis;

Sort the points according to the angles x2, …. xn

P is the polygon defined by the list of points in sorted order.

End.

Cycle Graphs: A connected graph that is regular of degree 2 is a cycle graph. We denote the cycle graph on n vertices by Cn.

Path graphs: The graph obtained from cycle graphs Cn by removing an edge is the path graph on n vertices, denoted by Pn.

Wheels: The graph obtained from Cn-1 by joining each vertex to a new vertex v is the wheel on n vertices, denoted by Wn.

Regular graphs: A graph in which each vertex has the same degree is a regular graph. If each vertex has degree r, the graph is regular of degree r or r-regular.

Bipartite Graphs: If the vertex set of a graph G can be split into two disjoint sets A and B so that each edge of G joins a vertex of A and a vertex of B, then G is a bipartite graph.

A complete bipartite graph is a bipartite graph in which each vertex. In a is joined to each vertex in B by just one edge.

Cubes: of special interest among the regular bipartite graphs the cubes. The K cube Qk is the graph whose vertices correspond to the sequence (a1, a2, .…, ak) where each a1 = 0 or 1 and whose edges join those sequences that differ in just one place.

The complement of a simple graph: If G is a simple graph with vertex srt v(G), its complement G is the simple graph with vertex set V(G) in which two vertices are adjacent if and only if they are not adjacent in G.

Atonic Graphs: of interest among regular graphs are the platonic graphs, armed from the vertices and edges of the five regular solids the ………., cube, icosahedron and dodecahedron.

Describe the minimum cornceior problem.

Answer: We can reformulate the problem in terms of weighted graphs. We denote the weight of the edge e by 10(e), and our aim is to find the spanning true T with least possible total weight W (T).

For example,

If there are five cities, shown in figure, then we start by choosing the edge AB (2) and BD (3). We cannot choose the edge AD (4). Since it would create a cycle ABD. So we choose the edge DE (W5). We cannot then choose the edges AE by BE. Since we would create a cycle, so we choose the edge BC. This complete the tree.

Define cut vertex?

A separating set in a connected graph is a set of vertices whose delrhion disconnect G. If a separating set contains only one vertex V, we call V a cut vertex.

Here, V is a cut-vertex.

Describe Convex Hull algorithm?

Algorithm Convex Hull (P)

Input: A set P of points in the plane.

Output: A list containing the vertices of CH (P) in clockwise order.

1. Sort the points by x-coordinate, resulting in a sequence P1…..Pn.

2. Put the points P1 and P2 in a list Lupper, with P1 as the first point.

3. For i 3 to n

4. Do append Pi to Lupper

5. While Lupper contains more than two points and at least three points in Lupper do not make a right turn.

6. Do delete the middle of the last three points from Lupper.

7. Put the points Pn and Pn-1 in a list L lower with Pn as the first point.

8. For i ( n-2 down to 1

9. Do append Pi to Llower.

10. While Llower contains more than 2 points and the last three points in Llower do not make a right turn.

11. Do delete the middle of the last three points from Llower.

12. Remove the first and last point from Llower to avoid duplication of the points where the upper and lower hull meet.

13. Append Llower and Lupper and the result list L.

14. Return L.

Example: A natural way to represent a polygon is by listing its vertices in clockwise order, starting with an arlmtory one. So, the problem we want to solve is this: given a set P = {P1, P2, .…, Pn} of points in the plane, compute a list that contains those points from P that are the vertices of CH (P), listed in clockwise order,

Input: Set of points;

P1, P2, P3, P4, P5, P6, P7, P8, P9

Output: Representation of Convex Hull.

P4, P5, P8, P2, P9

Algorithm Slow Convex Hull (P)

Input: A set P of points in the plane.

Output: A list L containing the vertices of CH (P) in clockwise order.

1. E. Q

2. For all ordered pairs (P, q) E P(P with P not equal to q.

3. Do valid ( true

4. For all points r E P not equal to Porq

5. Do if r lies to the left of the directed line from p to q.

6. Then valid ( false

7. If valid then add the directed edge pq to E.

8. From the set (/E of edges construct n list L of vertices of CH (P) sorted clockwise order.

Application Domains

- Computer Graphics

- Robotics

- Geographic information systems.

- CAD/CAM

Describe travelling salesman problem?

Answer: In this problem, a travelling salesman wishes to visit several given cities and return to is starting point, covering the least possible total distance. For example, if there are five cities A, B, C, D and E and if the distances are given. In figure, then the shortest possible routes is A ( B ( D ( E ( C ( A giving a total distance at 26, as well can be seen by inspection.

This problem can also be reformulated in terms of weighted graphs. In this case, the requirement is to find a Hamilton cycle of least possible total weight in a weighted complete graph.

One possible algorithm is to calculate the total distance for all possible Hamiltonian cycles, but this is far too complicated for more than about five cities. For example, if there are 20 cities, then the number of possible cycle is (191)/2 which is about 6(1016.

Define (1) spanning tree, (2) Cycle rank of graph G, (III) cutset rank of graph G.

Answer:

1) Spanning Tree: Given any connected graph G, we can choose a cycle and remove any one of its edges and the resulting graph remains connected. We repeat this procedure with one of the remaining cycles, containing until there are no cycles left. The graph that remains is a tree that connects all the vertices.

A graph is planar if and only if it contains no sub-graph contractible

Answer:

Sketch of proof: Assume first that the graph G is non-planar. Then, by Kuratowski’s theorem, G contains a sub-graph H homeomorphic to K5 or K3 or successively contracting edges of H that one incident to a vertex of degree 2, we see that H is contractible to K5 or K3.

Now assume that G contains a sub-graph H contractible to K3 and let the vertex V of K3 arise contracting the sub-graph Hv of H.

The vertex V is incident in K3.3 to three edges e1, e2 and e3. When regarded as edges of H, these edges are incident to three vertices v1, v2 and v3 of Hv. If V1, V2 and V3 are distinct, then we can find a vertex w of H and three paths from W to these vertices, intersecting only at w.

It follows that we can replace the sub-graph Hv by a vertex w and three paths leading out of it. If this construction is carried out for each vertex of K3.3 and the resulting paths joined up with the corresponding edges of K3.3 then the resulting sub-graph is homeomorphic to K3.3 follows from kuratowski if theorem that G is non-polar.

What is Homeomorphic Graph?

Answer

Homeomorphic Graph: To graphs to be homeomorphic if both can be obtained from the same graph by inserting new vertices of degree 2 into its edges.

For example, any two cycle graphs are homeomorphic,

K3, 3 and K5 are non-planar?

Answer:

Proof: Suppose first that K3,3 is planar, has a cycle u ( v ( w ( x ( y ( z ( u of length 6, any plane drawing must contain this cycle drawn the form of a hexagon, as shown in figure.

Now the edge we must the either wholly inside the hexagonal or wholly outside it. We deal with the case in which we was inside, the hexagon, the other is similar. Since the edge ux must not cross the edge wz, it must lie outside the hexagon; the situation is now as in figure: b. it is then impossible to draw the degree vy, as it would cross either ux or wz. This gives the required contradiction.

Now suppose that K5 is planar.

Since K5 has a cycle v ( w ( x ( y ( z (v of length 5, any plane drawing must contain this cycle, drawn in the form of a pentagon, as shown figure.

Now the edge wz must lie either wholly inside the pentagon or wholly outside it. Since the edges vx and vy do not cross the edge wz. They must both lie outside the pentagon, the figure is shown below –

But the edge xz cannot cross the edge vy and so must lie inside the pentagon. Similarly the edge wy must lie inside the pentagon, and the edges wy and wz must hem cross. This gives the required contradiction.

What is Dual graphs?

Dual graphs: Given a plane of a planar graph G, we construct another graph G called the dual of G. the construction is in two stages –

1) Inside each face of G we choose a point v – these points are the vertices of G.

2) Corresponding to each edge of G we draw a line that crosses e and joins the vertices v in the faces f adjoining e these lines are the edges of G.

Describe Euler’s Formula?

Answer:

If G is a planar graph, then any plane drawing of G divides the set of points of the plane not lying on G into regions, called faces. In each case, the face f4 is unbounded, it is called the infinite face.

We map the graph onto the surface of a sphere by stereo graphic projection.

We now rotate the sphere so that the point of projection lies inside the face we want as the infinite fare, and then project the graph down onto the plane tangent to the sphere at the South Pole. The chosen face is now the infinite face.

So, we now prove the Euler’s formula that, what even the plane drawing of a planar graph we take, the number of faces is always, the same.

Describe Hall’s marriage problem?

Answer:

Hall’s marriage theorem: The marriage theorem, proved in 1935 by Philip Hall, answers the following question, known as the marriage problem. If there is a finite set of girls, each of whom knows several boys, under what conditions can all the girls marry the boys in such a way that each girl marries a boy she knows.

For example, if there are four girls {g1, g2, g3, g4} and five boys {b1, b2, b3, b4, b5} and the friendship are shown in figure, then a possible solution is for g1 to marry b4, g2 to marry b1, g3 to marry b3 and g4 to marry b2.

This solution is by taking G to be the bipartite graph in which the vertex set is divided into two disjoint sets v1 and v2, and where each edge joins a girl to a boy she knows.

A complete matching: A complete matching from v1 to v2 in a bipartite graph G (v1, v2) in a one-one correspondence between the vertices in v1 and a sub-set of the vertices v2, such that corresponding vertices are joined.

Marriage Condition: For the solution of the marriage problem, every K girls must know collectively at least k boys, for all integers k satisfying 1≤K≤m, when m denotes the total number of girls.

Solution

Here,

E = {b1, b2, b3, b4, b5} and so, F = {g1, g2, g3, g4}

S1 = {b1, b4, b5}

S2 = {b1}

S3 = {b2, b3, b4}

S4 = {b2, b4}

Theorem 251: Necessary and sufficient condition for a solution at the concerned problem is that each set collectively knows at least k boys for 1≤K≤m.

Proof:

Using induction on m, assume that the theorem is true if the number of girls is less than m.

The theorem is true if m = 1.

Suppose that there m girls. There are two cases to consider.

1) If every k girls collectively knows at least k+1 boys, so that the condition is always true, with one boy to spare. The original condition then remains true for the other m-1 girls, who can be married by inductions completing the proof in this case.

2) If now there is a set of k girls who collectively know exactly K boys, then these K girls can be married by induction to the K boys. If any collection of h of these m-k girls, for h≤m-k, must know at least h of the remaining boys, otherwise fewer than h+k boys, contrary to our assumption. It follows that the original condition applies to the m-k girls.

They can therefore be married by induction in such a way that everyone is happy and the proof is complete.

Describe ……… theorem?

Answer: ………………………………. Paths connecting two given vertices v and w in a graph G. Now, the maximum number of paths from v to w, no two of which have an edge. In common such paths are called …… disjoint paths. Now, the maximum number of paths from v to ………….. vertex in common, except, of course v and w these are called vertex disjoint paths.

For example, in the graph there are four edge disjoint paths and two vertex disjoint ones.

In the figure, the sets E1 = {ps, qs, ty, tz} and E2 = {aw, xw, yw, zw} are vw disconnecting sets and V1 = {s, t} and v2 = {p, q, y, z} are vw-separating sets.

What us capacity?

A digraph to each area of which is assigned a non-negative real number called its capacity.