My text book mentions transitive closure but did not give an example. Thanks so much for the clear example. Question: Closure is when we perform said operations on ALL vertices without adding any new elements to our set. Yes? Also, the edges don’t alow paths in both directions. So this makes it non-commutative. If they were bi-directional, it would be commutative - yes?
sir i don't think in a directed graph each vertex is obviously reachable to itself. i think what it means is "starting from a vertex v, can we get back to v following any path in the graph?". Let me know your thoughts.
of course not, but that's not what the graph is saying. think, if we knew that [2,1] is a path, then of course [2,1] -> [1,1] is also a valid way to reach node 1. if the matrix is not made this way the algorithm will fail
You're right. Otherwise, the diagonal from left-to-right would always be filled with 1's in the transitive closure and that would not convey much useful information. Also, in the video, you cannot reach A starting from A (there exists no path, at 1:10) but he marked it as 1 in the transitive closure, which means he actually meant that "it is obvious every vertex can reach itself".
sir your videos on graph theory is good and no doubt everybody can easily understand. sir i am requesting you please make videos on graph coloring ,vertex coloring,np completeness and linear programming in graph theory. I am eagerly waiting for response. Thanking you sir
sir can u upload more questions on dynamic programming for interview purpose and sir upload daily one algorithm please sir i request you you should daily upload one algorithm please sir
thanks for the video! quick Question: is diagonal always 1? meaning any vertex can reach itself? it doesn't need a self-circle edge? i thought without self-circle edge self reach=0.
Noo here if we start from say a.. we will get back to a ; So here we'll take diagonal as 1.. i.e. if we do have a closed path for any vertex we can take its diagonal one as 1 or else 0 ..
@@Tyokok if a node has a self circle then its quite good it will be having 1 in its diagonal...but here look into the question if we start from 1 we will get back to 1.. that means a path exsits .. so we will take it as 1 .
In a digraph D, prove that a vertex y is reachable from a vertex x if and only if D contains an (x, y)− path. 2. Show that a digraph D is strong if every vertex of V (D) is reachable from every vertex other vertex of V (D). 3. Show that a digraph D is strong if and only if it has a closed Hamilton walk. 4. Develop a strong digraph D = (V, A) and extract possible separator from D.
this is wrong. First, this isn't how the algorithm to obtain the transitive matrix is preformed. Second, a path from A to A signifies a looped edge. Thus, all values on the main diagonal [top left corner to bottom right corner] should all be zero because this graph has no looping edges.
you're confusing between adjacent matrix representation of a graph and transitive closure , get a book cormen to be specific and see the algorithm on transitive closure maybe you can understand that he is correct.
![[MPD직캠] 베이비몬스터 직캠 8K 'FOREVER' (BABYMONSTER FanCam) | @MCOUNTDOWN_2024.7.11](http://i.ytimg.com/vi/ylRx8QOuGXo/mqdefault.jpg)
I'm a French student the day before my exam, and thank you very much for this video ;)
Pareil c est fou, ya peu de contenu en français sur ça
Oh I failed it btw, but still ^^
@@AnnoyedUnicorn ohhh you still came back after a year .....😅
My text book mentions transitive closure but did not give an example. Thanks so much for the clear example. Question: Closure is when we perform said operations on ALL vertices without adding any new elements to our set. Yes? Also, the edges don’t alow paths in both directions. So this makes it non-commutative. If they were bi-directional, it would be commutative - yes?
Big help again, thank you!
sir can you please explain how A will reach to A again in the adjacent matrix...i feel their is a flaw in solution
Great sir...you have clear my doubt
Please make video on DFS algorithm
sir i don't think in a directed graph each vertex is obviously reachable to itself. i think what it means is "starting from a vertex v, can we get back to v following any path in the graph?". Let me know your thoughts.
I think you are correct.
With the methode I learned with my math professor, we addition to the identity Matrix, so obviously, he is right ;)
of course not, but that's not what the graph is saying. think, if we knew that [2,1] is a path, then of course [2,1] -> [1,1] is also a valid way to reach node 1. if the matrix is not made this way the algorithm will fail
Yes u are correct i guess
You're right. Otherwise, the diagonal from left-to-right would always be filled with 1's in the transitive closure and that would not convey much useful information. Also, in the video, you cannot reach A starting from A (there exists no path, at 1:10) but he marked it as 1 in the transitive closure, which means he actually meant that "it is obvious every vertex can reach itself".
sir your videos on graph theory is good and no doubt everybody can easily understand. sir i am requesting you please make videos on graph coloring ,vertex coloring,np completeness and linear programming in graph theory. I am eagerly waiting for response. Thanking you sir
sir can u upload more questions on dynamic programming for interview purpose
and sir upload daily one algorithm please sir i request you you should daily upload one algorithm please sir
we can also use bfs right..?
thanks for the video! quick Question: is diagonal always 1? meaning any vertex can reach itself? it doesn't need a self-circle edge? i thought without self-circle edge self reach=0.
I learned it this way as well...
@@vibranteye4369 what you mean? can you make it clear please? So it should 0 or 1, and the meaning of each? Thanks a lot!
Noo here if we start from say a.. we will get back to a ; So here we'll take diagonal as 1.. i.e. if we do have a closed path for any vertex we can take its diagonal one as 1 or else 0 ..
@@manognadevineni8901 so you saying regardless we have self-circle edge, we always set diagonal to 1, like convention ?
@@Tyokok if a node has a self circle then its quite good it will be having 1 in its diagonal...but here look into the question if we start from 1 we will get back to 1.. that means a path exsits .. so we will take it as 1 .
thank you. very useful
In a digraph D, prove that a vertex y is reachable from a vertex x if and only if D
contains an (x, y)− path.
2. Show that a digraph D is strong if every vertex of V (D) is reachable from every vertex
other vertex of V (D).
3. Show that a digraph D is strong if and only if it has a closed Hamilton walk.
4. Develop a strong digraph D = (V, A) and extract possible separator from D.
please teach particle swarm algorithm
Sir, please explain TSP!
please provide the code for this Qs.
There is no path from A to A
So how did you write the path from A to A?
Today my xm this is video is very helpful ❤️
thanks alot sir!!
this is wrong. First, this isn't how the algorithm to obtain the transitive matrix is preformed. Second, a path from A to A signifies a looped edge. Thus, all values on the main diagonal [top left corner to bottom right corner] should all be zero because this graph has no looping edges.
You are talking about Adjacent matrix 😅
you're confusing between adjacent matrix representation of a graph and transitive closure , get a book cormen to be specific and see the algorithm on transitive closure maybe you can understand that he is correct.
Thank You.
Thank you sir ❤❤❤❤
Thank you, sir; it was great.
Please send me some material about(Transit function and betweenness) if you have any!
Tqu so much sir
i think the diagonals should be 0 as there is no selfloop
thank you
Ossm sir I'm easily understand to see ur videos 🥰TQ u so much sir
Ty
Is the transitive closure of this graph is correct??
nope
How can reach form a to a 🤔
Same doubt bro
Because it is same node re
7 minutes for only describing a matrix!!! I thought you are also describing the Floyd-Warshall algorithm.
Wrong teaching. There is no path for node a.
Please check it Again.
check this out.. shortest code ever
A to C there is no path ..
Direct path from a to c is not there. But indirectly we can approach c from a by d in middle.
galat padha rh ho
Jake khud padh le pahele
Abey chutiye.... Loop kahan dikhaaya gaya hai Harr vertex Pai
Teach properly