↓ Ir para o conteúdo principal

← todas as notas

📎 Webclip

Understanding graph theory will seriously enhance your engineering skills

The thread argues that understanding graph theory is crucial for engineering, because many seemingly different systems (internet, brain, social relations, cities) are networks that can be studied with a common language. It introduces graphs as abstract relation spaces made of vertices and edges, explains that their layout is arbitrary, and defines walks, trails, paths, and cycles to reason about direct and indirect connections. With these notions, the author raises questions of connectivity and how removing certain vertices or edges (cut vertices/edges) can fragment a graph, and points to further material on trees and longer posts.

Reading notes
#

  • Graph theory is presented as a way to seriously improve engineering skills, something the reader “must absolutely” become familiar with.
  • Very different systems like the internet, the brain, one’s acquaintances, and a city all share the structure of networks that express relationships between objects.
  • Despite their differences, these networks share properties such as a notion of distance, where elements can be considered closer or farther in various senses.
  • Graph theory studies networks of interconnected elements to uncover fundamental properties that apply across many kinds of networks.
  • A graph is described as a finite collection of vertices (or nodes) connected by edges, representing an abstract space of relations.
  • Edges encode who is related to whom, independent of the specific nature of the relationship.
  • Names and precise positions of vertices in drawings are not intrinsic; the same graph can be laid out in infinitely many ways.
  • The layout of a graph is arbitrary, so many different visual representations can depict the same underlying structure.
  • Indirect connections matter as much as direct ones and are formalized as walks, which are finite sequences of connected nodes.
  • A concrete example of a walk is given as the sequence (a, b, a, e, c, d) on a sample graph.
  • If no edge is repeated in such a sequence, it is called a trail; the earlier walk is not a trail because it backtracks along edge ab.
  • The sequence (a, e, c, d, e) is given as a valid trail, since vertex e can reappear as long as different edges are used.
  • When no vertex is repeated in the sequence, it is a path; (c, d, e, a, b) is given as an example that includes all vertices.
  • If a path’s final vertex loops back to its starting vertex, so start and end coincide, this is called a cycle.
  • Vertices and edges form the basic building blocks of graphs, which then give rise to walks, trails, paths, and cycles.
  • With these concepts in hand, one can ask structural questions such as which vertices are reachable from each other, referred to as connectivity.
  • A central connectivity question is how critical a particular vertex or edge is for keeping the graph connected.
  • If removing a single vertex (or edge) splits a connected component into two or more, that vertex (or edge) is called a cut vertex (or cut edge).
  • In the example graph, removing vertex a and its edges yields five connected components, while removing vertex b yields three.
  • Removing just the edge ab in the same graph results in two connected components.
  • The author announces that the next installment will discuss trees, described as arguably the most important data structure in computer science.
  • This thread is stated to be a collaboration with Alejandro Piad Morffis and covers only about 15% of a longer post.
  • The full post can be found in the alt text of an image mentioned in the thread.
  • The author invites readers who enjoyed the thread to share it, follow for more technical content, or respond positively to help visibility.
  • A reply notes that an earlier post covers related material, emphasizing an undervalued connection between matrices and graphs.
  • The illustrations in the thread are made using Inkscape, according to a reply.
  • In a response, the author comments that graph theory is powerful: translating a problem into graphs can either make it quickly solvable or reveal it as very hard.
  • The author confirms that the full version of the post is available where a commenter suggested.
  • Another reply says that a class on this topic will probably be one of the most useful classes for the student.
  • The author mentions an earlier post dealing with directed graphs and their matrix representation, calling directed graphs extremely important.
  • A later reply mentions that upcoming posts will cover algorithmic graph theory, including implementations.
  • Sales of the author’s material are handled via Gumroad, which generates invoices, and support is offered via direct messages.
  • The author credits collaborator Alejandro Piad Morffis heavily, saying the content is mostly his work.