How to create a Personal Portfolio or Resume-CV Websites Design using HTML CSS JavaScript. Personal Portfolio or Resume-CV Websites Template Free Download

Hands-on Graph Theory – 1

Do you know that almost all kinds of problems in the world can be solved by making some roads and city problems? When graph theory was born, you and I were not even born, and there were no computers in the world! In the late 1700s, Leonard Euler invented graph theory to solve Königsberg’s seven bridges problem. Then it became clear to everyone that graph theory is no match for modeling any problem as a city-road problem. And whenever you can convert a problem into a known problem, it becomes much easier to solve.

Graph theory has many applications. The most common is to find the fastest way to get from one city to another. You may know that a webpage from the server has to go through many routers to reach your PC, graph theory is used to find the path from one router to another. During the war, if some roads of a country are blown up with bombs, the country’s capital will be separated from all the cities, it can also be deduced by graph theory. We will see many more applications when learning graph algorithms.

Our goal in this tutorial is to first learn some very basic definitions of graph theory, then learn how to store graph memory, then learn some basic graph algorithms, and at the same time see some interesting problems. If you look at all the definitions together, you won’t remember them, so if you don’t know them at all, I will look at some definitions first, then I will learn some more definitions as needed.

What is the graph?

Let’s say we marked 6 cities with 1,2,3,4,5,6. Now I draw a line between the cities that have direct roads to them:

There is no need to give the names of the cities with 1, 2 etc., you can give Dhaka, Chittagong etc. if you want. This is a very simple graph showing the roads between some cities. In the language of graph theory, cities are called nodes (Node) or Vertex (Vertex) and roads are called Edge (Edge). A graph is a collection of some nodes and some edges.

A node in a graph can mean many things, in a graph maybe a node means a city, in a graph an airport, in a graph it can mean a room on a chess board! And edge means the relationship between the nodes. An edge in a graph can show the distance between two cities, in a graph it can show the time to go from one airport to another, and if there is a knight in a room on the chess board, it can also show which room can be reached from that room.

The chess board in the picture below is also a graph. Each cell is a node. Edges are shown from the room where the horse is:

In short, the job of a node is to represent some kind of object and the job of an edge is to show the relationship between two objects.

B is called an adjacent node of A if there is an edge from node A to node B. Simply put, adjacent nodes are nodes directly connected by edges. A node can have many adjacent nodes.

Directed Graph and Undirected Graph:

In directed graph the edges have arrows, that means the edges are unidirectional, in undirected graph the edges are bidirectional. The following image will make it clear:

The graph on the left is directed, the right is undirected.

Weighted and Unweighted Graph:

Sometimes a graph may have Weight or Cost written in small letters next to the edges:

This weight or cost can mean many things, like how many kilometers are the distance between two cities, or how long does it take to travel through the road, or how many cars can travel along the road, etc. The previous graphs were unweighted, in which case we do not assume that all edges have a weight value of one (1). If all weights are 1, there is no need to write them separately.

path:

Path (Path) is the edges that can go from one node to another node. That is, a sequence of edges.

There can be many paths from one node to another. There are two paths from A to D in the figure. A->B,B->C,C->D is a path, the total weight of this path is 3+4+2=9. Again A->D can also be a path such that the total cost of the path is 10. The path which has the least cost is called the shortest path.

Degree:

In a directed graph, the number of edges entering a node is called indegree, and the number of edges leaving a node is called outdegree.

An undirected graph does not distinguish between indegree and outdegree. The number of adjacent nodes a node has is the degree of the node.

The Handshaking Lemma states that the number of nodes of an odd degree is always even. In the graph above, A and C have degree 3, they are nodes of odd degree. Then there are 2 nodes of odd degree, 2 being an even number. A handshake always takes 2 hands, just like an edge always connects 2 nodes. Just think about it:

Adding 2 even degree nodes with an edge creates 2 new odd degree nodes.

Adding 2 odd degree nodes with an edge reduces 2 odd degree nodes.

Adding 1 even and 1 odd degree node equals the total number of odd degree nodes (decrease on one side, increase on other side).

Then it is seen that either increases by 2 or decreases by 2 or remains the same, so the number of nodes of odd degree is always even.

Similarly, it can be shown that the sum of the degrees of a graph is twice the number of edges. In the graph above, the sum of degrees is 10, and the number of edges is 5.

These are very basic conversations. In the next article, you will learn how to store graphs in variables. Hope you have a great journey in graph theory and learn a lot.

## Join Our FreeWebsiteCreate Facebook Group to get an instant update for projects, templates, design resources, and solutions.

Free Website Create – HTML CSS, PHP, JavaScript Programming Projects For Free

## Thank You,

Stay with FreeWebsiteCreate.net

Share the post if necessary.

FreeWebsiteCreate.net tries to provide HTML, CSS, SCSS, JavaScript, React, Android Studio, Java, PHP, Laravel, Python, Django, C#(C Sharp), and ASP.net-related projects 100% free. We try to make learning easier. Free Website Create always tries to give free projects to new learners. Free projects and source code will help to learn quickly.

They can save time and learn more. In this post, we share a free portfolio project website code with HTML and CSS. This free code portfolio contains a single landing page with a responsive design. In this post, we get a free best carpenter and craftsman service website designed by FreeWebsiteCreate with HTML, CSS, Bootstrap, and JavaScript.

To get a free website project code,