Skip to main content

Eulerian circuit

Eulerian circuit

In this tutorial, We will learn about a special type of graph circuit called  Eulerian circuit

Eulerian circuit

A simple circuit is a walk where first and last point are the same and no edges are repeated. A Euler’s circuit is a simple circuit which uses all possible edges of the graph. The vertices can be repeated.
The definition of Eulerian circuits arose from the problem of Konigsberg bridges


Konigsberg Bridges Problem: There are four regions connected with seven bridges. Can you go through all the bridges without revisiting any bridge? Here in figure left side representing the Konigsberg bridges and right side figure is a theoretical representation of the bridge (edge) and cities (vertices). The question is equivalent to finding a Eulerian circuit in the graph.

A connected graph (not necessarily simple) has a Eulerian circuit iff all vertices have even degree.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Labels:

Comments

Post a Comment

Popular posts from this blog

SSC Practice Problem Solution

SSC Practice Problem Solution In this post, we will discuss solution of  SSC Practice Problem . Question 1  The efficiency of (A + B) = 100/24 = (25/6)% The efficiency of (A + B + C) = 100/8 = (25/2)% The efficiency of C = 25/2 – 25/6 = (50/6)% Hence, C can alone finish this job in = 100/(50/6) = 12 days Answer: 12 days option (1) Question 2  Original price = Rs. 6000; Price after discount = 6000 – 1200 = Rs. 4800; Price after raising service contract = 4800 + 480 = Rs. 5280 Answer: Rs. 5280 option (2) Question 3  Suppose the received money by A, B, and C is respectively 5x, 6x, and 9x. 5x = 450; => x = 90; Hence, the total money = 20x = 20*90 = Rs. 1800; Answer: Rs. 1800 option (2) Question 4 Suppose the Cost price of the bag= Rs. x; Hence, x + 0.15x = 230; => x = Rs. 200; Selling price after selling on 20% = 200 + 20% of 200 = Rs. 240 Answer: Rs. 240 option (3) Question 5  The required percentage ...
Post a Comment
Read more

Average

Average In this post, We will learn about average.  Average of any collection of data is the sum of data divide by number of data. Average = (Sum of observations /  Number of observations) Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.  problems The arithmetic mean of x, y and z is 80, and that of x, y, z, u and v is 75, where u=(x+y)/2 and v=(y+z)/2. If x ≥ z, then the minimum possible value of x is (CAT 2018) As specified in the question mean of x and y and z is 80 x+y+z=3*80 mean of x, y, z,u,v is 75 x+y+z+u+v=75*5 2u=x+y 2v=y+z x+y+z+((x+y+y+z)/2)=75*5 y+3(x+y+z)=75*10 y=750-720 y=30 since x+y+z=240 y=30 so x+z=210 since x>=z so minimum value of x=210/2 = 105 Problem2: In first 5 inings sehwag has scored at average of 40. In sixth ining He had scored 52 what is His average after 6th ining. one simple approach is getting total score divided by no of inin...
Post a Comment
Read more

Complex Number

Complex Number While solving the equation of the form  a x 2 + b x + c = 0 , the roots of the equations can take three forms which are as follows: Two Distinct Real Roots Similar Root No Real roots (Complex Roots) The introduction of complex numbers in the 16th century made it possible to solve the equation  x 2 + 1 = 0 . The roots of the equation are of the form  x = ± − 1 ‾ ‾ ‾ √  and no real roots exist. Thus, with the introduction of complex numbers, we have Imaginary roots. We denote  − 1 ‾ ‾ ‾ √  with the symbol i, where i denotes Iota (Imaginary number). An equation of the form z= a+ib, where a and b are real numbers, is defined to be a complex number. The real part is denoted by Re z = a and the imaginary part is denoted by Im z = b. Algebraic Operation on Complex numbers: Addition of two complex numbers Subtraction of two complex number Multiplication of two complex number Division of two complex number Power of Iota (i) ...
Post a Comment
Read more

Logarithm

Logarithm When a x   = N , then we say that x = logarithm of N to the base a and write it as x = log a N . In simple words, it represents the power to which a number must be raised. Let me expand on that by giving a simpler example. If we are asked, what would be the result if ‘a’ is multiplied with itself ‘b’ times; then your answer would be x = a*a*a*…. b (times). This can also be written as a^b. This is also known as ‘a raised to the power of b’ If we are asked, which number multiplied with itself ‘b’ times, will result in a; then you are asked for the value of x such that x*x*x*… b(times) = a => x^b = a => x = a^(1/b) This is also known as ‘bth root of a’ If swe are asked, how many times should you multiply ‘a’ with itself to get ‘b’, that is where the concept of logarithm comes into the picture. You are asked for the value of ‘x’ such that a*a*a…. x (times) = b => x = Log  a  b This is also known as ‘ Log b to the base a’ ...
Post a Comment
Read more