Talk:Graph (mathematics)

From Wikipedia, the free encyclopedia

This article is within the scope of WikiProject Mathematics.
Mathematics grading:	A Class	High Importance	Field: Discrete mathematics
Nneeds more on motivation and applications. Tompw (talk) 17:20, 3 January 2007 (UTC)

Why are we duplicating the stuff at Graph theory? Dysprosia 23:29, 23 Sep 2003 (UTC)

Oh ok, I see now. Someone coulda told me ;) Dysprosia 23:37, 23 Sep 2003 (UTC)

Contents 1 Generalizations section 2 Merged graph (mathematics) into graph theory 3 Loops? 4 Oriented graphs 5 Variorum 6 Articles for edge and node 7 Citation Style 8 unordered pair? 9 Definition of a Graph 10 Definition of a Vertex

[edit] Generalizations section

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)

[edit] Merged graph (mathematics) into graph theory

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)

[edit] Loops?

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)

In my opinion it is easier to call a graph without loops simple graph and a graph with loops graph then the other way round. But you are free to change the definition. MathMartin 19:55, 18 Jan 2005 (UTC)

Well, I guess I mainly care about consistency between "graph" and "directed graph". It sounds like you think the definition of "graph" should be changed to allow loops. Anyone else have an opinion? dbenbenn | talk 02:47, 19 Jan 2005 (UTC)

Yes I would change the definition of graph to allow loops (my main concern is consistency too). I think it is easier having a broad definition for graphs and digraphs which includes loops and multiple edges than giving separate definitions. The broad definition can be narrowed down, if necessary, by using adjectives like simple. Another reason for the broader definition is to define a broader notion of graph homomorphism (as you have already noticed). But this is just my opinion. At the moment I am a bit busy so I am unable to work on either article. If you think you can make the definitions more consistent or clearer go ahead. MathMartin 13:47, 19 Jan 2005 (UTC)

The graph theory literature is divided on whether "digraph" allows loops. Whichever we give as the primary definition, the section on variations of definitions should mention the inconsistency. --Zero 09:21, 19 Jan 2005 (UTC)

[edit] Oriented graphs

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)

[edit] Variorum

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)

[edit] Articles for edge and node

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)

[edit] Citation Style

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)

[edit] unordered pair?

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)

An "unordered pair" is just a set with two elements. Otherwise simply called a "pair". The adjective "unordered" is sometime added to emphasize that it is not an ordered pair. Perhaps a definition of the term "unordered pair" should be added to the "ordered pair" article, which unordered pair could then link to. Paul August ☎ 17:15, 18 October 2006 (UTC)

Ok I've now done the above. Paul August ☎ 17:25, 18 October 2006 (UTC)

Thanks. Actually, my post was motivated by the question "how do we define a loop in not directed graph". Formally, the set {v,v} collapses to the singleton {v} and it's no longer "a pair". Well, I do not think it's a big problem here, but perhaps someone knows a standard solution so that we could make it clear in the article --Beaumont (@) 22:57, 4 November 2006 (UTC)

You're welcome. You are correct that with the definition given in the article, a non-directed graph is not allowed to have loops. If you want to alow a non-directed graph to have loops, then you can simple drop the word "distinct" in the definition of edge given in the the article, taking the set {a, a} to be a "pair" with non-distinct elements (See Balakrishnan, V. K.; Schaum's Outline of Graph Theory, McGraw-Hill; 1 edition (February 1, 1997). ISBN 0070054894.) Or more explicitly, you can define each edge to be either a one or two element subset of V, (See Gross, Jonathon L, and Yellen, Jay; Graph Theory and Its Applications, CRC Press (December 30, 1998). ISBN 0849339820.) Paul August ☎ 23:55, 4 November 2006 (UTC)

Yeah, there isn't a single way of doing this that makes everyone happy. The most common approach is to hide the issue in sloppy terminology. Usually confusion is avoided. One place where the distinction matters is in enumeration, where loops are usually regarded as adding 2 to the degree of a vertex but nevertheless add only 1 to the row and column sums of the adjacency matrix. McKay 03:00, 5 November 2006 (UTC)

[edit] Definition of a Graph

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)

Done. YOu could have done it yorself. `'mikka 21:32, 26 February 2007 (UTC)

[edit] Definition of a Vertex

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

You are right that the wording is sub-optimal but your suggested fix is not good. The story is, first, that V is a set (any set will do). And, second, that the elements of the set will henceforth be called "vertices". I'll try making a change. McKay 03:44, 12 March 2007 (UTC)

Thank you for your fast reply. Now I signed both messages with my brand new user account name. hmoraldo