Fact-checked by Grok 2 weeks ago

Directed graph

A directed graph, also known as a digraph, is a mathematical structure in graph theory consisting of a set of vertices (or nodes) and a set of directed edges (or arcs) that connect ordered pairs of vertices, where each edge indicates a one-way relationship from a source vertex to a target vertex.^[1]^[2] Unlike undirected graphs, which model symmetric connections, directed graphs capture asymmetric or oriented relationships, such as traffic flow on one-way streets or follower connections in social networks.^[2]^[3] Key properties of directed graphs include the in-degree of a vertex, defined as the number of edges incoming to it, and the out-degree, the number of edges outgoing from it; these degrees help analyze connectivity and structure within the graph.^[4] Directed graphs may contain cycles, loops (edges from a vertex to itself), or multiple edges between the same pair of vertices in the same direction, though simple directed graphs restrict to at most one edge per ordered pair.^[5] A directed graph is strongly connected if there is a directed path between every pair of vertices, and it is acyclic (a directed acyclic graph or DAG) if it contains no directed cycles, which is crucial for applications like scheduling and dependency resolution.^[2]^[6] Directed graphs find extensive applications in computer science and engineering, including modeling prerequisites in course curricula, web page linking for search engine algorithms like PageRank, and network flows in optimization problems.^[2] Fundamental algorithms for directed graphs encompass topological sorting for acyclic graphs, shortest path computations adapted for directionality, and decomposition into strongly connected components using methods like Kosaraju's or Tarjan's.^[2] These structures also appear in operations research for project management (e.g., PERT charts) and in biology for representing metabolic pathways or neural connections.^[2]

Formal Definition

Basic Components

A directed graph, also known as a digraph, is formally defined as a pair (V, A), where V is a set of vertices and A is a set of ordered pairs (u, v) with u, v \in V, representing directed edges or arcs from u to v. This definition applies to simple directed graphs, where A contains at most one occurrence of each ordered pair (no multiple arcs) and may or may not include self-loops (arcs with u = v).^[7] These arcs indicate a one-way connection, distinguishing directed graphs from undirected graphs, in which edges lack direction and allow traversal in both ways.^[8] The directionality of arcs enables asymmetric relationships; for instance, the presence of an arc (u, v) does not require a corresponding arc (v, u), which impacts how information or flow traverses the graph.^[9] In a simple directed graph without self-loops, no arcs from a vertex to itself and no multiple arcs between the same ordered pair of distinct vertices are allowed.^[10] For example, consider vertices V = \{a, b, c\} with arcs A = \{(a, b), (b, c)\}; this forms a simple directed path from a to c without loops or duplicates. In more general directed graphs (multidigraphs), self-loops and multiple arcs between the same ordered pair are permitted, where A is treated as a multiset of ordered pairs or defined using a multiplicity function from V \times V to non-negative integers.^[3] Directed graphs can be represented using adjacency matrices, where entry (i, j) indicates an arc from vertex i to j, or adjacency lists that store outgoing neighbors for each vertex.

Mathematical Representation

A directed graph G = (V, A), consisting of a set V of vertices and a set A of directed arcs, can be formally represented using matrices or lists to encode the structure for computational and theoretical analysis.^[2] The adjacency matrix is a square n \times n matrix A, where n = |V|, and the entry A_{ij} = 1 if there is a directed arc from vertex i to vertex j, and A_{ij} = 0 otherwise.^[2] For weighted directed graphs, A_{ij} instead holds the weight of the arc from i to j, or 0 if no arc exists. In multidigraphs, A_{ij} can represent the number of arcs from i to j.^[11] The adjacency list representation maps each vertex to a list of its outgoing neighbors, storing the graph as a collection of such lists, one per vertex.^[12] This structure directly reflects the arcs by listing the targets reachable from each source vertex. The incidence matrix is a rectangular |V| \times |A| matrix B, with rows indexed by vertices and columns by arcs; for an arc from vertex u (tail) to vertex v (head), the entry B_{u,k} = -1, B_{v,k} = 1, and all other entries in column k are 0.^[13] Adjacency matrices enable constant-time O(1) queries to check for the existence of an arc between any pair of vertices, making them advantageous for dense graphs where many arcs are present, though they require \Theta(n^2) space regardless of the number of arcs.^[14]^[15] In contrast, adjacency lists use \Theta(|V| + |A|) space, which is more efficient for sparse graphs with few arcs relative to n^2, but arc existence queries take O(d) time where d is the out-degree of the source vertex.^[16] Incidence matrices, while useful in linear algebra applications such as computing the graph Laplacian, are less common for general purposes due to their larger size proportional to |A| and the need for arc indexing.^[13] For example, consider a directed graph with vertices V = \{1, 2, 3\} and arcs A = \{(1,2), (2,3)\}. The adjacency matrix is

\begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{pmatrix},

the adjacency list is

1: {{grok:render&&&type=render_inline_citation&&&citation_id=2&&&citation_type=wikipedia}}, \, 2: {{grok:render&&&type=render_inline_citation&&&citation_id=3&&&citation_type=wikipedia}}, \, 3: []

, and the incidence matrix (with columns for arcs e_1 = (1,2) and e_2 = (2,3)) is

\begin{pmatrix} -1 & 0 \\ 1 & -1 \\ 0 & 1 \end{pmatrix}.

Terminology

Core Concepts

In a directed graph, an arc, also known as a directed edge, connects two vertices by specifying a tail (origin) and a head (destination), thereby imposing a one-way relationship between them.^[17] A directed walk is a sequence of one or more arcs such that the head of each arc coincides with the tail of the subsequent arc, allowing traversal from an initial vertex to a terminal vertex while following the directions; directed walks permit repeated vertices.^[18] A directed path is a directed walk with no repeated vertices.^[18] A directed cycle arises when a directed path starts and ends at the same vertex, forming a closed loop where every arc points forward in the sequence.^[17] For example, in a directed graph with vertices A, B, and C, the arcs A → B, B → C, and C → A constitute a directed cycle of length 3, which can be detected by tracing paths that revisit the origin.^[17] A path of length k involves exactly k arcs and k+1 distinct vertices.^[19] Certain vertices play special roles based on arc incidence: a source is a vertex with no incoming arcs, serving as a potential starting point for paths, while a sink is a vertex with no outgoing arcs, acting as an endpoint.^[17] An oriented graph is a specific type of directed graph formed by assigning a direction to each edge of an underlying undirected simple graph, without introducing multiple arcs or loops between the same pair of vertices.^[17] A key distinction from undirected graphs is that a directed graph can be acyclic—lacking any directed cycles—even when its underlying undirected graph contains cycles, as the orientations may prevent closed directed loops.^[20]

Degree Measures

In a directed graph, the out-degree of a vertex v, denoted d^+(v) or \mathrm{outdeg}(v), is defined as the number of arcs that originate from v.^[5] Similarly, the in-degree of v, denoted d^-(v) or \mathrm{indeg}(v), is the number of arcs that terminate at v.^[5] The total degree of v is then given by the sum d(v) = d^+(v) + d^-(v), which accounts for all arcs incident to v regardless of direction.^[21] A fundamental property relating these measures across the graph is the handshaking lemma for directed graphs, which asserts that the sum of all out-degrees equals the sum of all in-degrees, and both equal the total number of arcs |A|.^[22] This can be expressed mathematically as:

\sum_{v \in V} d^+(v) = \sum_{v \in V} d^-(v) = |A|.

The equality holds because each arc contributes exactly one unit to the out-degree of its starting vertex and one unit to the in-degree of its ending vertex.^[21] These degrees can be computed efficiently using the adjacency matrix of the directed graph, where the out-degree of a vertex corresponds to the sum of the entries in its row, and the in-degree to the sum of the entries in its column.^[23] For example, consider a vertex with out-degree 3 and in-degree 0; such a vertex serves as a source, with three outgoing arcs but no incoming ones.^[5] Special cases include an isolated vertex, which has both in-degree and out-degree equal to 0, and a self-loop at a vertex, which increments both its in-degree and out-degree by 1.^[5]

Structural Properties

Degree Sequences

In a directed graph with n vertices, the out-degree sequence is the nonincreasing list of out-degrees d^+ = (d^+_1 \geq d^+_2 \geq \dots \geq d^+_n), where each d^+_i is the number of edges departing from vertex i, and $0 \leq d^+_i \leq n-1. The in-degree sequence is defined analogously as d^- = (d^-_1 \geq d^-_2 \geq \dots \geq d^-_n), with each d^-_i counting edges arriving at vertex i.^[24] A pair of such sequences (d^+, d^-) is termed graphical if there exists a simple directed graph (no self-loops or multiple edges in the same direction) realizing exactly these in- and out-degrees. The Fulkerson–Chen–Anstee theorem gives necessary and sufficient conditions for graphicality: assuming the sequences consist of nonnegative integers with \sum_{i=1}^n d^+_i = \sum_{i=1}^n d^-_i = m (the number of edges), the pair is graphical if and only if, for every k = 1, 2, \dots, n,

\sum_{i=1}^k d^+_i \leq k \sum_{i=1}^k \min\{d^-_i, k-1\} + \sum_{i=k+1}^n \min\{d^-_i, k\}.

This formulation ensures no subset of vertices exceeds the possible incoming edges from the rest of the graph, accounting for the no-self-loop constraint.^[25]90301-2) The theorem admits a constructive proof via a greedy algorithm analogous to the Havel–Hakimi procedure for undirected graphs. To realize the sequences, sort the vertices by nonincreasing out-degree and, for the vertex v with the highest remaining out-degree d^+(v), connect it to the d^+(v) vertices with the highest remaining in-degrees (excluding itself). Reduce the in-degrees of those targets by 1, remove v (setting its in- and out-degrees to 0), and repeat on the reduced instance until all degrees are zero or a contradiction arises. If the process succeeds without negative degrees, the graph is constructed; otherwise, the sequences are non-graphical. This runs in O(n^2) time.^[26] For example, consider n=3 with out-degree sequence (2,1,1) and in-degree sequence (1,1,2). The sums match at 4, and the inequalities hold for all k: for k=1, $2 \leq 1 \cdot \min(1,0) + \min(1,1) + \min(2,1) = 0 + 1 + 1 = 2; similar verifications for k=2,3. A realization is vertices A,B,C with edges A \to B, A \to C, B \to C, C \to A (adjusting labels to match sequences). In contrast, out-degrees (2,1,0) and in-degrees (1,2,0) fail the condition for k=1 ($2 > 1 \cdot \min(1,0) + \min(2,1) + \min(0,1) = 0 + 1 + 0 = 1) and cannot be realized, as the high-out-degree vertex cannot connect to enough valid targets without self-loops.^[25]90301-2) Compared to undirected graphs, where a single sequence must satisfy symmetric conditions like the Erdős–Gállai theorem, directed graphical sequences offer greater flexibility due to the asymmetry between in- and out-degrees, allowing structures impossible in undirected realizations.^[24]

Connectivity

In directed graphs, connectivity can be assessed in two primary ways: weak and strong. A directed graph is weakly connected if its underlying undirected graph—obtained by ignoring edge directions—is connected, meaning there exists an undirected path between every pair of vertices.^[2] This notion captures overall structural cohesion without regard to directionality. For example, a directed tree with all edges oriented away from the root is weakly connected, as the underlying undirected tree connects all vertices, but it lacks return paths to the root.^[27] A directed graph is strongly connected if there is a directed path from every vertex to every other vertex.^[2] Strong connectivity implies mutual reachability and is a stricter condition than weak connectivity; every strongly connected graph is weakly connected, but the converse does not hold. A classic example is a directed cycle, where each vertex has a successor and predecessor, ensuring paths in both directions around the cycle.^[27] In contrast, the outward-oriented tree mentioned earlier is not strongly connected, as leaves cannot reach the root or siblings via directed paths. The strongly connected components (SCCs) of a directed graph are the maximal subgraphs that are strongly connected.^[2] These components partition the graph into equivalence classes based on mutual reachability. The condensation of the graph is formed by contracting each SCC to a single vertex, resulting in a directed acyclic graph (DAG) where edges between vertices represent connections between distinct SCCs.^[28] This structure reveals the hierarchical organization of reachability, with no cycles across components. Efficient algorithms exist for identifying SCCs, including Kosaraju's algorithm, which performs two depth-first searches—one on the original graph and one on its transpose—to achieve linear time complexity O(|V| + |E|), and Tarjan's algorithm, which uses a single depth-first search with additional bookkeeping to find SCCs in the same time bound.^[27] These methods, seminal in graph theory, enable practical computation of connectivity structures in large directed graphs.

Variants and Types

Subclasses of Directed Graphs

Directed acyclic graphs (DAGs) form a fundamental subclass of directed graphs characterized by the absence of directed cycles, ensuring a topological order exists among vertices where arcs only point from earlier to later vertices in the ordering. This property makes DAGs particularly useful in applications such as scheduling tasks with precedence constraints, topological sorting, and modeling dependencies in computational workflows. Seminal work on DAGs highlights their kernel-perfect nature, meaning every induced subgraph admits a kernel—a stable set that absorbs all vertices via outgoing arcs—and they are solvable in polynomial time for problems like finding longest paths or feedback arc sets.^[29] Tournaments represent another key subclass, defined as directed graphs where every pair of distinct vertices is connected by exactly one directed arc, often modeling round-robin competitions or pairwise comparisons. Every tournament has a Hamiltonian path, and strong tournaments (those with a directed path between any pair of vertices) contain a Hamiltonian cycle (Camion's theorem), as established in foundational results by Rédei and others. These graphs are extensively studied for properties like score sequences and kings (vertices reaching all others in at most two steps), with polynomial-time algorithms available for problems such as finding arc-disjoint paths.^[29]^[2] Semicomplete digraphs generalize tournaments by requiring at least one arc between every pair of distinct vertices, allowing bidirectional arcs (2-cycles) while excluding missing connections. This subclass includes tournaments as a special case and is notable for its quasi-transitive variants, where the existence of arcs xy and yz (with x \neq z) implies at least one arc between x and z. Semicomplete digraphs admit efficient algorithms for connectivity augmentation and 2-path problems, and they often exhibit strong connectivity properties, with every strong semicomplete digraph on n \geq 3 vertices having diameter at most 2. Multipartite semicomplete digraphs, where vertices are partitioned into independent sets with all possible arcs between different parts, extend this further and share Hamiltonicity guarantees under weak conditions.^[29] Oriented graphs constitute a subclass obtained by assigning directions to the edges of an undirected simple graph without creating 2-cycles, effectively representing asymmetric relations. These are asymmetric in nature and serve as orientations of undirected graphs, preserving underlying connectivity while introducing directionality. Oriented graphs are central to problems like graph orientation for minimizing maximum out-degree (as in the seminal Havel-Hakimi-like algorithms for score sequences) and are analyzed for acyclic orientations in comparability graphs. They differ from tournaments by not requiring completeness, allowing sparser structures.^[29] Strong digraphs, where there exists a directed path from every vertex to every other, form a connectivity-focused subclass essential for studying robustness in networks. This property implies the existence of cycles covering all vertices in sufficiently large strong digraphs, and k-strong variants (with k vertex-disjoint paths between any pair) generalize this for fault-tolerant designs. Applications include communication networks, where strong connectivity ensures reachability. Balanced digraphs, a related subclass where each vertex has equal in-degree and out-degree, model Eulerian circuits in directed multigraphs and are key to arc-decomposition problems.^[29]

Directed Graphs with Additional Properties

Directed graphs can be augmented with additional properties on their arcs or vertices to model more complex relationships and real-world phenomena. One common enhancement is the assignment of weights to arcs, resulting in a weighted digraph, where each arc carries a numerical value representing attributes such as cost, distance, or capacity. These weights enable the analysis of quantitative aspects, such as optimizing paths in networks where the goal is to minimize total cost or maximize throughput. Weighted digraphs are foundational in operations research and computer science, particularly for problems involving resource allocation and routing.^[30] Labeled digraphs extend this by associating descriptive labels with arcs or vertices, which can encode qualitative information like types of relationships or categories. For instance, in semantic networks, vertices represent concepts and labeled arcs denote associations such as "is-a" or "part-of," facilitating knowledge representation and inference in artificial intelligence systems. This labeling allows for richer semantic modeling compared to unadorned digraphs, enabling applications in natural language processing and ontology construction.^[31] Signed digraphs incorporate signs on arcs, typically positive or negative, to capture relational polarities like friendship or antagonism in social structures. This property is central to balance theory, which posits that a signed digraph is balanced if the product of the signs around any cycle is positive, implying structural stability akin to all-positive or all-negative cycles. The theory, introduced by Frank Harary,^[32] provides a framework for analyzing social cohesion and conflict resolution in networks. Oriented graphs represent a specific symmetry consideration in directed structures, defined as digraphs with no bidirectional arcs between any pair of vertices, ensuring asymmetry in connections. In contrast, symmetric variants, such as digraphs allowing 2-cycles, permit mutual arcs that mirror each other, effectively embedding undirected edges within a directed framework. These distinctions influence properties like tournament analysis, where oriented graphs without symmetric pairs model competitive relations.^[33] Prominent examples of directed graphs with these properties include flow networks, which are weighted digraphs where arc weights denote capacities for modeling commodity transport from sources to sinks, as formalized in the maximum flow problem. Similarly, artificial neural networks can be viewed as weighted digraphs, with vertices as neurons and weighted arcs as synaptic connections that propagate signals during learning processes like backpropagation.^[34] In applications, weighted digraphs underpin transportation systems by representing routes with weights as travel times or fuel costs, aiding in efficient routing and logistics optimization. Labeled digraphs appear in dependency graphs, such as those in software compilation, where arcs labeled with attribute flows illustrate interdependencies among program elements to guide code generation and optimization.^[35]^[31]

References

[1]
4.2 Directed Graphs - Algorithms, 4th Edition
Jan 14, 2020 · A directed graph (or digraph) is a set of vertices and a collection of directed edges that each connects an ordered pair of vertices.
[2]
[PDF] 6.042J Chapter 6: Directed graphs - MIT OpenCourseWare
A graph with directed edges is called a directed graph or digraph. Definition 6.1.1. A directed graph G D .V;E/ consists of a nonempty set of nodes V and a set ...
[3]
[PDF] Chapter 8 Graphs: Definition, Applications, Representation
Directed graphs are in some sense more general than undirected graphs since we can easily represent an undirected graph by a directed graph by placing an arc ...<|control11|><|separator|>
[4]
5.11 Directed Graphs
A directed graph, or digraph, is a graph where edges have a direction, indicated by an arrow, and are represented as ordered pairs (v,w) or (w,v).
[5]
[PDF] Lecture 16: Directed graphs and multigraphs - Faculty Web Pages
A multigraph allows loops and parallel edges. A directed graph has directed edges (arcs) from v to w, and can have multiple arcs from v to w.
[6]
[PDF] Lecture 4: Introduction to Graph Theory and Consensus - Caltech
Mar 16, 2009 · • A directed graph is irreducible if, given any two vertices, there exists ... • Spectral properties related to connectivity of graph.
[7]
directed graph
Formal Definition: A graph G is a pair (V,E), where V is a set of vertices, and E is a set of edges between the vertices E ⊆ {(u,v) | u, v ∈ V}.
[8]
Directed and Undirected Graphs - MATLAB & Simulink - MathWorks
For directed graphs the edge direction (from source to target) is important, but for undirected graphs the source and target node are interchangeable.
[9]
[PDF] Digraphs: Walks & Paths: Chapter 9.1 – 9.4 - MIT OpenCourseWare
Definition 9.0.1. A directed graph, G, consists of a nonempty set, V.G/, called the vertices of G, and a set, E.G/, called the edges of G. An element of V.G ...
[10]
Simple Directed Graph -- from Wolfram MathWorld
A simple directed graph is a directed graph having no multiple edges or graph loops (corresponding to a binary adjacency matrix with 0s on the diagonal).
[11]
[PDF] Graph Theory Fundamentals
The adjacency matrix for a graph is n X n and each element contains 0 for non-neighbors and the edge weight for neighbors. A = Page 5.
[12]
Lecture 24: Graph Representations and Traversals
Directed graphs are commonly represented as an adjacency list , which comprises an array or list of vertices, where each vertex vi stores a list of all the ...
[13]
[PDF] Graphs, networks, incidence matrices - MIT OpenCourseWare
Incidence matrices. The incidence matrix of this directed graph has one column for each node of the graph and one row for each edge of the graph: ⎤. ⎡ -1. 1.
[14]
Introduction to Graphs - cs.wisc.edu
If the graph is sparse (there are not many edges), then adjacency lists will probably be more space efficient than adjacency matrices; if the graph is dense ( ...
[15]
[PDF] Representing Graphs
• Advantages of the adjacency matrix to look through the list of neighbors of the node to find whether the other node is a neighbor.
[16]
[PDF] Directed graphs - UMD Computer Science
One advantage of adjacency list representation over adjacency matrix representation of a graph is that in adjacency list representation, space is saved for ...
[17]
[PDF] Section 1.5. Directed Graphs
Sep 17, 2022 · A directed path or directed cycle is an orientation of a path or cycle in which each vertex is joined to its successor in the sequence. Note. ...
[18]
[PDF] Networks:
Networks: Definitions and notation: Directed graphs and Networks: A directed graph, G = ( N, A ) consists of a set of N. Nodes and a set of A arcs whose ...
[19]
[PDF] graph theory: basic definitions and theorems
In a directed graph, the in-degree of a vertex is the number of edges incident to the vertex and the out-degree of a vertex is the number of edges incident from ...
[20]
[PDF] Directed graphs Digraph D = (V,A). V ={vertices}, A={arcs}
A Directed Acyclic Graph (DAG) is a digraph without any directed cycles. Lemma 1 If D is a DAG then D has at least one source (vertex of indegree 0) and at ...
[21]
[PDF] CS311H: Discrete Mathematics Introduction to Graph Theory
In-Degree and Out-Degree of Directed Graphs. ▷ The in-degree of a vertex v, written deg−(v), is the number of edges going into v. ▷ deg−(a) = ▷ The out ...Missing: lemma | Show results with:lemma
[22]
[PDF] Discrete Methods in Computer Science Spring 2025 Basics of Graph ...
In-degree deg. -. (v) is number of edges entering v. Out-degree deg+(v) is number of edges leaving v. Directed Graphs. 2/34. Page 4. Hand-Shaking Lemma for ...<|control11|><|separator|>
[23]
[PDF] Chapter 9. Graph Theory - UCSD Math
The sum of entries in row u is the outdegree of u. The sum of entries in column v is the indegree of v. Prof. Tesler. Ch. 9. Graph Theory.
[24]
[PDF] Configuring Random Graph Models with Fixed Degree Sequences
Most importantly, a directed graph has two separate degree sequences, the in-degree se- quence and the out-degree sequence, and one may wish to fix either or ...
[25]
ZERO-ONE MATRICES WITH ZERO TRACE - Project Euclid
1 inequalities.
[26]
A simple Havel-Hakimi type algorithm to realize graphical degree ...
May 29, 2009 · ... degree sequence of a simple graph is the greedy algorithm of Havel and Hakimi. This note extends their approach to directed graphs. It also ...
[27]
[PDF] Algorithms - cs.Princeton
giant weakly connected component,. Page 7. Vertex = variable; edge = logical ... constant-time client strong-connectivity query. 5 strongly-connected components.
[28]
[PDF] Fundamental Graph Algorithms
condensation GSCC of G is a DAG. connection between SCCs and DAGs: the SCCs of a graph form a DAG. clusters of nodes.
[29]
[PDF] Digraphs Theory, Algorithms and Applications - Computer Science
Aug 15, 2007 · ... graph theory, combinatorial optimization and graph algorithms. Furthermore, it can be used for more focused ... Special Classes of Digraphs ...
[30]
Network Flows: Theory, Algorithms, and Applications - Google Books
This book provides an integrative view of the theory, algorithms and applications of network flows ... Ahuja, Ravindra Ahuja, Thomas L. Magnanti, James B. Orlin.
[31]
Directed Labeled Graph - an overview | ScienceDirect Topics
Semantic networks are modeled as labeled directed graphs, representing hierarchical and associative knowledge. 20. Domain maps, a type of ontology, can also ...Introduction to Directed... · Formal Definitions and... · Algorithms for Directed...
[32]
[PDF] bang-jensen-gutin_digraph-book.pdf - UC Davis Mathematics
... special classes of digraphs. We illustrate an application due to Cheriyan and Thurimella of Mader's results on minimally k-(arc)-strong digraphs to the.
[33]
[PDF] maximal flow through a network - lr ford, jr. and dr fulkerson
L. R. FORD, JR. AND D. R. FULKERSON. Introduction. The problem discussed in this paper was formulated by. T. Harris as follows: "Consider a rail network ...Missing: citation | Show results with:citation
[34]
[PDF] Application of Graph Theory in Transportation Networks
Jul 7, 2017 · San Francisco and Los Angeles draw the weighted graph. Some approximate road distances among four city. New York, Oklahoma city. SF. 2930. NY.Missing: digraphs | Show results with:digraphs