Bifalgorithm post · Brisk · Chapter 1

Why does the spatial positioning of vertices not change a graph?

Why does the spatial positioning of vertices not change a graph? (Brisk · Chapter 1) — "One important thing to understand about graphs is which aspects of a di…

Ideas in this flowchart

  • A graph is determined by its vertices and edges, not by their spatial arrangement.
  • The spatial positioning of vertices is arbitrary and is not part of the mathematical information represented by a graph.
  • Two diagrams represent the same graph when they contain the same vertices and the same edges between them.
  • In the prize fighter graph, Muhammad Ali and Sonny Liston can be placed differently while the graph remains the same.
  • In the MapQuest graph, physical locations can also be repositioned if all nodes and links remain the same.
  • Spatial layout is chosen for human convenience and aesthetic presentation.
  • Every vertex must be drawn somewhere, but its chosen location does not contribute mathematical information.
  • This is similar to a set, whose elements have no order even though they must be listed in some order when specified.
Feed/

Why does the spatial positioning of vertices not change a graph?

Channel

Brisk

1 page

"One important thing to understand about graphs is which aspects of a diagram are relevant. Specifically, the spatial positioning of the vertices doesn’t matter. In Figure 5.2 we drew Muhammad Ali in the mid-upper left, and Sonny Liston in the extreme upper right. But this was an arbitrary choice, and irrelevant. More specifically, this isn’t part of the information the diagram claims to represent. We could have positioned the vertices differently, as in Figure 5.5, and had the same graph. In both diagrams, there are the same vertices, and the same edges between them (check me). Therefore, these are mathematically the same graph.\n\nThis might not seem surprising for the prize fighter graph, but for graphs like the MapQuest graph, which actually represent physical locations, it can seem jarring. In Figure 5.3 we could have drawn Richmond north of Fredericksburg, and Virginia Beach on the far west side of the diagram, and still had the same graph, provided that all the nodes and links were the same. Just remember that the spatial positioning is designed for human convenience, and isn’t part of the mathematical information. It’s similar to how there’s no order to the elements of a set, even though when we specify a set extensionally, we have to list them in some order to avoid writing all the element names on top of each other. On a graph diagram, we have to draw each vertex somewhere, but where we put it is simply aesthetic."

Flowchart preview
Series cover
👍
0
0 comments0 shares

Sign in to view and post comments.