Talk:Directed graph

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computer science (Rated C-class, High-importance)
WikiProject icon 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.
C-Class article C  This article has been rated as C-Class on the project's quality scale.
 High  This article has been rated as High-importance on the project's importance scale.
 
WikiProject Mathematics (Rated C-class, Mid-importance)
WikiProject Mathematics
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.
Mathematics rating:
C Class
Mid Importance
 Field: Discrete mathematics

I feel this page does not contain enough information about the context of its subject. It is not made clear in what scientific or mathematical fields one is likely to encounter a digraph, nor is any information presented about how they are useful. 75.162.233.85 (talk) 05:56, 15 October 2008 (UTC)

The Use of "Arcs" instead of "Edges"[edit]

I don't know about anyone else, but most of the academic literature I have encountered uses the word "edge" instead of "arc" or "arrow". In the context of the english version, I think this makes even more sense because using the symmetric name for the set "E" is not likely to be confused with a word, unlike the set name "A" (which is easily confused with the word "a" when it is being used at the beginning of a sentence). This has even more value in improving clarity if the article includes the use of the upper-case letter to name the set and the lower-case to name an edge from the set of edges.

Three pieces of data?[edit]

Why is the third of these needed? Seems to me that it is superfluous; a digraph is a set of nodes, and a (multi)set of ordered pairs (arcs) node→node. I guess the nodes need to all be connected too, but that does't follow from the article, which says:

  • a set V, whose elements are called vertices or nodes,
  • a set A of ordered pairs of vertices, called arcs, directed edges, or arrows, and
  • two maps from A to V that associate to an arc its head and its tail.

JöG (talk) 12:22, 22 November 2008 (UTC)

You are right: "two maps" is not part of the mathematical definition. Although they may appear useful in some computer representations of digraphs. Twri (talk) 00:10, 25 November 2008 (UTC)

Either you have a set A of ordered pairs of vertices, or you have just a set A plus two maps 'head' and 'tail'. The two maps GIVE each arrow a direction, namely from the head to the tail. The difference is this option (a plain set plus two maps) allows multiple (or none at all) arrows between two vertices. This gives the notion of a 'directed multigraph'.145.97.197.129 (talk) 14:19, 30 July 2010 (UTC)

definition of directed graphs[edit]

Definitions of Directed graph on the Web: • A directed graph or digraph is an ordered pair with * is a set, whose elements are called vertices or nodes, * is a set of ordered pairs of vertices, called directed edges, arcs, or arrows. •

A graph in which the edges are ordered pairs, so that, if the edge (a, b) is in the graph, the edge (b, a) need not be in the graph and is ...

• • A graph with signed edges. For example, in a protein interaction network, we have excitatory interactions (which might be represented by an edge ...

• A graph with one-way edges. See also directed acyclic graph (DAG).

• (digraph):The edges are ordered pairs of V (ie the binary relation is not necessarily symmetric).

• A graph in which information flows between vertices unidirectionally.

• A graph is a directed graph if the edges have a direction, ieif they are arrows with a head and a tail.

(Jabihul Quamar Jugnu & Shailendra Pratap) —Preceding unsigned comment added by 59.180.153.186 (talk) 07:07, 27 April 2009 (UTC)

File:Directed.svg Nominated for Deletion[edit]

Image-x-generic.svg 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
What should I do?

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.

  • If the image is non-free then you may need to upload it to Wikipedia (Commons does not allow fair use)
  • If the image isn't freely licensed and there is no fair use rationale then it cannot be uploaded or used.

This notification is provided by a Bot --CommonsNotificationBot (talk) 19:45, 6 September 2011 (UTC)

Confusing sentence in definition[edit]

The last sentence of the introduction is confusing:

"On the other hand, some texts allow loops, multiple arcs, or both in a digraph."

What is a "text" in this context?

166.111.70.36 (talk) 05:55, 1 November 2012 (UTC)