6.042J Lecture Notes - Lecture 17: Triangle Inequality, Well-Ordering Principle, If And Only If

• School: MIT
• Department: Electrical Engineering and Computer Science
• Course: 6.042J
• Professor: Albert Meyer

Document Summary

The in-degree of a vertex in a digraph is the number of arrows coming into it, and similarly its out-degree is the number of arrows coming out of it. If g is a digraph and v v(g), then. The immediate consequence of this de nition is indeg(v) = outdeg(v) Picturing digraphs with points and arrows makes it natural to talk about following successive edges through the graph. The sequence of edges followed in a particular way is called a walk through the graph. A path is a walk which never visits a vertex more than once. The natural way to represent a walk is with the sequence of successive vertices it went through, such as 1 2 4 12. However, it is conventional to represent a walk by an alternating sequence of successive vertices and edges, such as. 1 <1 2> 2 <2 4> 4 <4 12> 12. So a walk v is a sequence of the form.