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

Install Virtual Environment

VIRTUAL ENV Virtualenv is a tool to create an isolated Python environment. In this post, we will learn how to setup virtualenv on ubuntu. Prerequisite pip Install Virtualenv If you have pip3  sudo pip3 install virtualenv if you have pip sudo pip install virtualenv Create a Virtualenv virtualenv venv venv is a directory in which virtual environment will be created. Working with Virtualenv source venv/bin/activate Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Post a Comment
Read more

Equations

In general we frame real life problems into some mathematical formula called equations in which we use constant and some variables(unknown) Example: Ram is 12 years old.Ram 's age is 3/5 of Shyam's age what is Shyam's age. Let Shyam's age is x then 3/5 of sham's age is 3*x/5 x*3/5=12 x=60/3=20 so Shyam's age is 20. Linear equations When there is a linear combination of unknown variables is there then eqn is linear Example: 3x+ 2y+ 4z=9 Non Linear Equations: Equations in which non linear combination of the variable is there then eqn is non linear. When any 2 unknown variable multiplication present in the equation then it is the nonlinear equation. Example: 2x+5yz=98 is a nonlinear equation because yz multiplication is there: Quadratic equation in one variable: x^2 + 4*x + 2=0 is non linear because unknown variable x is being multiplied in term x^2 Quadratic equation in many variable: x^2 + y^2 +z^2 + w=0 cubic equati...
Post a Comment
Read more

How Machine Learning (ML) Work

How Machine Learning (ML) Work In this post, We will learn how machine learning work. What is machine learning (ML) ? Machine learning is a study of model that compute use to progressively improve their performance on a specific task. What is Machine learning models ? Machine learning model contains a set of instruction or mathematical formula or in simple word it contain a piece of code in which we provide some data as input and model return some output. We learn more about model and how use a machine leaning model latter. How Machine Learning (ML) Work  ? This part we will understand with an example. Suppose want to have a simple application which will take a picture and banana or apple and application will tell us either it is banana or apple or picture is neither banana nor apple. To solve this problem first we provide a set of banana picture to our model and we will tell our model that this is a banana picture similarly we will provide a set of apple...
7 comments
Read more

How to install certificates for command line

Install Certificates In this post, We will learn how to install the certificate on Ubuntu with the command line. Open your terminal and execute the following sequence of command. Here mycert.cer is the certificate that you want to install. $ sudo cp mycert.cer /usr/share/ca-certificates/mycert.pem $ sudo dpkg-reconfigure ca-certificates $ sudo update-ca-certificates $ git config --global http.sslCAInfo /usr/share/ca-certificates/mycert.pem Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
1 comment
Read more