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
Негізгі бет Which Sequences are Graphical? (Degree Sequences and Havel-Hakimi algorithm) | Graph Theory
No video
Пікірлер: 68