Talk:Graph theory

This  level-4 vital article is rated C-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Computing Low‑importance This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.ComputingWikipedia:WikiProject ComputingTemplate:WikiProject ComputingComputing Low This article has been rated as Low-importance on the project's importance scale. Mathematics High‑priority This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics High This article has been rated as High-priority on the project's priority scale. Computer science High‑importance This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science High This article has been rated as High-importance on the project's importance scale. Things you can help WikiProject Computer science with: Here are some tasks awaiting attention: Article requests : Requested articles/Applied arts and sciences/Computer science, computing, and Internet Cleanup : Computer science articles needing attention Computer science articles needing expert attention Copyedit : Computing Expand : Computer science Infobox : Computer science articles without infoboxes Maintain : Timeline of computing 2020–present Photo : Find pictures for the biographies of computer scientists (see List of computer scientists) Computing articles needing images Stubs : Computer science stubs Unreferenced : WikiProject Computer science/Unreferenced BLPs Project-related : Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}}

Archives

1

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)Reply

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)Reply

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)Reply

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)Reply

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)Reply

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)Reply

I agree Bg9989 (talk) 12:01, 9 March 2013 (UTC)Reply

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)Reply

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)Reply

Speaking as someone else in a CS department who does graph theory, I agree with David. McKay (talk) 03:17, 30 August 2016 (UTC)Reply

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)Reply

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)Reply

elementary graph theory is often taught to computer science students. However, algebraic graph theory, spectral graph theory, etc. are usually in math departments. I am a bit surprised by this entire conversation. Graph theory is clearly mathematics, just because it is taught to computer science students does not change that. Do not computer science students take calculus? Isn't that still mathematics? — Preceding unsigned comment added by 2605:6000:1526:4538:3561:C16:A398:4FC2 (talk) 15:40, 7 October 2020 (UTC)Reply

This edit request has been answered. Set the |answered= parameter to no to reactivate your request.

 Not done: please establish a consensus for this alteration before using the {{edit semi-protected}} template. — LeoFrank  ^Talk 06:16, 8 July 2018 (UTC)Reply

[...] In chemical graph theory graphs represent both molecules and chemical reactions. A special case of the latter are synthon graphs, whose edges represent multistep synthetic reactions. Retrosynthetic analysis splits a target molecule into simpler reagents, until simple starting materials are obtained. This sort of computerized chemical reverse engineering has facilitated the syntheses of complicated molecules. [...]

Is this supposed to be a replacement for the two existing sentences about chemical graph theory? It seems overly WP:TECHNICAL, unsourced, and (in the last two sentences) a bit off-topic to me. And are reaction networks really graphs? How can they be when reactions typically have more than one input and output? —David Eppstein (talk) 00:54, 8 July 2018 (UTC)Reply

I am a bit surprised with the museum guard problem in the list of problems. If one want to see this as a graph theoretical problem, it should be rather seen as a dominating set problem. And for the later, I would include it maybe in the set cover part (which I will do now). So maybe we can remove that section? Dorbec (talk) 16:51, 11 February 2020 (UTC)Reply

I think the way the following sentence is phrased, hints that the two events are independent, but according to MacTutor and this article the second is a consequence of the first:

"his problem was first posed by Francis Guthrie in 1852 and its first written record is in a letter of De Morgan addressed to Hamilton the same year."

Perhaps the second part of the sentence could be removed or stated as a footnote? Dimitris131 (talk) 12:33, 15 January 2024 (UTC)Reply

The first definition of the edges of a graph is given as the set E which is a subset of the set of pairs of vertices such that they are in the set of vertices, V, and are not equal to one another. Shortly after, it is said that this describes an "undirected simple graph". There is then a diagram showing an "example of simple undirected graph with 3 vertices, 3 edges and 4 loops.", but the definition above of a simple undirected graph in this article does not allow for looping edges. One of these has to be wrong, but I'd have to dig into my discrete math textbook to figure out which one. Leoerickson94 (talk) 15:05, 1 December 2024 (UTC)Reply

The example is not a simple graph. It is an illustration for "one more general sense of the term allowing multiple edges", given with a different definition. —David Eppstein (talk) 18:11, 1 December 2024 (UTC)Reply

Do you think the caption should be changed then? Leoerickson94 (talk) 18:48, 1 December 2024 (UTC)Reply

Yes, fixed. Changing the image title is more difficult. —David Eppstein (talk) 21:44, 1 December 2024 (UTC)Reply

there are only subject areas of applications. SHould add actual examples of applications 99.252.125.64 (talk) 12:00, 3 November 2025 (UTC)Reply

Apparently, Graph theory mentions the definition of a graph precisely. While I am illustrating the definition of a graph briefly, does "vary" mean in this context that there are two different primary definitions of a graph, which relate to the directness? There are too many glossaries of terms, so it is preferable to merge the redirects (if we have one) to Graph (discrete mathematics) instead. Are there many definitions of a graph other than these two? Dedhert.Jr (talk) 02:35, 9 February 2026 (UTC)Reply

The first incorrect word in your comment here is "the". Why do you think mathematicians only use one formal definition for graphs? —David Eppstein (talk) 02:43, 9 February 2026 (UTC)Reply

Sorry, I meant definitions that use mathematical notations in the section "Definition". But anyway, I have rewritten it. Dedhert.Jr (talk) 03:32, 9 February 2026 (UTC)Reply