This
level-4 vital article is rated B-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||||||||||||||||
|
Daily pageviews of this article
A graph should have been displayed here but
graphs are temporarily disabled. Until they are enabled again, visit the interactive graph at
pageviews.wmcloud.org |
The previous text was this: Every graph gives rise to a matroid, but in general the graph cannot be recovered from its matroid, so matroids are not truly generalizations of graphs. Of course not all matroids correspond to graphs - that's the whole point of a generalization. The same applies to hypergraphs and any other generalization. I removed the remark. Wandrer2 09:28, 26 January 2007 (UTC)
I merged the two articles. See Wikipedia_talk:WikiProject_Mathematics#Graph_.28mathematics.29_vs_Graph_theory for a discussion. MathMartin 16:22, 9 Jan 2005 (UTC) after that he did another theory —Preceding unsigned comment added by 217.38.127.254 ( talk) 17:44, 4 September 2007 (UTC)
The current definition of "directed graph" allows loops. (And it did before I edited it!) I suggest that by default, a directed graph should not allow loops; that possibility should only be mentioned in the alternate definitions section. I'll make the change eventually unless there are objections. Dbenbenn 14:48, 13 Jan 2005 (UTC)
Something the article should make more clear is which of the two intuitive concepts of loop it is referring to. It's one thing to have a line coming out from a node and back around directly in to the same node again. It's another to connect A-B-C-A.. Cesiumfrog ( talk) 05:49, 1 October 2010 (UTC)
I am surprised why a directed graph should _not_ allow self loops. While literature may offer mutually exclusive definitions, at least the articles on Wikipedia should not contradict one another. Compare /info/en/?search=Loop_(graph_theory)#Degree: "For a directed graph, a loop adds one to the in degree and one to the out degree." – This directly contradicts the definition on this page (x/=y). 2601:647:5C00:4460:0:0:0:AA8E ( talk) 17:31, 4 October 2021 (UTC)
The current definition of degree says that a loop is counted twice. A bit later in the page it says the maximum degree for a graph of n vertices (with loops) is n. I believe this should be n+1. — Preceding unsigned comment added by 2601:1C2:1B7F:9FA0:441D:A012:C730:FECF ( talk) 03:44, 29 November 2022 (UTC)
I question this: "A more fundamental difference is that, in a directed graph (or multigraph), the directions are fixed, but in an oriented graph (or multigraph), only the underlying graph is fixed, while the orientation may vary." I don't know what "may vary" means. It seems to me that an oriented graph consists of a pair (undirected graph, orientation). A given undirected graph can be oriented in different ways but these lead to different oriented graphs, not to the same oriented graph where the orientation has "varied". -- Zero 00:25, 17 August 2005 (UTC)
JA: I will be making some comments on the variations in definitions and terminology, but just to keep my headings together I will locate everything on the Graph theory talk page. Jon Awbrey 19:10, 18 March 2006 (UTC)
The articles edge (graph theory), node (graph theory) and node (computer science) are essentially impossible to write since you cannot explain edge without explaining node and graph (graph theory) and vice-versa. Therefore, I made these articles redirect to graph (graph theory). ylloh 01:01, 15 April 2006 (UTC)
JA: My recommendation is that we continue to use the citation styles that are standard in math journals, and avoid the use of footnotes. These things make the line spacing on the face article very jagged, make the text in the edit window very hard to proofread, they become almost impossible to maintain when there gets to be more than a few of them, they lead to information loss when the source data is too complex for the Ref format, and all in all they make the article look very amateurish and antiquated, as footnotes for citations were already being phased out in the late 60's, just from what I recall. Jon Awbrey 13:30, 27 June 2006 (UTC)
Could one explain what means the unordered pair used in the definition of the graph? It seems that there is no such an entry in wikipedia (and the Axiom of the unordered pair, is not what we want here, is it?). -- Beaumont (@) 16:04, 18 October 2006 (UTC)
I think the 3rd bullet point of the definition of a graph should be moved into the paragraph below, it's not part of the definition of a graph, it just defines some extra terminology. -- Llygadebrill 21:11, 26 February 2007 (UTC)
I find strange that a formal definition might depend on sets of some kind of object that is never defined. What are vertices? I guess some description on what kind of object is required to be a vertex or node would add to the article. But as I understand, there is no requirement for vertices objects (they need not properties other than being comparable for equality, which is always the case for math objects). So the only modification I suppose necessary is to tell this in the text: "V is a set of mathematical objects of any kind; they are called vertices (or nodes)". Am I wrong? hmoraldo
My understanding of quivers is that a quiver _is_ just a directed graph, and that a representation of a quiver attaches a vector space to each vertex and linear mappings to each edge. Could someone please correct me if I am wrong or otherwise comment?
Thanks SophomoricPedant 04:19, 3 June 2007 (UTC)
Since no one responded, I will adjust the wording to reflect the above distinction SophomoricPedant 04:19, 3 June 2007 (UTC)
Our team has created a very effective graph and network optimization tool: an open source library written in C++ language. We think that our project is matured enough to be mentioned here in external links section. Or we could create a brand new Wikipedia article for it that could be cited from here. Everybody who gets familiar with graphs wants to use them. If our library was mentioned here, the next step towards using graphs would be presented here. The name of our open source library is LEMON. Here you can get familiar with it.
Phegyi81 14:15, 14 June 2007 (UTC)
You dit it real nice.
?? ??
Since no one responded, I refer our library in External links section.
Phegyi81 11:14, 2 July 2007 (UTC)
Is seems like someone has written the definition of a linear graph based on the wrong definition of a graph. Can anyone verify this? If no one says otherwise, or beats me to it, I'll rewrite the definition later. BTW, would a linear graph be, by definition, connected? MagiMaster ( talk) 22:13, 11 February 2008 (UTC)
I think graphs im Maths are too complicated and you never use them in every day life (jobs) —Preceding unsigned comment added by 88.108.216.138 ( talk) 17:23, 27 February 2008 (UTC)
Hamiltonian and Euler graphs are more important than others. Needs grouping graphs according to their applications- for a non-mathematician.
The articles Graph (mathematics) and Graph Theory overlap several things. Why did someone write like this? I recommend reworking both of them and combinig as a single article. In summary, we are trying to dump duplicate materials at different places. They are not well organized.
-- Tangi-tamma ( talk) 20:32, 6 April 2008 (UTC)
As a mathematician working mostly in geometry and topology, I always find the "definitions" section in graph theory textbooks rather annoying since they often avoid defining the object at the proper level of generality. The same is true here which should make anyone who is reading this article carefully fairly confused. The main definition of a graph given in the article is already that of a simple graph. If edges are defined as two-element subsets of the vertex set, then you automatically exclude loop-edges and multiple edges. So what does it mean then to say that a "A simple graph is an undirected graph that has no self-loops and no more than one edge between any two different vertices"? Sounds like a tautology to me. In fact what is a self-loop in the sense of the main graph definition anyway?
The actual general definition of a graph (where both loop-edges and multiple edges are allowed; if I remember correctly, this is called a pseudo-graph) is something like this: a triple G=(V,E,j) where j is a function that assigns to every element e of E a subset of V consisting of one or two elements.
I understand that this is a Wikipedia article, not a mathematical textbook, but shouldn't the formal general definition of a pseudo-graph be contained somewhere in the article? Nsk92 ( talk) 04:11, 21 May 2008 (UTC)
As a computer science student heavily working on computer networks, we are constantly talking about " Graph metrics" or " Network metrics". Is there a similar concept in the article? Should it be included? -- 80.136.117.67 ( talk) 13:39, 5 October 2008 (UTC)
Is the concept of a connected graph too simple to be mentioned? Either the "Graph Types" or the "Properties of Graphs" section should mention "Connected Graph" or "a graph is called connected", if even a "finite graph" is explained. -- 80.136.83.51 ( talk) 12:29, 10 October 2008 (UTC)
Fellows, when defining connected graphs, woudn`t be useful to define what is a "path" (in opposition to "edge")? I mean, a path of length 1 is merely an edge - and that worth mentioning to clarify someone who is unfamiliar with this theme hferro —Preceding undated comment added 01:26, 4 October 2016 (UTC)
Please see Category talk:Graphs#Subcategory suggestion. Twri ( talk) 17:21, 10 October 2008 (UTC)
Under important graphs, should we add the n-cube? i.e. the graph of joining the vertices of a hypercube that differ by 1 bit when the vertices are in a bit stream? AndrewHarvey4 ( talk) 06:55, 14 October 2008 (UTC)
It would be easy to start a war over ownership of the term graph, but I'll refrain—for now, anyway :-). Nsk92 asserted above that the definition was too narrow, and Gandalf61 agreed and changed it. Now, I see things differently. For me, and for lots of other practicing mathematicians, graph implies simple, and if you want your edges to be multisets, you're welcome to a different term for this different beast, namely multigraph. Edges of cardinality not equal to 2 are perfectly respectable entities and are emminently worth studying, they merely merit (to our way of thinking) different terminology.
Since tons of mathematicians would be in the same pew with me in this religious debate, I've adjusted the blurb acknowledging our usage. In particular, where it used to attribute the usage to "some authors," it now refers to "many authors."
Let the food fight begin!— PaulTanenbaum ( talk) 21:28, 23 October 2008 (UTC)
Would it make sense to have a minimal discussion of graph invariants, such as diameter, valence, girth, perhaps eigenvalue, etc? Katzmik ( talk) 10:11, 24 October 2008 (UTC)
I recently made this with an edit summary of: (See wp:manual of style#Italics "Italics are used sparingly to emphasize words in sentences (bolding is normally not used at all for this purpose).") About an hour later, User:Gandalf61 reverted my edit to this version with an edit summary of: (rv - bold text highlights defined terms, which is necessary in this overview article). Is this true? Is this the article where bolding can be used 74 times? (Yes, I did count them.) Any thoughts? 98.166.139.216 ( talk) 19:50, 28 November 2008 (UTC)
I'd sure like to know why we have graphs. Just starting them in discrete math class, I find them fascinating, and I can't help but imagine they have countless real world applications, but there's no discussion of this on the page...could someone help? —Preceding unsigned comment added by 74.10.227.130 ( talk) 20:49, 31 March 2009 (UTC)
An image used in this article,
File:Directed.svg, has been nominated for deletion at
Wikimedia Commons in the following category: Deletion requests September 2011
Don't panic; a discussion will now take place over on Commons about whether to remove the file. This gives you an opportunity to contest the deletion, although please review Commons guidelines before doing so.
This notification is provided by a Bot -- CommonsNotificationBot ( talk) 19:45, 6 September 2011 (UTC) |
Missing: "Two graphs are said to be equal iff ...". Should follow each definition.
Also a word on isomorphy would be nice. — Preceding unsigned comment added by Modelpractice ( talk • contribs) 22:47, 11 August 2012 (UTC)
Why is there figure of something that is *distinctly not a graph*, but a pseudograph, next to the definition? Would it not be much better to have a *graph* illustrating, you know, the definition of a *graph*?— Preceding unsigned comment added by 130.225.212.4 ( talk)
Please explain in the article why the word "edge" is used. If an "edge" is just a line, why isn't it called a line? If there is some subtle distinction that makes an "edge" not a line, it might be helpful to explain that. Alternately, if the meaning is identical but the term lives on for merely historical reasons, that would also be helpful to know. 129.219.155.89 ( talk) 20:05, 2 April 2014 (UTC)
The result of the move request was: no consensus unfortunately. While there is general agreement that the current title is problematic, there is clearly no consensus as to how exactly this article should be renamed. Seeing as the discussion here has died, I'm closing this discussion because I think the chances of it reaching a consensus for any of the proposed variants to be almost nonexistent. No prejudice against any new RMs if anyone can think up a title they think will gain a consensus. Jenks24 ( talk) 09:46, 25 January 2016 (UTC)
Graph (mathematics) →
Graph (discrete mathematics) – Users often incorrectly point to
Graph (mathematics) when they actually mean
Graph of a function.
Graph (mathematics) should be redirected to
Graph (disambiguation)#Mathematics.
Petr Matas 11:48, 5 January 2016 (UTC)--Relisted.
Cúchullain
t/
c 14:54, 13 January 2016 (UTC)
Indeed, we have several possible moves, each being better than nothing; however, we do nothing, since we do not know which possibility is optimal; just Buridan's ass. Could we choose one possibility randomly? Boris Tsirelson ( talk) 12:11, 25 January 2016 (UTC)
The title ambiguity problem has been solved by moving the page to Graph (discrete mathematics), but more discussion is needed before choosing the final title. Please put each proposed new title into a separate subsection to allow clean argumentation and voting. Please review the arguments (see also the previous discussion) before voting. Petr Matas 09:12, 30 January 2016 (UTC)
Pinging Dicklyon, kennethaw88, Joel B. Lewis, D.Lazard, Slawekb, Tsirel, Mark L MacDonald, Dmcq, David Eppstein, Wcherowi, The Earwig. Petr Matas 09:13, 30 January 2016 (UTC)
Narrow the scope of this article to complement the articles Directed graph and Mixed graph. Move the discussion of graph types to Graph theory.
I've asked Google image for "graph connections" and feel satisfied with the result. Boris Tsirelson ( talk) 15:22, 30 January 2016 (UTC)
There is an inane edit war going on about the definitions of path graph and cycle graph given in this article. One editor prefers a definition in terms of connectedness and degree sequence. In my opinion, this definition actively obscures the structure of the graph (and this is reinforced by the fact that the definition added was wrong repeatedly). Instead, I prefer the previous definition, which explicitly gives the structure in vertices and edges. I would like to invite other editors to give their opinions. (Of course, both definitions offered are equivalent: they define the finite paths (or cycles). The question is, which one is better for a broad article of this sort?) I am also open to constructive suggestions for improving the wording of the structural definition. -- JBL ( talk) 14:22, 22 January 2016 (UTC)
There is a redirect from nonadjacent to Graph but the word does not occur in the article. Just mentioning. — Is there no bot for this? IXhdBAH ( talk) 13:43, 6 June 2016 (UTC)
The comment(s) below were originally left at Talk:Graph (discrete mathematics)/Comments, and are posted here for posterity. Following several discussions in past years, these subpages are now deprecated. The comments may be irrelevant or outdated; if so, please feel free to remove this section.
needs more on motivation and applications. Tompw ( talk) 17:20, 3 January 2007 (UTC) Agreed. And also an extra image or two (an image is used twice at the moment) and a longer lead. Geometry guy 16:09, 9 June 2007 (UTC) |
Substituted at 18:19, 17 July 2016 (UTC)
@ David Eppstein and Maggyero: In addition to the widespread introduction of the nonstandard (in the context of graph theory) term "arrows" for directed edges, Maggyero's edits also widely introduced the word "link". IANAGT, but this also seems like a nonstandard usage to me. (It was mentioned in the article previously, but not so heavily used.)
Another thing I noticed is the following addition (my bold): "Typically, a graph is depicted in diagrammatic form as a set of dots or circles for the vertices, joined by lines or curves for the edges." I would be more inclined to challenge this/ask for a reliable source if (1) there were any discussion of this point in the body of the article, rather than in the lead, and (2) if that discussion had any reliable sourcing. Presumably graph theorists comment on this in their textbooks sometimes? Maybe it (the diagrammatic/pictorial representation of graphs) even deserves a small section in this article, if it can be supported. -- JBL ( talk) 12:19, 16 April 2019 (UTC)
Discussion moved from User talk:D.Lazard (begin)
Your last edit Applying MOS:LISTBULLET ( https://en.wikipedia.org/?title=Graph_theory&oldid=896700053) makes the definitions harder to read, as they do not stand out. If the definitions were less subtle it would be fine, but here this is not the case (simple graphs, multigraphs, simple graphs permitting loops, multiple graphs permitting loops, and likewise for directed graphs). So I think we should keep the bulleted version for the reader.
End of the moved discussion
User:JayBeeEll: I would like to discuss this. Thank you for giving the reason; without that, it's impossible to know what to think (that's why I reverted your first reversion and probably why you made that first reversion). You wrote, '"graph" is a countable noun, the plural construction is much more natural (and certainly grammatically correct)'. I disagree with the conclusion. The plural should appear in "types", not (necessarily) "graph". It is good standard English to not pluralize the object of the preposition in this context. The issue is not that "graph" is "countable" or that "graphs" is ungrammatical; it is that the plural belongs on "type" and is unnecessary on "graph", and it is good style not to pluralize twice. Zaslav ( talk) 22:17, 4 November 2023 (UTC)
This
level-4 vital article is rated B-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||||||||||||||||
|
Daily pageviews of this article
A graph should have been displayed here but
graphs are temporarily disabled. Until they are enabled again, visit the interactive graph at
pageviews.wmcloud.org |
The previous text was this: Every graph gives rise to a matroid, but in general the graph cannot be recovered from its matroid, so matroids are not truly generalizations of graphs. Of course not all matroids correspond to graphs - that's the whole point of a generalization. The same applies to hypergraphs and any other generalization. I removed the remark. Wandrer2 09:28, 26 January 2007 (UTC)
I merged the two articles. See Wikipedia_talk:WikiProject_Mathematics#Graph_.28mathematics.29_vs_Graph_theory for a discussion. MathMartin 16:22, 9 Jan 2005 (UTC) after that he did another theory —Preceding unsigned comment added by 217.38.127.254 ( talk) 17:44, 4 September 2007 (UTC)
The current definition of "directed graph" allows loops. (And it did before I edited it!) I suggest that by default, a directed graph should not allow loops; that possibility should only be mentioned in the alternate definitions section. I'll make the change eventually unless there are objections. Dbenbenn 14:48, 13 Jan 2005 (UTC)
Something the article should make more clear is which of the two intuitive concepts of loop it is referring to. It's one thing to have a line coming out from a node and back around directly in to the same node again. It's another to connect A-B-C-A.. Cesiumfrog ( talk) 05:49, 1 October 2010 (UTC)
I am surprised why a directed graph should _not_ allow self loops. While literature may offer mutually exclusive definitions, at least the articles on Wikipedia should not contradict one another. Compare /info/en/?search=Loop_(graph_theory)#Degree: "For a directed graph, a loop adds one to the in degree and one to the out degree." – This directly contradicts the definition on this page (x/=y). 2601:647:5C00:4460:0:0:0:AA8E ( talk) 17:31, 4 October 2021 (UTC)
The current definition of degree says that a loop is counted twice. A bit later in the page it says the maximum degree for a graph of n vertices (with loops) is n. I believe this should be n+1. — Preceding unsigned comment added by 2601:1C2:1B7F:9FA0:441D:A012:C730:FECF ( talk) 03:44, 29 November 2022 (UTC)
I question this: "A more fundamental difference is that, in a directed graph (or multigraph), the directions are fixed, but in an oriented graph (or multigraph), only the underlying graph is fixed, while the orientation may vary." I don't know what "may vary" means. It seems to me that an oriented graph consists of a pair (undirected graph, orientation). A given undirected graph can be oriented in different ways but these lead to different oriented graphs, not to the same oriented graph where the orientation has "varied". -- Zero 00:25, 17 August 2005 (UTC)
JA: I will be making some comments on the variations in definitions and terminology, but just to keep my headings together I will locate everything on the Graph theory talk page. Jon Awbrey 19:10, 18 March 2006 (UTC)
The articles edge (graph theory), node (graph theory) and node (computer science) are essentially impossible to write since you cannot explain edge without explaining node and graph (graph theory) and vice-versa. Therefore, I made these articles redirect to graph (graph theory). ylloh 01:01, 15 April 2006 (UTC)
JA: My recommendation is that we continue to use the citation styles that are standard in math journals, and avoid the use of footnotes. These things make the line spacing on the face article very jagged, make the text in the edit window very hard to proofread, they become almost impossible to maintain when there gets to be more than a few of them, they lead to information loss when the source data is too complex for the Ref format, and all in all they make the article look very amateurish and antiquated, as footnotes for citations were already being phased out in the late 60's, just from what I recall. Jon Awbrey 13:30, 27 June 2006 (UTC)
Could one explain what means the unordered pair used in the definition of the graph? It seems that there is no such an entry in wikipedia (and the Axiom of the unordered pair, is not what we want here, is it?). -- Beaumont (@) 16:04, 18 October 2006 (UTC)
I think the 3rd bullet point of the definition of a graph should be moved into the paragraph below, it's not part of the definition of a graph, it just defines some extra terminology. -- Llygadebrill 21:11, 26 February 2007 (UTC)
I find strange that a formal definition might depend on sets of some kind of object that is never defined. What are vertices? I guess some description on what kind of object is required to be a vertex or node would add to the article. But as I understand, there is no requirement for vertices objects (they need not properties other than being comparable for equality, which is always the case for math objects). So the only modification I suppose necessary is to tell this in the text: "V is a set of mathematical objects of any kind; they are called vertices (or nodes)". Am I wrong? hmoraldo
My understanding of quivers is that a quiver _is_ just a directed graph, and that a representation of a quiver attaches a vector space to each vertex and linear mappings to each edge. Could someone please correct me if I am wrong or otherwise comment?
Thanks SophomoricPedant 04:19, 3 June 2007 (UTC)
Since no one responded, I will adjust the wording to reflect the above distinction SophomoricPedant 04:19, 3 June 2007 (UTC)
Our team has created a very effective graph and network optimization tool: an open source library written in C++ language. We think that our project is matured enough to be mentioned here in external links section. Or we could create a brand new Wikipedia article for it that could be cited from here. Everybody who gets familiar with graphs wants to use them. If our library was mentioned here, the next step towards using graphs would be presented here. The name of our open source library is LEMON. Here you can get familiar with it.
Phegyi81 14:15, 14 June 2007 (UTC)
You dit it real nice.
?? ??
Since no one responded, I refer our library in External links section.
Phegyi81 11:14, 2 July 2007 (UTC)
Is seems like someone has written the definition of a linear graph based on the wrong definition of a graph. Can anyone verify this? If no one says otherwise, or beats me to it, I'll rewrite the definition later. BTW, would a linear graph be, by definition, connected? MagiMaster ( talk) 22:13, 11 February 2008 (UTC)
I think graphs im Maths are too complicated and you never use them in every day life (jobs) —Preceding unsigned comment added by 88.108.216.138 ( talk) 17:23, 27 February 2008 (UTC)
Hamiltonian and Euler graphs are more important than others. Needs grouping graphs according to their applications- for a non-mathematician.
The articles Graph (mathematics) and Graph Theory overlap several things. Why did someone write like this? I recommend reworking both of them and combinig as a single article. In summary, we are trying to dump duplicate materials at different places. They are not well organized.
-- Tangi-tamma ( talk) 20:32, 6 April 2008 (UTC)
As a mathematician working mostly in geometry and topology, I always find the "definitions" section in graph theory textbooks rather annoying since they often avoid defining the object at the proper level of generality. The same is true here which should make anyone who is reading this article carefully fairly confused. The main definition of a graph given in the article is already that of a simple graph. If edges are defined as two-element subsets of the vertex set, then you automatically exclude loop-edges and multiple edges. So what does it mean then to say that a "A simple graph is an undirected graph that has no self-loops and no more than one edge between any two different vertices"? Sounds like a tautology to me. In fact what is a self-loop in the sense of the main graph definition anyway?
The actual general definition of a graph (where both loop-edges and multiple edges are allowed; if I remember correctly, this is called a pseudo-graph) is something like this: a triple G=(V,E,j) where j is a function that assigns to every element e of E a subset of V consisting of one or two elements.
I understand that this is a Wikipedia article, not a mathematical textbook, but shouldn't the formal general definition of a pseudo-graph be contained somewhere in the article? Nsk92 ( talk) 04:11, 21 May 2008 (UTC)
As a computer science student heavily working on computer networks, we are constantly talking about " Graph metrics" or " Network metrics". Is there a similar concept in the article? Should it be included? -- 80.136.117.67 ( talk) 13:39, 5 October 2008 (UTC)
Is the concept of a connected graph too simple to be mentioned? Either the "Graph Types" or the "Properties of Graphs" section should mention "Connected Graph" or "a graph is called connected", if even a "finite graph" is explained. -- 80.136.83.51 ( talk) 12:29, 10 October 2008 (UTC)
Fellows, when defining connected graphs, woudn`t be useful to define what is a "path" (in opposition to "edge")? I mean, a path of length 1 is merely an edge - and that worth mentioning to clarify someone who is unfamiliar with this theme hferro —Preceding undated comment added 01:26, 4 October 2016 (UTC)
Please see Category talk:Graphs#Subcategory suggestion. Twri ( talk) 17:21, 10 October 2008 (UTC)
Under important graphs, should we add the n-cube? i.e. the graph of joining the vertices of a hypercube that differ by 1 bit when the vertices are in a bit stream? AndrewHarvey4 ( talk) 06:55, 14 October 2008 (UTC)
It would be easy to start a war over ownership of the term graph, but I'll refrain—for now, anyway :-). Nsk92 asserted above that the definition was too narrow, and Gandalf61 agreed and changed it. Now, I see things differently. For me, and for lots of other practicing mathematicians, graph implies simple, and if you want your edges to be multisets, you're welcome to a different term for this different beast, namely multigraph. Edges of cardinality not equal to 2 are perfectly respectable entities and are emminently worth studying, they merely merit (to our way of thinking) different terminology.
Since tons of mathematicians would be in the same pew with me in this religious debate, I've adjusted the blurb acknowledging our usage. In particular, where it used to attribute the usage to "some authors," it now refers to "many authors."
Let the food fight begin!— PaulTanenbaum ( talk) 21:28, 23 October 2008 (UTC)
Would it make sense to have a minimal discussion of graph invariants, such as diameter, valence, girth, perhaps eigenvalue, etc? Katzmik ( talk) 10:11, 24 October 2008 (UTC)
I recently made this with an edit summary of: (See wp:manual of style#Italics "Italics are used sparingly to emphasize words in sentences (bolding is normally not used at all for this purpose).") About an hour later, User:Gandalf61 reverted my edit to this version with an edit summary of: (rv - bold text highlights defined terms, which is necessary in this overview article). Is this true? Is this the article where bolding can be used 74 times? (Yes, I did count them.) Any thoughts? 98.166.139.216 ( talk) 19:50, 28 November 2008 (UTC)
I'd sure like to know why we have graphs. Just starting them in discrete math class, I find them fascinating, and I can't help but imagine they have countless real world applications, but there's no discussion of this on the page...could someone help? —Preceding unsigned comment added by 74.10.227.130 ( talk) 20:49, 31 March 2009 (UTC)
An image used in this article,
File:Directed.svg, has been nominated for deletion at
Wikimedia Commons in the following category: Deletion requests September 2011
Don't panic; a discussion will now take place over on Commons about whether to remove the file. This gives you an opportunity to contest the deletion, although please review Commons guidelines before doing so.
This notification is provided by a Bot -- CommonsNotificationBot ( talk) 19:45, 6 September 2011 (UTC) |
Missing: "Two graphs are said to be equal iff ...". Should follow each definition.
Also a word on isomorphy would be nice. — Preceding unsigned comment added by Modelpractice ( talk • contribs) 22:47, 11 August 2012 (UTC)
Why is there figure of something that is *distinctly not a graph*, but a pseudograph, next to the definition? Would it not be much better to have a *graph* illustrating, you know, the definition of a *graph*?— Preceding unsigned comment added by 130.225.212.4 ( talk)
Please explain in the article why the word "edge" is used. If an "edge" is just a line, why isn't it called a line? If there is some subtle distinction that makes an "edge" not a line, it might be helpful to explain that. Alternately, if the meaning is identical but the term lives on for merely historical reasons, that would also be helpful to know. 129.219.155.89 ( talk) 20:05, 2 April 2014 (UTC)
The result of the move request was: no consensus unfortunately. While there is general agreement that the current title is problematic, there is clearly no consensus as to how exactly this article should be renamed. Seeing as the discussion here has died, I'm closing this discussion because I think the chances of it reaching a consensus for any of the proposed variants to be almost nonexistent. No prejudice against any new RMs if anyone can think up a title they think will gain a consensus. Jenks24 ( talk) 09:46, 25 January 2016 (UTC)
Graph (mathematics) →
Graph (discrete mathematics) – Users often incorrectly point to
Graph (mathematics) when they actually mean
Graph of a function.
Graph (mathematics) should be redirected to
Graph (disambiguation)#Mathematics.
Petr Matas 11:48, 5 January 2016 (UTC)--Relisted.
Cúchullain
t/
c 14:54, 13 January 2016 (UTC)
Indeed, we have several possible moves, each being better than nothing; however, we do nothing, since we do not know which possibility is optimal; just Buridan's ass. Could we choose one possibility randomly? Boris Tsirelson ( talk) 12:11, 25 January 2016 (UTC)
The title ambiguity problem has been solved by moving the page to Graph (discrete mathematics), but more discussion is needed before choosing the final title. Please put each proposed new title into a separate subsection to allow clean argumentation and voting. Please review the arguments (see also the previous discussion) before voting. Petr Matas 09:12, 30 January 2016 (UTC)
Pinging Dicklyon, kennethaw88, Joel B. Lewis, D.Lazard, Slawekb, Tsirel, Mark L MacDonald, Dmcq, David Eppstein, Wcherowi, The Earwig. Petr Matas 09:13, 30 January 2016 (UTC)
Narrow the scope of this article to complement the articles Directed graph and Mixed graph. Move the discussion of graph types to Graph theory.
I've asked Google image for "graph connections" and feel satisfied with the result. Boris Tsirelson ( talk) 15:22, 30 January 2016 (UTC)
There is an inane edit war going on about the definitions of path graph and cycle graph given in this article. One editor prefers a definition in terms of connectedness and degree sequence. In my opinion, this definition actively obscures the structure of the graph (and this is reinforced by the fact that the definition added was wrong repeatedly). Instead, I prefer the previous definition, which explicitly gives the structure in vertices and edges. I would like to invite other editors to give their opinions. (Of course, both definitions offered are equivalent: they define the finite paths (or cycles). The question is, which one is better for a broad article of this sort?) I am also open to constructive suggestions for improving the wording of the structural definition. -- JBL ( talk) 14:22, 22 January 2016 (UTC)
There is a redirect from nonadjacent to Graph but the word does not occur in the article. Just mentioning. — Is there no bot for this? IXhdBAH ( talk) 13:43, 6 June 2016 (UTC)
The comment(s) below were originally left at Talk:Graph (discrete mathematics)/Comments, and are posted here for posterity. Following several discussions in past years, these subpages are now deprecated. The comments may be irrelevant or outdated; if so, please feel free to remove this section.
needs more on motivation and applications. Tompw ( talk) 17:20, 3 January 2007 (UTC) Agreed. And also an extra image or two (an image is used twice at the moment) and a longer lead. Geometry guy 16:09, 9 June 2007 (UTC) |
Substituted at 18:19, 17 July 2016 (UTC)
@ David Eppstein and Maggyero: In addition to the widespread introduction of the nonstandard (in the context of graph theory) term "arrows" for directed edges, Maggyero's edits also widely introduced the word "link". IANAGT, but this also seems like a nonstandard usage to me. (It was mentioned in the article previously, but not so heavily used.)
Another thing I noticed is the following addition (my bold): "Typically, a graph is depicted in diagrammatic form as a set of dots or circles for the vertices, joined by lines or curves for the edges." I would be more inclined to challenge this/ask for a reliable source if (1) there were any discussion of this point in the body of the article, rather than in the lead, and (2) if that discussion had any reliable sourcing. Presumably graph theorists comment on this in their textbooks sometimes? Maybe it (the diagrammatic/pictorial representation of graphs) even deserves a small section in this article, if it can be supported. -- JBL ( talk) 12:19, 16 April 2019 (UTC)
Discussion moved from User talk:D.Lazard (begin)
Your last edit Applying MOS:LISTBULLET ( https://en.wikipedia.org/?title=Graph_theory&oldid=896700053) makes the definitions harder to read, as they do not stand out. If the definitions were less subtle it would be fine, but here this is not the case (simple graphs, multigraphs, simple graphs permitting loops, multiple graphs permitting loops, and likewise for directed graphs). So I think we should keep the bulleted version for the reader.
End of the moved discussion
User:JayBeeEll: I would like to discuss this. Thank you for giving the reason; without that, it's impossible to know what to think (that's why I reverted your first reversion and probably why you made that first reversion). You wrote, '"graph" is a countable noun, the plural construction is much more natural (and certainly grammatically correct)'. I disagree with the conclusion. The plural should appear in "types", not (necessarily) "graph". It is good standard English to not pluralize the object of the preposition in this context. The issue is not that "graph" is "countable" or that "graphs" is ungrammatical; it is that the plural belongs on "type" and is unnecessary on "graph", and it is good style not to pluralize twice. Zaslav ( talk) 22:17, 4 November 2023 (UTC)