Which Sequences are Graphical? (Degree Sequences and Havel-Hakimi algorithm) | Graph Theory
ฝัง
- เผยแพร่เมื่อ 20 ต.ค. 2024
- How do we determine if a sequence is graphical? Remember that a sequence is graphical if it is the degree sequence of some graph. It is of course very easy, given a graph, to find its degree sequence. We just identify the degrees of its vertices then write those degrees in non-increasing order. We make it non-increasing so that the degree sequence is unique.
It is considerably more difficult to look at an arbitrary non-increasing sequence of non-negative integers and determine whether or not it is graphical - whether or not some graph has it as a degree sequence. Today we will look at 5 sequences and see some ways we may determine whether or not a sequence is graphical. In our final example we use a theorem telling us a sequence S is graphical if and only if another certain sequence, obtained from S, is graphical. This is the Havel-Hakimi algorithm, although I don't use that name for it in the lesson.
First Theorem of Graph Theory: • The First Theorem of G...
Every Graph has an Even Number of Odd Degree Vertices: • Proof: Every Graph has...
Intro to Degree Sequences: • Degree Sequence of a G...
★DONATE★
◆ Support Wrath of Math on Patreon for early access to new videos and other exclusive benefits: / wrathofmathlessons
◆ Donate on PayPal: www.paypal.me/...
Thanks to Robert Rennie, Barbara Sharrock, and Lyndon for their generous support on Patreon!
Follow Wrath of Math on...
● Instagram: / wrathofmathedu
● Facebook: / wrathofmath
● Twitter: / wrathofmathedu
My Music Channel: / @emery3050
Support the production of this course by joining Wrath of Math as a Channel Member for exclusive and early videos, original music, and upcoming lecture notes for the graph theory series! Plus your comments will be highlighted for me so it is more likely I'll answer your questions!
th-cam.com/channels/yEKvaxi8mt9FMc62MHcliw.htmljoin
Graph Theory course: th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
Graph Theory exercises: th-cam.com/play/PLztBpqftvzxXtYASoshtU3yEKqEmo1o1L.html
Thank you so much. My lecturer does not show any examples and just states theorems and proofs over and over again with no intuition behind these things. If only my tuition money could be going to people like you instead.
great setup, everything is decorated so well, that it is feeling soothing while watching the video
Thank you, that's exactly what I wanted to achieve with the Christmas videos! I wasn't able to do them last year simply because of time constraints, but if I can ever work on these full time, the Christmas set ups will be INTENSE.
this channel should have atleast 500k subscribers
Its now having close to 130k subs!
took me like half an hour to understanbd it throught my uni book which didnt explain it at all and 5 minutes from your video. Keep it up! Thanks a lot!
So glad it helped! Thanks for watching and if you're looking for more graph theory, check out my playlist! th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
@@WrathofMath Wow! Thanks. I have a sequence a=d1, d2... dn and one b=n-d1-1,..., n-dn-1, how can i prove this "prove a is graphical (iff) if only b is graphical". There are no numbers..
these videos are more informative than the class im paying thousands of dollars to take lol. I appreciate them a lot man, keep it up!!
I'm glad they've been helpful, thanks a lot for watching and let me know if you ever have any questions! Many more videos to come, and be sure to check out my Graph Theory playlist if you haven't already: th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
Same here, man. I was sent a load of pdfs at the start of the course and I'm expected to just read it all and assimilate it. Thank f**k for TH-cam and creators like this guy!
How'd the rest of your class go?
I'm a data science student and learning graph theory. I was having trouble understanding the concepts, thank god! that I found this channel. Sean, you're an amazing teacher, explanations are damn!.... I would really appreciate it if you could make some videos on the application of graph theory like stable allocation, pair matching, etc. Also, it'd be great to have some videos on topology and applications.
Only 12 minutes of video saved my few hours for preparing exam
Glad to help, thanks for watching!
this is the best video that ive been looking for.. thanks alot. just subbed
Glad to help, thanks for your support!
OMG THIS IS WAY TOO HELPFUL TY VERY MUCHHH
While drawing the graph can't we draw loops to show that it is graphical...please explain as I have my exam coming
Also pls tell that is {2,3,4,4,5} graphical is some multigraph possible to draw with this degree sequence
Very Precise Information Given...Great 😃👍👍
Thanks for watching!
just in time for my test tomorrow.. thank you so much!!!
Loving the christmas outfit :)
You're very welcome! Good luck on the test and thank you - I'm enjoying the season, it'll be a bummer to go back to normal videos after the end of December, but I think people will be ready for it haha!
So does “graphical” mean connected or disconnected graph? Also thank you for the precise explanation 🔥
Thank you so much for this! you saved my life!!!
Red is a bit distracting but the class is very good. Thanks for the video :)
Thank you for watching!
@Wrath of Math - I came back for some last-minute revision. You should put "Havel-Hakimi" in the title. It will make it easier for people to find and you'll get the views it deserves.
Thanks for the idea, you're right! I think I wasn't familiar with Havel-Hakimi name when I made this!
Great video, helped me a lot! I just have one question:
If we have a multigraph then the 3 3 1 1 sequence would be possible since we could have the vertices with degree 3 connect to each other and each of them with 1 vertice of degree 1 and then just add a loop to the vertices of degree 3 making it possible?
So you want to connect the vertices of degree 3 with the vertices of degree 1, then connect the vertices of degree 3 with each other, and finally create a loop on the vertices of degree 3? i think the sequence would be : [5 5 1 1],
But if you only create a loop on the vertices of degree 3, all while connecting 1 vertex of degree 3 to a vertex of degree 1, i think it would then work. the sequence would stay the same. no need to connect the vertices of degree 3 with each other, since a loop is counted twice in a degree.
if loops and disconnected graphs are allowed, for a non directed graph:
edges: (v1, v2),(v3, v4),(v3,v3),(v4,v4)
d1 = d2 = 1,
d3 = d4 = 2 + 1 = 3
sequence 3,3,1,1
However the algorithm used in the video is only for simple graphs.
Agreed! Surely in graph theory you could have one vertex with multiple loops coming off it. Then then number of edges will be greater then the number of vertices.
Havel-Hakimi? More like "Thanks for these lectures; yes indeed-y!" 🙏
Thank you so much for such an informative video
My pleasure!
thank u sir.....nice explanation ....INDIA
Very helpful video. 🎉
Glad it was helpful! Thanks for watching!
thank you so much, you always help me.😊❤️
You're very welcome, so glad I can help! Thanks for watching! 😀
Thanks a lot for excellent video!!
Glad to help, thanks for watching!
but does a lace not allow the sequence 3 3 1 1 to be done, with a lace on each of the 3s and by joining them you get to degree 3. And the other two 1 degress you just connect them to each other?
Great great great! Thank you soooo much for the help
Thank you❤
The last sequence has odd number odd ones. How is it graphical?
Great video. thank you so much
i just love u u make my life easier
Glad to help!
s3 could have 7 if there are loops? Am i wrong
Thank you for the video! is the theorem you used the Havel-Hakimi?
My pleasure, thanks for watching! And I am not sure if the theorem is due to Havel and Hakimi, or if they just published algorithms using the theorem.
great video. In my discrete math class, I am told that using the Havel-Hakimi algorithm is helpful to determine if a degree sequence is graphical, like S5, but I am told that to constructively prove it's graphical, I still need to draw a graph with such a degree sequence.
I am looking for helpful guide to drawing graphs from a degree sequence, knowing it is graphical. Advice? That'd be helpful. Start with the vertex of greatest degree, then draw them adjacent to the lesser degree vertices?
thanks for the help!
This was great. Thanks!
No problem, thanks for watching! If you're looking for more on graph theory, check out my playlist if you haven't yet: th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
@@WrathofMath Bookmarked!
Describe the conditions of the graph being graphical
oh baby the santa of math to save my fucking C in discrete 2 thank fuck your coloring video was clutch
Hell yeah - good luck my man!
Capgemini brought me here 😂😂
And Cognizant brought me here 😂
@@anupr7925 Can i know for what reason? Are you guys preparing to appear for their aptitude exam or are these videos recommended for skill upgrade?
1:26
awesome
What about (3 2 1 0)
Not graphical, consider the fact that the first vertex needs to be adjacent to all the others, which is impossible because of the 0.
While drawing the graph can't we draw the loops to show that it is graphical ....please explain as I have my exam coming