Talk:Graph theory

Info about directed graphs, including acyclic ones, would be nice to have too.

You can tell someone who's spent far too much time studying computer science when he refers to his ancestors as the "family directed acyclic graph".

I hope at least the last few nodes of your family DAG form a proper binary tree. Brent Gulanowski

---

Maybe it's just me, but isn't it much more common to indicate graphs using the terms vertices and edges? Any formal defintion of graphs I've ever seen always uses these terms, G = (V, E). I know the other terms are also sometimes used, but I've never seen them in formal use, neither have I ever seen G = (N, E). Jeronimo

I agree. Vertices/edges is far more common than nodes/arcs. G=(V,E) is the standard notation. G=(N,E) is not only nonstandard, but it mixes the two nomenclatures. --LC 21:37 Sep 20, 2002 (UTC)

---

Maybe we need a few more pictures on this page; I moved the graphic down so that people wouldn't have to jump back and forth when considering the examples noted in the "properties" section; User:AxelBoldt moved it back so that people have a chance to see what the topic is about when they enter.

Perhaps smaller versions of the graphs shown at links like complete graph?

In addition, we could use a bit more meat here; graph isomorphisms, chromatic number, etc.; which might require a bit more overall restructuring. User:chas_zzz_brown 19:09 6 Oct 02 (UTC)

Ah, I just moved the graph down without realising there was some dispute over it. I will not move it back, though, because it seems clearly better where it is to me. It was more or less impossible to follow the examples with it stuck up at the top of the article without using a higher than normal resolution. If somebody wants to see it when they first get to the page, they can scroll down. --Camembert

I'm concerned about those people who are not mathematically mature enough and cannot follow the words without a picture. They won't scroll down, because they leave in frustration after the first paragraph. We can just show the same picture twice for now. AxelBoldt 19:35 Oct 6, 2002 (UTC)

Seems fair enough - if I'd realised there was some disagreement over where it should go, I would have done that myself. --Camembert

In addition, we could use a bit more meat here; Yup; maybe a section with elementary definitions like path, degree and cycle, and then a section with more substantive definitions like planar graph, coloring, Hamilton cycles etc and links to the respective pages. AxelBoldt 19:39 Oct 6, 2002 (UTC)

Arvindn, why did you remove the reference I put in to the Seven Bridges of Konigsberg problem? The page on Konigsberg and the page on Euler both mention this problem, which is a famous early problem in Graph Theory.

Hi. I changed the definition of a null graph to say "a graph with no edges," but it was changed back to "a graph with no edges and no vertices." I don't think this is the most common definition of a null graph; in fact this is the first place I have seen it. I checked in MathWorld, and it appears that the definition used there, is the same as the one used here. But in all the books I have read a null graph may contain vertices. Fisk 16:41 Jan 24, 2003 (UTC)

I made the change after checking the first two Google hits, Mathworld and PlanetMath. The other links however seem to agree with your definition. The references given in the MathWorld article sound convincing however. I don't know what to do. AxelBoldt 02:30 Jan 28, 2003 (UTC)

How bout Networks topic?

Done. Mikkalai

---

I typed "simple path" in the search box and it landed me here. I would fill in my own definition for a simple path if I could only figure out how to edit the simple path page. But I can't since it keeps landing me at Graph theory. Shouldn't there be a seperate page for things such as simple path? --Bryanlharris

Welcome, Bryan. Simple path. If you click there, you will see

Graph theory

(Redirected from [Simple path])

If you click on "simple path" there, you will see the page

Simple path

From Wikipedia, the free encyclopedia.

1. REDIRECT [graph theory]

And you can start editing.

BTW, if you type four tildas, ~~~~, it will give your signature with date. It helps us to tract conversations better.

Finally, in talk pages it is customary to add at the BOTTOM, not at the top of the page. I hope you will guess why.

Mikkalai 17:32, 6 May 2004 (UTC)

---

It seems that this page has been kinda stagnant for a little while. I just recently went through a grad class on the topic as well, and I'll probably fill in a few bits here and there as I have time to do so. I added a little bit on graph representations. I know that adjacency lists were covered by someone else in their own article, but I though that the adjacency matrix deserved a quick mention as well. I also added the special graph section, since there are several common graph structures which haven't been mentioned, from what I could see.

On second glance, it seems that this data may do better on the Graphs page. Don't have time to change it now, but I'll move it over soon. If anyone wants to do this for me, feel free.

--Naerbnic 07:14, 10 May 2004 (UTC)

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:23, 9 Jan 2005 (UTC)

complexity of the definitions

Currently we have definitions like this:

An undirected graph or graph G is a 3-tuple G:=(V, E, δ_E) with

• V a set of vertices,
• E a set of edges or nodes,
• <math>\delta_E : E \to {V \choose 2}<math> a function which maps each edge to its two vertices.

This is a perfectly good definition, but more complicated than necessary. Almost all (I mean > 99%) of papers in graph theory define E to be a set (or multiset) of pairs of elements of V and don't define δ_E at all. This is surely easier for a novice to understand, as well as being adequate for most professionals, so I propose we use it here. --Zero 23:17, 8 Jan 2005 (UTC)

I am not completely satisfied with my definition either, although I think the definition before was even worse. The reason for defining δ_E is to cleanly define graph homomorphism later on. If you have any ideas for simplifying the definition give it try, I will try tomorrow. MathMartin 00:13, 9 Jan 2005 (UTC)

I just noticed that the definition above is not correct. The addition "or nodes" (should be "or vertices") is presumably intended to include loops, but then δ_E should map the loop to a single vertex, not to a pair of distinct vertices which is all that (V choose 2) contains. Even if δ_E was extended to map into (V choose 2) union V, that would allow the bizarre possibility that a loop is mapped to a different vertex from the one it sits on. I think the root problem here is that we are attempting to be too formal. I would define an undirected graph like this:

An undirected graph or graph G is an ordered pair G=(V, E) where

• V is a set of vertices,
• E a set or multiset of edges, each of which is a set of 1 or 2 vertices.

Similarly "directed graph" has E a set or multiset of ordered pairs of vertices. A mixed graph has E containing both types.

A loop is just maped to the pair {v,v} where v is the vertice it sits on.--SurrealWarrior 02:53, 19 Jun 2005 (UTC)

A graph homomorphism from graph G=(V,E) to graph G'=(V',E') is a mapping from V to V' such that E is mapped to E'. (Since E is defined in terms of V rather than independently, the action on E is induced in an obvious way.) This works for undireced, directed and mixed graphs with the definitions I have suggested. The problems arise from trying to be too notational; English used carefully is just as precise. --Zero 01:27, 9 Jan 2005 (UTC)

Ok, I am finished. I moved the functions you did not like and the graph homomorphism section to graph homomorphism. I think this is a good solution. MathMartin 19:21, 9 Jan 2005 (UTC)

Rewording networks

I notice at the moment that networks (note no network at time of writing!) get a mention at the beginning of the article. However, I don't think the explanation is really right -- for a start, networks don't necessarily have weighted edges. I think it is probably better put as it is in network theory. There network theory (I prefer actually network analysis) is the applied mathematics of graph theory. How does a quick rewrite of the short network paragraph sound? -- as follows:

When graph theory is applied to real systems, it is called network analysis. A network can be used to model and analyze traffic networks, relations between people (social networks), or computer networks (like the internet).

--stochata 21:24, 30 Jan 2005 (UTC)

If I remember correctly the opening paragraph was rewritten by me some time ago. A network in mathematics is a graph with weighted edges (as far as I know) and the link is to network (mathematics) and not to network. This is a mathematics article so I think we should use the precise and common terminology (as used in mathematics). So I do not really understand what you mean be not really right, can you provide any links where a network (in mathematics) is defined without weighted edges ? Having said this the article definitely needs some more work and if you want to expand the introduction or add applications to the main article go ahead. MathMartin 22:05, 30 Jan 2005 (UTC)

You've actually helped me to work out what I meant by 'not right': as it is worded, the listed network topics (transport and the internet) are used in the sense of applied graph theory, whereas the sentence that introduces the network is the technical graph theoretic usage -- I'm from the applied end, so I'm not well acquainted with the terminology -- although it doesn't appear to be universally fixed within mathematics -- here's a quick googled link: [1] (http://web.hamline.edu/~lcopes/SciMathMN/concepts/ctypes.html) More importantly, though, within any applied area, even the more technical such as scale-free networks or small-world networks (unwritten on Wikipedia as yet, see Watts & Strogatz, Nature 393, 440 - 442 (04 Jun 1998) if you have access or small-world phenomenon), 'network' is used to mean simple a graph. Therefore it strikes me some clarification is necessary. As you say, this is a mathematics article, so yes, let's keep a technical definition of a weighted digraph, but also then suggest applied is looser with its definition? --stochata 01:58, 31 Jan 2005 (UTC)

Stochata is right! --Zero 08:42, 31 Jan 2005 (UTC)

I admit my focus is on mathematics and I do not work in applied graph theory. So if you think the sentence is unclear (and Zero does too), then be bold and go ahead and edit/clarify the article. By expanding the material the article can only become clearer. And I think it is a good idea to mention in the introduction that some people (for whatever strange reasons) refer to a simple graph as a network.MathMartin 11:20, 31 Jan 2005 (UTC)

Done, although it needs tidying up: now has a digraph twice --stochata 21:51, 1 Feb 2005 (UTC)

If you have a digraph with no loops( a group of vertices a[n] with a arrow going from a[j] to a[j+1] and a arrow going from a[n] to a[1]) it proveably has a vertice that no arrows point to is the problem of finding some or all of these vertices NP-Complete?--SurrealWarrior 02:49, 19 Jun 2005 (UTC)