Graph theory terminology

Please compose all posts in Emacs.

Moderators: phlip, Moderators General, Prelates

The one true graph jargon?

Lines & vertices
0
No votes
Lines & points
1
5%
Edges & nodes
6
30%
Arcs & nodes
0
No votes
Edges & vertices
11
55%
Arcs & points
0
No votes
Edges & points
0
No votes
Arcs & vertices
0
No votes
Lines & nodes
2
10%
Other
0
No votes
 
Total votes: 20

User avatar
Bloopy
Posts: 164
Joined: Wed May 04, 2011 9:16 am UTC
Location: New Zealand

Graph theory terminology

Postby Bloopy » Thu Jul 13, 2017 2:53 pm UTC

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?

Nyktos
Posts: 138
Joined: Mon Mar 02, 2009 4:02 pm UTC

Re: Graph theory terminology

Postby Nyktos » Thu Jul 13, 2017 6:40 pm UTC

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.

User avatar
Soupspoon
You have done something you shouldn't. Or are about to.
Posts: 2466
Joined: Thu Jan 28, 2016 7:00 pm UTC
Location: 53-1

Re: Graph theory terminology

Postby Soupspoon » Thu Jul 13, 2017 7:19 pm UTC

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.

Derek
Posts: 2145
Joined: Wed Aug 18, 2010 4:15 am UTC

Re: Graph theory terminology

Postby Derek » Fri Jul 14, 2017 10:01 am UTC

Edges and vertices doing math. Nodes is acceptable when programming.

Derek
Posts: 2145
Joined: Wed Aug 18, 2010 4:15 am UTC

Re: Graph theory terminology

Postby Derek » Fri Jul 14, 2017 10:01 am UTC

Edges and vertices doing math. Nodes is acceptable when programming.

User avatar
Flumble
Yes Man
Posts: 1943
Joined: Sun Aug 05, 2012 9:35 pm UTC

Re: Graph theory terminology

Postby Flumble » Fri Jul 14, 2017 10:16 am UTC

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:

EvanED
Posts: 4324
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI
Contact:

Re: Graph theory terminology

Postby EvanED » Fri Jul 14, 2017 11:18 am UTC

No one going to try to start a holy war over "vertices" vs "vertexes"?

Vertexes all the way.

User avatar
Xenomortis
Not actually a special flower.
Posts: 1396
Joined: Thu Oct 11, 2012 8:47 am UTC

Re: Graph theory terminology

Postby Xenomortis » Fri Jul 14, 2017 11:30 am UTC

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.
Image

User avatar
Soupspoon
You have done something you shouldn't. Or are about to.
Posts: 2466
Joined: Thu Jan 28, 2016 7:00 pm UTC
Location: 53-1

Re: Graph theory terminology

Postby Soupspoon » Fri Jul 14, 2017 11:59 am UTC

EvanED wrote:No one going to try to start a holy war over "vertices" vs "vertexes"?

Vertexes all the way.

Noden! (And linii, obviously.)

User avatar
Bloopy
Posts: 164
Joined: Wed May 04, 2011 9:16 am UTC
Location: New Zealand

Re: Graph theory terminology

Postby Bloopy » Fri Jul 14, 2017 9:19 pm UTC

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.

moiraemachy
Posts: 186
Joined: Wed Jan 04, 2012 9:47 pm UTC

Re: Graph theory terminology

Postby moiraemachy » Fri Jul 21, 2017 3:08 pm UTC

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.

Nyktos
Posts: 138
Joined: Mon Mar 02, 2009 4:02 pm UTC

Re: Graph theory terminology

Postby Nyktos » Fri Jul 21, 2017 4:12 pm UTC

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.

EvanED
Posts: 4324
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI
Contact:

Re: Graph theory terminology

Postby EvanED » Fri Jul 21, 2017 6:47 pm UTC

"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.

User avatar
chridd
Has a vermicelli title
Posts: 760
Joined: Tue Aug 19, 2008 10:07 am UTC
Location: ...Earth, I guess?
Contact:

Re: Graph theory terminology

Postby chridd » Fri Jul 21, 2017 7:57 pm UTC

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.)
~ chri d. d. /tʃɹɪ.di.di/ (Phonotactics, schmphonotactics) · they (for now, at least) · Forum game scores
mittfh wrote:I wish this post was very quotable...
flicky1991 wrote:In both cases the quote is "I'm being quoted too much!"

User avatar
phlip
Restorer of Worlds
Posts: 7543
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: Graph theory terminology

Postby phlip » Sat Jul 22, 2017 10:08 am UTC

Vertopodes.

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

EvanED
Posts: 4324
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI
Contact:

Re: Graph theory terminology

Postby EvanED » Sun Jul 23, 2017 3:57 am UTC

chridd wrote:I prefer Latin suffices over English ones
I believe you mean English "onei".

moiraemachy
Posts: 186
Joined: Wed Jan 04, 2012 9:47 pm UTC

Re: Graph theory terminology

Postby moiraemachy » Mon Jul 24, 2017 5:32 pm UTC

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.


Return to “Religious Wars”

Who is online

Users browsing this forum: No registered users and 4 guests