Wednesday 21 June 2023

 What Bipartite Graphs actually do?

This is a question which kept going in my head for years, so I decided to look into how bipartite graphs actually works? I mean what they are exactly used for?

So, I started learning discrete mathematics again where I found a link between different optimization technics and how they are correlated with each other and with the Bipartite Graphs also.

I came-up with the example on the fly which is related to the mating selection among animal species and how it helps in better understanding of this particular graph method.

Below, are some of the points which are taken from my video, and I hope this makes the understanding of optimization approaches in real life.

Studying bipartite graphs in discrete mathematics

Discovered bipartite graphs while studying discrete mathematics

Bipartite graphs have two disjoint sets with no connections within the sets.

Optimizing decision making through bipartite graphs

Graphs are used to optimize decision making in various scenarios such as traveling to a city

Bipartite graphs help make efficient connections between subsets, ensuring happiness for both males and females.

Bipartite graphs help in making connections between large number of nodes efficiently.

By dividing nodes into two subsets, connections can be made between them without having to connect each node individually.

This method is particularly useful when dealing with a large number of nodes, such as in matchmaking scenarios.

Using optimization to match characteristics and eliminate irrelevant species

Approach involves a probabilistic way of thinking

Eliminating irrelevant species to focus on specific characteristics.

Using the Hungarian method to optimize matching based on weights

Consider weights of meals and match with females based on proximity

Eliminate unnecessary paths to optimize matching

Preference is important in both males and females

Evolutionary biology has made males and females have preferences

Preference is important in various scenarios like railway ticket reservation

Consider preferences in seat selection using stable marriage algorithm

Weighted Hungarian method doesn't consider preferences. (Weights are given to the edge and preferences are given to the nodes)

Stable marriage algorithm considers both weights and preferences.

Bipartite graphs are used to optimize connections between two disjoint sets.

Removing certain connections heuristically to optimize the graph.

Introduction of the weights and preferences so we have to optimize connections further.

For a detailed explanation watch the video.

No comments:

Post a Comment

Do we really understand how loops work?

                                Particularly in programming! Back in 2014 when I used to take my programming classes, I spent around one and...