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".
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 .
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
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.
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?
The teacher is making a critical mistake. There are two types of transitive closure matrices that can be made. One is called Strict Transitive Closure and is represented by A+ (plus symbol superscript). In this matrix, we do NOT include the selected vertex, meaning A cannot reach itself unless there is a loop that allows it to reach itself (loop length must BE greater than 0! IMPORTANT) Then there's the other transitive closure matrix known as the Reflexive Transitive Closure. It is represented by A* (* symbol superscript). In this matrix, we DO include the selected vertex, meaning A can reach itself since this matrix accepts loops of length greater or equal than 0 The difference between two is, A+ only accepts passage way to other vertexes that are greater than 1 or 1. A* accepts passage ways to other vertexes (this time including itself, since passage way to itself is 0) that are greater than 0 or 0.
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.
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
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 .....😅
sir can you please explain how A will reach to A again in the adjacent matrix...i feel their is a flaw in solution
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".
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 .
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
There is no path from A to A
So how did you write the path from A to A?
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.
Great sir...you have clear my doubt
Please make video on DFS algorithm
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?
The teacher is making a critical mistake. There are two types of transitive closure matrices that can be made. One is called Strict Transitive Closure and is represented by A+ (plus symbol superscript). In this matrix, we do NOT include the selected vertex, meaning A cannot reach itself unless there is a loop that allows it to reach itself (loop length must BE greater than 0! IMPORTANT)
Then there's the other transitive closure matrix known as the Reflexive Transitive Closure. It is represented by A* (* symbol superscript). In this matrix, we DO include the selected vertex, meaning A can reach itself since this matrix accepts loops of length greater or equal than 0
The difference between two is, A+ only accepts passage way to other vertexes that are greater than 1 or 1.
A* accepts passage ways to other vertexes (this time including itself, since passage way to itself is 0) that are greater than 0 or 0.
Thank You So So Much Sir🙏🙏🙏🙏
we can also use bfs right..?
i think the diagonals should be 0 as there is no selfloop
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.
He is correct check algorithm first @@Anime_Animation_Illustration
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
Today my xm this is video is very helpful ❤️
How can reach form a to a 🤔
Same doubt bro
Because it is same node re
please provide the code for this Qs.
Thank you sir ❤❤❤❤
Big help again, thank you!
Sir, please explain TSP!
Thank you, sir; it was great.
Please send me some material about(Transit function and betweenness) if you have any!
please teach particle swarm algorithm
thanks alot sir!!
Wrong teaching. There is no path for node a.
Please check it Again.
thank you. very useful
Ossm sir I'm easily understand to see ur videos 🥰TQ u so much sir
Is the transitive closure of this graph is correct??
nope
Thank You.
thank you
Tqu so much sir
7 minutes for only describing a matrix!!! I thought you are also describing the Floyd-Warshall algorithm.
Ty
check this out.. shortest code ever
galat padha rh ho
dimaag ki dahi ho gya kuch samj nhi aya
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.
Jake khud padh le pahele
Abey chutiye.... Loop kahan dikhaaya gaya hai Harr vertex Pai
Teach properly
Thank u from Algeria u really helped me 😭 😭🫶🏻