Page 1 of 1

Graph theory terminology

Posted: Thu Jul 13, 2017 2:53 pm UTC
by Bloopy
https://en.wikipedia.org/wiki/Graph_theory
A graph in this context is made up of vertices, nodes, or points which are connected by edges, arcs, or lines.


Could also throw links & ... in the mix, or:

Drags & traps?
Spaghetti & meatballs?
2x4s & sycamores?

Re: Graph theory terminology

Posted: Thu Jul 13, 2017 6:40 pm UTC
by Nyktos
Does anyone really say "line"? I've heard "link", but not that. And "arc" is usually only used in the directed case, in which case you could also throw in "arrow" as an option.

The different terms for vertices are a legitimate source of disagreement. In my experience mathematicians tend to prefer "vertices" and computer scientists "nodes", but that's far from 100% in either case. Some people also say "node" only in the case that the graph is a tree.

In any case, this is only scratching the surface of graph theory terminology disagreements. The real religious wars are about whether a "path" is allowed to repeat vertices and whether the unmodified term "graph" allows for loops and/or parallel edges.

Re: Graph theory terminology

Posted: Thu Jul 13, 2017 7:19 pm UTC
by Soupspoon
For a tree, leaf (end-points), branchings (non-ending-points1, and branches themselves (lines) all 'stem' from a root (base node, even though often depicted at the top!) might be used. But at what point do we go from descriptive to (vaguely?) thematically analogous, in the naming convention?


1 Except those only doubly linked as a choiceless transit node. Depends how strict/optimal the tree is.

Re: Graph theory terminology

Posted: Fri Jul 14, 2017 10:01 am UTC
by Derek
Edges and vertices doing math. Nodes is acceptable when programming.

Re: Graph theory terminology

Posted: Fri Jul 14, 2017 10:01 am UTC
by Derek
Edges and vertices doing math. Nodes is acceptable when programming.

Re: Graph theory terminology

Posted: Fri Jul 14, 2017 10:16 am UTC
by Flumble
Vertices are the 0-dimensional attributes of 3D models and 3D models only, so the endpoints of edges in graphs are nodes. Also node is easier to type a thousand times when programming something that uses graphs (or their sub-types).

Towns and roads. Because those words definitely make sense for directed graphs, non-planar graphs and multigraphs. On the other hand, like spaghetti and meatballs, those words aren't used in mathematics for anything else, so it's not even that bad of an idea. :roll:

Re: Graph theory terminology

Posted: Fri Jul 14, 2017 11:18 am UTC
by EvanED
No one going to try to start a holy war over "vertices" vs "vertexes"?

Vertexes all the way.

Re: Graph theory terminology

Posted: Fri Jul 14, 2017 11:30 am UTC
by Xenomortis
EvanED wrote:No one going to try to start a holy war over "vertices" vs "vertexes"?
Vertexes all the way.

No, because we all know the correct answer there.
Vertices, you heathen!

I tend to say "node", but that's because I usually deal with graphs in a programming context.
I was definitely taught "vertex", but very rarely dealt with graphs in a maths context.

I hardly ever explicitly refer to the edges, but I suspect I would use the term "line" (probably because I'd be drawing them), maybe "edge" if I remembered to use the "correct" name.

Re: Graph theory terminology

Posted: Fri Jul 14, 2017 11:59 am UTC
by Soupspoon
EvanED wrote:No one going to try to start a holy war over "vertices" vs "vertexes"?

Vertexes all the way.

Noden! (And linii, obviously.)

Re: Graph theory terminology

Posted: Fri Jul 14, 2017 9:19 pm UTC
by Bloopy
Flumble wrote:those words aren't used in mathematics for anything else

It's definitely satisfying to pick words that don't conjure up distracting thoughts from within your domain. I tried "link" but went off it quickly as it's become a buzzword. If you combine it with anything it looks like a top-level name, ie. names of organisations, software applications, web portals and so on. JobLink, LearningLink, StudyLink, WineLink...

So it's nodes & edges for me. I dug up my project report on topological sorting from my final year of university which I hadn't looked at in a decade, and I was indeed using nodes & edges back then too. My current application is music-related, so I'm enjoying that edge makes a bit of an eigenpun on the straight edge subculture.

Re: Graph theory terminology

Posted: Fri Jul 21, 2017 3:08 pm UTC
by moiraemachy
Nyktos wrote:Does anyone really say "line"? I've heard "link", but not that. And "arc" is usually only used in the directed case, in which case you could also throw in "arrow" as an option.

I was never taught graph theory formally and neither were my peers, soo... anything besides "lines" is confusing. If I said "edges", people would consider the drawn figure, not the graph itself. "Arc" is confusing because 90% of the arcs are drawn as straight lines. "Link" is okay.

Re: Graph theory terminology

Posted: Fri Jul 21, 2017 4:12 pm UTC
by Nyktos
moiraemachy wrote:
Nyktos wrote:Does anyone really say "line"? I've heard "link", but not that. And "arc" is usually only used in the directed case, in which case you could also throw in "arrow" as an option.

I was never taught graph theory formally and neither were my peers, soo... anything besides "lines" is confusing. If I said "edges", people would consider the drawn figure, not the graph itself. "Arc" is confusing because 90% of the arcs are drawn as straight lines. "Link" is okay.
It's not clear to me why "edge" suggests a drawn figure but "line" doesn't.

Re: Graph theory terminology

Posted: Fri Jul 21, 2017 6:47 pm UTC
by EvanED
"Line" would confuse me; I think this thread is the only time I've heard that term used for what I've almost always heard called edges.

Re: Graph theory terminology

Posted: Fri Jul 21, 2017 7:57 pm UTC
by chridd
EvanED wrote:No one going to try to start a holy war over "vertices" vs "vertexes"?

Vertexes all the way.
I prefer Latin suffices over English ones. (I also prefer pseudo-Latin.)

Re: Graph theory terminology

Posted: Sat Jul 22, 2017 10:08 am UTC
by phlip
Vertopodes.

Re: Graph theory terminology

Posted: Sun Jul 23, 2017 3:57 am UTC
by EvanED
chridd wrote:I prefer Latin suffices over English ones
I believe you mean English "onei".

Re: Graph theory terminology

Posted: Mon Jul 24, 2017 5:32 pm UTC
by moiraemachy
Nyktos wrote:
moiraemachy wrote:
Nyktos wrote:Does anyone really say "line"? I've heard "link", but not that. And "arc" is usually only used in the directed case, in which case you could also throw in "arrow" as an option.

I was never taught graph theory formally and neither were my peers, soo... anything besides "lines" is confusing. If I said "edges", people would consider the drawn figure, not the graph itself. "Arc" is confusing because 90% of the arcs are drawn as straight lines. "Link" is okay.
It's not clear to me why "edge" suggests a drawn figure but "line" doesn't.
It's not that it doesn't suggest the drawn figure, it's that the suggestion works: when drawn lines intersect, edges stop being edges but lines don't stop being lines. Also, if you graph looks like a convex thing, edges can mean "sides". You only get this sort of problem (drawn stuff != graph stuff) with "lines" when nodes line up.