6.4 Minimum Spanning Tree | Properties of MST | Data Structures Tutorials

แชร์
ฝัง
  • เผยแพร่เมื่อ 23 ธ.ค. 2024

ความคิดเห็น •

  • @tarachandrahul1203
    @tarachandrahul1203 ปีที่แล้ว +43

    02:00 Minimum spanning trees are a subset of a given graph that contain the same number of vertices and a number of edges that is equal to the number of vertices minus 1.
    04:00 Minimum spanning tree is a tree that contains the same number of vertices as the graph and the number of edges in the spanning tree is one less than the number of vertices in the graph.
    06:00 The minimum spanning tree is the spanning tree with the lowest total edge weight.
    08:00 Minimum Spanning Tree (MST) is a tree with the minimum edge cost among all the possible spanning trees.
    10:00 Properties of Minimum Spanning Tree
    12:00 A complete graph of 4 vertices can have maximum 16 spanning trees.
    14:00 A complete graph has all pairs of vertices connected by one edge
    15:58 Properties of Minimum Spanning Tree

  • @spreddy7070
    @spreddy7070 4 ปีที่แล้ว +161

    Due to this covid education system is done with online classes etc .....during this period no one can concentrate on the topics which are told by the lectures. And when the exams has arrived each n every person is learning the subject to get pass marks .........we do not understand the topics when we open the books r PDFs without listening ....at dat tym Jenny's lecture is the best source for understanding every topics pin to pin so dat uh can write the xam very well n score the good marks . Tq Jenny's lecture for all the vds n making us understand n get a minimum thought of that topic .

  • @yashpandey350
    @yashpandey350 4 ปีที่แล้ว +216

    Small help for English students: Conversion of each Hindi sentence/words in English.Sorry for 1 second + -
    0:34: Now spanning tree of this graph would be
    3:31: So, Many spanning trees
    6:20: Minimum spanning tree is that whose total cost/weight of spanning tree is minimum out of all spanning trees' minimum cost/weight.
    7:27: Ok, see
    7:38: If you remove a single edge, a single one than that spanning tree would be disconnected
    7:55: So as many as edges in the spanning tree
    8:13: Distinct means different weights/costs, which means there is no same weight of any edge.
    8:21: There will only single MST and that would be unique
    8:26: If the edge case is not distinct then
    8:31: Suppose we have one graph and which has two or three edges whose weight is same this this this like that ok
    8:47: And
    9:17: This is the condition when edge weights are
    9:33: Talking about a complete graph. Complete graphs are those if each vertex of that graph is connected with another vertex.
    9:53: Here n is n to the power n-2, where n is the number of vertices of that graph.
    10:35: This will not happen that the graph is connected and it has no spanning tree. And that is not possible at least it has one spanning tree.
    10:57: Ok
    11:22: Ok
    11:32: Maximum edges can be removed are
    12:06: So maximum edges you can remove from this graph are
    12:10: What are its spanning trees, and spanning trees properties are
    12:24: Means how many edges
    13:00: So maximum edge you can remove only one
    13:04: We removed 1 and we got this spanning tree
    13:50: Complete graph has this property
    13:55: Now one of Its spanning trees, let us first draw all of its vertices.
    14:06: Number of edges would be
    14:13: Three edge could be that
    14:35: So maximum edges you can remove from this graph is (e-n+1)
    14:41: How many numbers of edges
    14:58: Ok, and how many edges we removed from this graph are: these three edges we have and we removed these three edges and if you remove another edge then this graph would be disconnected.
    15:20: So the maximum you can remove only
    15:32: Main properties, I already told you that there would be the same number of vertices and edges would be
    15:47: One more property of spanning-tree we can add
    Love you from India.

  • @themechanic_gj
    @themechanic_gj 4 ปีที่แล้ว +136

    this is a great help for people like me who's preparing in last minute😌

    • @arsalanalam8195
      @arsalanalam8195 3 ปีที่แล้ว +1

      Yes bro this is very helpfull for people like me and you who preparing in last minute

    • @arehonematodzi601
      @arehonematodzi601 2 ปีที่แล้ว +1

      @@arsalanalam8195 🤣🤣🤣🤣🤣i wonder how people who dont study in last minutes understand

    • @MUSAFIRBEFIQR
      @MUSAFIRBEFIQR 7 หลายเดือนก่อน

      after three years. where are you?

    • @themechanic_gj
      @themechanic_gj 7 หลายเดือนก่อน +1

      @@MUSAFIRBEFIQR working at Bosch!

  • @TheFarshid360
    @TheFarshid360 5 ปีที่แล้ว +41

    Thank you so much for your amazing videos on data structures it has been really helpful for my studies.

  • @kakashisensei6282
    @kakashisensei6282 3 ปีที่แล้ว +2

    abla sen olmasan ülkenin yarısı kalacak Thank you for all those, you are hero

  • @sharmisthasinhakashyap4949
    @sharmisthasinhakashyap4949 4 ปีที่แล้ว +9

    Add More Lectures of Operating system , best Lecture For Data Structure, really appreciative

  • @javadeveloper8695
    @javadeveloper8695 3 ปีที่แล้ว +2

    in pandemic students fells very deficulty thank you so mcuh please upload these kind video you explain in polite manner which comes explain in one time

  • @namangupta9582
    @namangupta9582 5 ปีที่แล้ว +13

    You are amazing mam.i just wished that you should be our college teacher.

  • @razarizvi7085
    @razarizvi7085 2 ปีที่แล้ว +3

    Thanks, a lot maam your videos are amazing and help me a lot in DSA and also in Artificial Intelligence. Huge Respect from Pakistan

  • @awaisaslam5284
    @awaisaslam5284 2 ปีที่แล้ว +8

    Tomorrow is my terminal exam and this helps me completely, now I'm going for merge sort and insertion sort.
    Thanks and respect for this. 👍👏

  • @surajjajoo6997
    @surajjajoo6997 4 ปีที่แล้ว +13

    Congratulations for 100k. Big fan of your teaching. Keep on uploading such videos

  • @sumitjaiswal855
    @sumitjaiswal855 5 ปีที่แล้ว +12

    Thanx mam for saving my semester

  • @rashmijoshi520
    @rashmijoshi520 4 ปีที่แล้ว

    Visited so many channels and dived through so many internet resources but find your teaching easy to get.

  • @Learn-With-Omar
    @Learn-With-Omar 10 หลายเดือนก่อน +1

    05:55I didn't understand how it could be possible to visit the vertices of the number 5 twice.
    .
    .
    thank you and I appreciate your hard work keep going

  • @khushibansal1437
    @khushibansal1437 5 ปีที่แล้ว +20

    Thank you ma'am you teach really well 😊

  • @alikhasanov7940
    @alikhasanov7940 2 ปีที่แล้ว

    i have started learning DS and hindi in her DS lectures , very efficient )))

  • @spbe-xg1qp
    @spbe-xg1qp 4 ปีที่แล้ว +4

    Beauty with brains...!

  • @saptarshichattopadhyay8234
    @saptarshichattopadhyay8234 ปีที่แล้ว

    When I come here to learn something, I do not check comment section....Thank you so much Madam.... ❤❤❤❤❤❤❤

  • @guruprasad1231
    @guruprasad1231 3 ปีที่แล้ว +1

    Ur explanation is simply perfect 🤝

  • @krishnapandurangmate963
    @krishnapandurangmate963 5 ปีที่แล้ว +4

    You are awesome in teaching.
    Please keep on making video on CS thank you☺

  • @shahidmalik6107
    @shahidmalik6107 4 ปีที่แล้ว +3

    Explained really well, respect from Pakistan.

  • @giridharpatro5239
    @giridharpatro5239 3 ปีที่แล้ว

    Love from India ❤️ the way you explain is awesome 😊😊

  • @babarkamranahmed
    @babarkamranahmed ปีที่แล้ว +3

    Simply Amazing. 😀 Tomorrow 12:00 PM is my Operations Research (OR) Exam and I googled just now "minimal spanning tree youtube" and found this video of yours link on second rank. Really helpful in creating concepts before reading lectures or books of MST. Do you have video series on other concepts of OR?

  • @hironakae
    @hironakae 3 ปีที่แล้ว +3

    your explanation is so thorough and clear! amazing.

  • @bishwajeetpandey1570
    @bishwajeetpandey1570 5 ปีที่แล้ว +11

    U are explaining very clearly, u have cleared all doubts 👍
    Can you please upload video on AA TREE and RED BLACK TREE 🙏

  • @AbhishekSharma-jd4km
    @AbhishekSharma-jd4km 5 ปีที่แล้ว +2

    Mam you are awesome.Firstly you look so humble and pretty(obviously),secondly you give crisp knowledge.Mam pls try to discuss gate questions after completing concept. Seprate video for pyq and practise questions.

  • @radhakrishna4355
    @radhakrishna4355 3 ปีที่แล้ว

    Thanks a lots madam i really understand your class more clear and understandable please video s much as easy way to easy too understand LOve you madam❤❤❤❤❤

  • @souravdas7014
    @souravdas7014 5 ปีที่แล้ว

    Thank you mam..you just make data structure easy for me that is crystal clear now..Again Thanx a lot

  • @teja2775
    @teja2775 5 ปีที่แล้ว +5

    The way your explanation is awesome thanks for sharing knowledge 👍👌 keep doing it, if possible do some programs in data structures happy learning :)

  • @vaibhavgupta777
    @vaibhavgupta777 หลายเดือนก่อน +1

    Thank You Mam So So Much🙏🙏🙏🙏

  • @mr.gymaholic6858
    @mr.gymaholic6858 2 ปีที่แล้ว +1

    Mam is so cuuuutee 🥺🥺🥺🥺

  • @sathvikbantupalli6449
    @sathvikbantupalli6449 5 ปีที่แล้ว +13

    Explain concept at left side of the board And algorithm at right side of the board .....so that viewers can understand the concept clearly

  • @mohanroxx4205
    @mohanroxx4205 2 ปีที่แล้ว

    Love ❣️ from vizag😍😍

  • @Monstagegaming
    @Monstagegaming 4 ปีที่แล้ว

    Mam your explanation is very well ..tq u so much mam

  • @chandanbs9897
    @chandanbs9897 4 ปีที่แล้ว +1

    Mam u r doing really a great job
    And ur videos of teaching r very helpful for us thank you so much 🙏
    Hattsoff to ur work👍

  • @farhanarshad7120
    @farhanarshad7120 4 ปีที่แล้ว +1

    Excellent 👌 work Mam

  • @sacman3001
    @sacman3001 4 ปีที่แล้ว +1

    super complete! Thank you so much!

  • @kishankushavaha6199
    @kishankushavaha6199 หลายเดือนก่อน

    this is example of brain with beauty...

  • @bokamsriramteja6228
    @bokamsriramteja6228 ปีที่แล้ว +5

    Mam I love you 💟😘😘😘

  • @ayushkumsrisri6264
    @ayushkumsrisri6264 5 ปีที่แล้ว +1

    Perfect explanation.

  • @awanishkumarsingh6994
    @awanishkumarsingh6994 3 ปีที่แล้ว +6

    love u mam

  • @pranjaltiwari8470
    @pranjaltiwari8470 2 ปีที่แล้ว

    Maam I am mechanical student but by your lecture video I managed to study my data structure

  • @paragggoyal1552
    @paragggoyal1552 2 ปีที่แล้ว +1

    That last property why is it written maximum, shouldn't the term used be 'exactly' in place of 'maximum'?
    Also, why only complete graph, won't all connected graphs holds that property true?
    e - n + 1 = e-(n-1).
    and (n-1) is the number of edges in a spanning tree, therefore, in all connected graphs having 'e' edges, we have to remove 'e-(n-1)'. == 'e-n+1'. Exactly.
    Am I wrong??
    Please reply.

  • @piyushmishra860
    @piyushmishra860 3 ปีที่แล้ว +1

    Tq so muchh mam 💖

  • @yedukondalug7933
    @yedukondalug7933 ปีที่แล้ว

    Good Explanation, super

  • @dhananjay4you
    @dhananjay4you 5 ปีที่แล้ว +1

    u make it easy mam..

  • @destiny8597
    @destiny8597 ปีที่แล้ว +1

    Love u mam 😍😗🤗

  • @aryanjoshi3859
    @aryanjoshi3859 5 ปีที่แล้ว +6

    Awesome Ma'am,:)

  • @tahirnawaz5989
    @tahirnawaz5989 2 ปีที่แล้ว

    Thanks a lot, this very helpful for me,,.

  • @fansbilever9676
    @fansbilever9676 4 ปีที่แล้ว

    Thanks a lot mam.
    Thank you so much.
    It will help me alot.🙏🙏🙏🙏🙏

  • @rajeshprajapati4863
    @rajeshprajapati4863 3 ปีที่แล้ว

    Thank you so much. Keep up the good work .

  • @praneethaavasarala4875
    @praneethaavasarala4875 3 ปีที่แล้ว

    Thank you so much. You explained really well.

  • @manjirasaraekanayakaalphys9256
    @manjirasaraekanayakaalphys9256 3 ปีที่แล้ว

    Thank u maam.Im frm sri lanka

  • @informato9449
    @informato9449 3 ปีที่แล้ว

    Excellent Explanation

  • @yeyuksel
    @yeyuksel 4 ปีที่แล้ว

    You are my new ma'am

  • @beingoutofthebox8906
    @beingoutofthebox8906 3 ปีที่แล้ว

    Thank you for such a sweet explanation

  • @vRKa_pvt_ltd
    @vRKa_pvt_ltd 17 วันที่ผ่านมา

    wouldn't the e-v+1 propety be true for every graph not just a complete graph?

  • @Suja_shitole
    @Suja_shitole 2 ปีที่แล้ว

    Just wow ❤️

  • @vishal_vibes
    @vishal_vibes 5 ปีที่แล้ว +1

    Mam please more videos on data mining and warehousing please
    Love the way you explain 👌👌

  • @vaishaliraj7173
    @vaishaliraj7173 4 ปีที่แล้ว

    Well explain mam,,,,,thanku so much 😇

  • @alifruslan2728
    @alifruslan2728 4 ปีที่แล้ว +1

    Thank you so much, I am pretty much clear about the topic, just I am not confident in the point why is E' needed to be |V|-1 ? Could anyone explain me? Thanks in advance.

  • @NVANAPALLIANUSHA
    @NVANAPALLIANUSHA 2 ปีที่แล้ว +3

    Mam could you please tell how to implement it

  • @vanisurada5633
    @vanisurada5633 ปีที่แล้ว

    Tq mam for explaining us

  • @yashpandey350
    @yashpandey350 4 ปีที่แล้ว +5

    A sweat girl/madam with quality of working hard.I mean wow..........

  • @suryadev9739
    @suryadev9739 5 ปีที่แล้ว

    Mam..u cover important formulas and concepts which will help in competetive Exams....Really Thanks to u Mam.....

  • @ddsadvitiya6705
    @ddsadvitiya6705 5 ปีที่แล้ว +4

    Explanation soft and beautiful....
    And one observation not related to study..you should have tried the Chinese chopstick hairstyle instead of that pink clip..

    • @HarshPatel-iy5qe
      @HarshPatel-iy5qe 5 ปีที่แล้ว

      😂😂bhai padhne aya hai balo ko dekhne

  • @ayushsrivastava5659
    @ayushsrivastava5659 5 ปีที่แล้ว +1

    The maximum number of STs possible is also dependent on number of edges?
    Like in last Example 6 edges were there, but the graph can be made out of 4 edges, then the STs would not be 16, isn't it?

    • @amangupta3342
      @amangupta3342 3 ปีที่แล้ว +1

      Yes I made all the ST's there are only 12 not 16. Then I calculated the formula too. It came out to be n!/2

  • @snehasuresh3871
    @snehasuresh3871 4 ปีที่แล้ว

    Thnk u maam, it help me to solve the problems thnk u so muchh

  • @hemalathakarri9448
    @hemalathakarri9448 3 ปีที่แล้ว

    Mam we give one formula to find number of spanning tree by using vertices but, that formula is applicable for any number vertices

  • @habibhasanshakil9086
    @habibhasanshakil9086 4 ปีที่แล้ว

    Really helpful....♥

  • @samiulislamdurjoy
    @samiulislamdurjoy 4 ปีที่แล้ว

    G 244
    two condition of spaning tree
    1. V'=V
    2. E'=|V|-1
    note: spanning tree should not contain any cycle
    note: To find Minimum spanning tree, eliminate maximum costed edge
    note: golden basic from7:19-final

  • @sudeshnadutta5702
    @sudeshnadutta5702 3 ปีที่แล้ว

    Hi, you said that disconnected graphs can't have STs but what if I have 3 connected components then can't we have 3 MSTs?

  • @chazrocks
    @chazrocks 4 ปีที่แล้ว

    Thankyou mam u helped me a lot♥

  • @vivekojha2825
    @vivekojha2825 7 หลายเดือนก่อน

    amazing videos ..........

  • @kommojuharesh3032
    @kommojuharesh3032 4 ปีที่แล้ว

    Super explanation mam

  • @Kaviyugamithran
    @Kaviyugamithran 4 ปีที่แล้ว +1

    Hi.... could you please explain about tree decompositions in detial.......

  • @bijayalaxmipatra2974
    @bijayalaxmipatra2974 3 ปีที่แล้ว

    Thanks so much 😍

  • @saritakumari-oh8fs
    @saritakumari-oh8fs 4 ปีที่แล้ว

    Router and switches using spanning tree data structute. Now I understand this

  • @HossamHassan-el1oe
    @HossamHassan-el1oe 5 ปีที่แล้ว

    thanks for your pure explanation ,you are amazing .Egypt

  • @nibedita__dey
    @nibedita__dey 4 ปีที่แล้ว

    Thank u ma'am for that amazing explanation

  • @hardikanand6153
    @hardikanand6153 2 ปีที่แล้ว

    What is the differnce between minimum spanning tree and a minimmal spanning tree of a graph?

  • @rajesht9702
    @rajesht9702 2 ปีที่แล้ว +2

    Thank You Madam 🙏

  • @livc.6761
    @livc.6761 3 ปีที่แล้ว

    Very helpful thank you

  • @syambabu9987
    @syambabu9987 ปีที่แล้ว

    very use full madam

  • @subhendupoddar7868
    @subhendupoddar7868 5 ปีที่แล้ว

    mam, why removing max(e-n+1) edges makes a graph ST? if we remove less than (e-n+1) edges will it make a Spanning tree(ST)? I mean shouldn't it be 'only' (e-n+1) instead of 'max'(e-n+1) edges

  • @tecnnicalskull9949
    @tecnnicalskull9949 3 ปีที่แล้ว

    Good video teacher

  • @Yateesh20
    @Yateesh20 2 ปีที่แล้ว +1

    Please consider a lecture on string matching techniques

    • @akshatmehta4538
      @akshatmehta4538 2 ปีที่แล้ว

      Bro idhar milega kuch dino mein
      th-cam.com/video/P0dmKnLJG4c/w-d-xo.html

  • @vishalchaurasia2402
    @vishalchaurasia2402 5 ปีที่แล้ว

    Amazing ma'am 💕😍

  • @vinayakpuri3855
    @vinayakpuri3855 2 ปีที่แล้ว

    Thanks mam 😊

  • @yadhu153
    @yadhu153 4 ปีที่แล้ว

    Thank you so much!

  • @Rohit-ez7pf
    @Rohit-ez7pf 5 ปีที่แล้ว +1

    Thanks

  • @Sanjayyadav-tn2fl
    @Sanjayyadav-tn2fl 3 ปีที่แล้ว

    How to find the weight of edges.
    Please help me with these thing

  • @kommojuharesh3032
    @kommojuharesh3032 4 ปีที่แล้ว

    Thank you so much

  • @glammakeupbysara
    @glammakeupbysara 5 ปีที่แล้ว

    Good language

  • @ishantsingh122
    @ishantsingh122 ปีที่แล้ว

    how to calculate weight of edges??

  • @RajKumar-jk9dm
    @RajKumar-jk9dm ปีที่แล้ว +1

    Also explain the complexity of these algorithms like Kruskal, Prims and Dijk stra , which one is better algorithm in average case ,best case and worst case

  • @ShobhitAshkMishra
    @ShobhitAshkMishra 3 ปีที่แล้ว

    HTML, CSS and JavaScript pr bhi video bnaiye 🙏 please !

  • @nishantpruthi1172
    @nishantpruthi1172 4 ปีที่แล้ว

    mam plz tell what is edge weight???

  • @dd9484
    @dd9484 3 ปีที่แล้ว

    the difference between a graph and tree is: grph must have cycle and tree must not have cycle? only one node is a tree or a graph?