Talk:Graph theory

From Wikipedia, the free encyclopedia
Jump to: navigation, search

Too technical[edit]

The articles starts off fine until you reach the section on graph-theoretic data structures, then it becomes too technical. It is not clear why this section is included on this page. The link I can see is that the concept of graph (data structure) uses the structure and therefore theory of graph (mathematics), so should this section be moved to graph (mathematics) instead as an application?. It is not clear if this is actually a part of graph theory, about graph theory an extension or an application? I am not sure if splitting the applications section into subsections, and including it somewhere in that, with some explanation may help? Sorry if i appear dumb. Bg9989 (talk) 22:00, 3 March 2013 (UTC)

I agree -- it's big, technical, and not really on topic. It's certainly not more important to graph theory than the sections that follows it. --JBL (talk) 18:00, 4 March 2013 (UTC)
I agree that is is too technical, but not that it is not important. However, it should be moved to Graph (mathematics), renamed and rewritten. It should be renamed "Representing graphs on a computer". The explicit mentions of basic data structures (arrays, linked lists, ...) must be removed, and the various representations should be described at higher level (like pseudo-code vs. code). The main representations (which have a lot of technical variants) are
  • Incidence matrix
  • List of the name of the vertices and list of the edges, which are pairs of vertices
  • List of vertices, each linked to the list of the vertices connected to it by an edge
Also, the respective advantages of each representation should be discuted. For example, the last one is the best if the graph may change during the computation, and if one want to find paths in the graph.D.Lazard (talk) 19:19, 4 March 2013 (UTC)
We already have a separate article about representing graphs on a computer. It is Graph (abstract data type). —David Eppstein (talk) 21:13, 4 March 2013 (UTC)
I missed this article. This means that every people that is interested in groups and does know what is an abstract data type will also miss it (although I know what is an abstract data structure). However this article allows to make above suggested section "Representing graphs on a computer" shorter, with a hatnote {{main}}. D.Lazard (talk) 08:44, 5 March 2013 (UTC)
Yes, but this section should also be in the article on graphs in mathematics, not graph theory. --JBL (talk) 14:11, 5 March 2013 (UTC)
I agree Bg9989 (talk) 12:01, 9 March 2013 (UTC)

Mathematics or Computer Science?[edit]

This article starts with "In mathematics graph theory is the study [...]", which made think if it is right to classify Graph Theory in maths?

I think that in all the universities I have known, there are professors of the department of (theoretical) Computer Science that study graph theory. Also, courses of graph theory are typically taught to students of computer science.

So, maybe it would be better to change the article by saying that it is an area in the intersection of mathematics and computer science... What do you think about?

Lp.vitor (talk) 19:22, 29 August 2016 (UTC)

To me (and I speak as someone in a computer science department who does graph theory) graph theory is clearly mathematics, not computer science. It is heavily used in computer science, and graph algorithms are computer science, but graph theory itself is mathematics. —David Eppstein (talk) 19:25, 29 August 2016 (UTC)
Speaking as someone else in a CS department who does graph theory, I agree with David. McKay (talk) 03:17, 30 August 2016 (UTC)
Mathematics are likely to be applied (everywhere). David is absolutely right about graph theory being mathematics used in computer science. SlvrKy (talk) 12:23, 30 August 2016 (UTC)
Speaking as someone who earned a Ph.D. in computer science and had a pair of advisors—one each in mathematical sciences and computer science—David is absolutely right about graph theory being mathematics used in computer science. PaulTanenbaum (talk) 20:41, 30 August 2016 (UTC)