Digraph

Directed graph in mathematics and computer science

About WikiMD: The article, Digraph, is part of WikiMD.
WikiMD is a free medical encyclopedia and wellnesspedia moderated by medical professionals.

A digraph or directed graph is a type of graph in which the edges have a direction. This means that each edge is an ordered pair of vertices, representing a one-way relationship between the vertices. Digraphs are used extensively in computer science, mathematics, and related fields to model relationships and processes.

Definition

A digraph is defined as a pair \( G = (V, E) \), where:

• \( V \) is a set of vertices (also called nodes or points).
• \( E \) is a set of ordered pairs of vertices, called directed edges (or arcs).

In a digraph, an edge \( (u, v) \) is directed from vertex \( u \) to vertex \( v \). This directionality distinguishes digraphs from undirected graphs, where edges have no orientation.

Types of Digraphs

There are several types of digraphs, including:

• Simple digraphs: Digraphs with no multiple edges or loops.
• Multidigraphs: Digraphs that allow multiple edges between the same pair of vertices.
• Weighted digraphs: Digraphs where edges have associated weights or costs.

Properties

Digraphs have several important properties:

• In-degree and out-degree: The in-degree of a vertex is the number of edges directed towards it, while the out-degree is the number of edges directed away from it.
• Paths and cycles: A path in a digraph is a sequence of vertices connected by directed edges. A cycle is a path that starts and ends at the same vertex.
• Strong connectivity: A digraph is strongly connected if there is a directed path from any vertex to every other vertex.

Applications

Digraphs are used in various applications, including:

• Computer networks: Modeling the flow of data between devices.
• Social networks: Representing relationships and interactions between individuals.
• Project management: Using PERT and CPM charts to model task dependencies.
• Linguistics: Representing syntactic structures in natural language processing.

Related Concepts

• Graph theory
• Adjacency matrix
• Adjacency list
• Topological sorting
• Directed acyclic graph

See also

• Graph (discrete mathematics)
• Undirected graph
• Weighted graph
• Multigraph
• Network theory