Directed graph

A directed graph, or digraph, is a graph whose edges have direction, so each connection goes from one vertex to another in an ordered pair. In Combinatorics, it models one-way relationships, paths, and flow.

What is directed graph?

A directed graph in Combinatorics is a set of vertices connected by edges that point in a specific direction. Instead of thinking of an edge as a two-way link, you treat it as an ordered pair, like A to B. That direction matters because A to B does not automatically mean B to A.

This is the version of a graph you use when the relationship is not symmetric. A web link from one page to another, a one-way street, or a prerequisite chain in a class schedule all behave this way. The graph is still made of the same basic pieces as any graph, but the arrow changes how you read every connection.

One of the first things you do with a directed graph is track direction-based counts. A vertex can have an out-degree, which counts arrows leaving it, and an in-degree, which counts arrows entering it. That distinction shows up a lot in problems about influence, routing, prerequisites, and network movement.

Directed graphs also make paths more restrictive. A path has to follow the arrows, so a route that looks connected on paper may not actually be usable if the directions do not line up. This is why directed graphs show up in shortest path problems and flow problems, where the allowed movement through the network matters more than just the presence of edges.

Some directed graphs contain cycles, meaning you can follow the arrows and return to where you started. Others are acyclic, which means no directed cycle is possible. That difference matters in scheduling and dependency problems, because a cycle can create a loop of tasks that never gets a clean starting point.

You will also see directed graphs written in adjacency lists or adjacency matrices. In an adjacency matrix, the row and column order tells you which direction the edge goes, so the entry for A to B can be different from B to A. That is one of the easiest places to make a mistake if you are used to undirected graphs.

Why directed graph matters in COMBINATORICS

Directed graphs are the language Combinatorics uses for one-way structure. Once direction enters the picture, counting and tracing become more specific, because you are no longer asking whether two vertices are connected, you are asking whether you can move from one vertex to another in the correct order.

That matters in shortest path problems, where a route only counts if every step follows the arrows. It also matters in maximum flow and minimum cut problems, where edges carry capacity in a fixed direction and the whole setup depends on where flow can enter and leave the network. If you ignore direction, you can easily get the wrong answer.

Directed graphs also turn dependency questions into clean combinatorics problems. A task schedule, for example, can be modeled with arrows from each prerequisite to the task that depends on it. Then you can look for a topological ordering, which tells you a valid sequence when no cycle blocks the process.

Even outside formal algorithms, directed graphs help you read real systems more accurately. If a problem describes one-way streets, citations, web links, or transfers that only go one direction, the direction is part of the math, not just decoration.

How directed graph connects across the course

Vertex

Vertices are the nodes in a directed graph, and direction only makes sense because each arrow starts at one vertex and ends at another. When you solve a problem, you usually name the vertices first, then list which outgoing edges leave each one. That makes it easier to track paths, degrees, and reachability.

Edge

An edge is the connection between two vertices, but in a directed graph it is an ordered connection. That order changes how you read the graph, because the edge from A to B is not the same as the edge from B to A. This is the main idea behind one-way movement in graph problems.

Weighted graph

A directed graph can also be weighted, which means each directed edge carries a number such as cost, distance, or capacity. Then you have to pay attention to both direction and weight at the same time. That combination shows up often in shortest path and flow questions, where the arrow tells you where you can go and the weight tells you the price or limit.

Out-degree

Out-degree counts how many edges leave a vertex in a directed graph, so it is a natural companion to direction. Problems may ask you to compare out-degree with in-degree, identify a source or sink, or interpret which vertices send information outward. It is one of the fastest ways to summarize a directed network.

Is directed graph on the COMBINATORICS exam?

A problem set or quiz question might give you a directed graph and ask you to list all valid paths, find the out-degree of each vertex, or decide whether a proposed route is allowed. In flow problems, you use the arrows to see which edges can carry flow forward and where bottlenecks appear. In shortest path work, you only count routes that follow direction, so a visually close vertex may be unreachable.

You may also be asked to read a matrix or adjacency list and translate it back into arrows on a graph. A common mistake is treating the edge as two-way just because the vertices are connected. Another common move is checking whether a directed cycle exists before trying to produce an ordering or schedule.

Directed graph vs mixed graph

A mixed graph has both directed and undirected edges, while a directed graph uses arrows for all of its edges. If a problem includes some two-way connections and some one-way connections, it is mixed, not purely directed. That difference changes how you read the network and which paths are allowed.

Key things to remember about directed graph

• A directed graph uses arrows, so each edge has an order from one vertex to another.

• Direction changes the math, because A to B does not imply B to A.

• Out-degree counts edges leaving a vertex, while in-degree counts edges entering it.

• Directed graphs are the right model for one-way streets, prerequisites, web links, and flow networks.

• When you solve a problem, always check whether a path follows the arrows before you count it.

Frequently asked questions about directed graph

What is a directed graph in Combinatorics?

A directed graph, or digraph, is a graph whose edges have direction. Each edge goes from one vertex to another, so the pair is ordered. In Combinatorics, this matters whenever the relationship is one-way, like a prerequisite chain or a route that only moves forward.

How is a directed graph different from an undirected graph?

In an undirected graph, an edge connects two vertices without direction, so you can treat it as a two-way link. In a directed graph, the arrow matters, and you have to follow it exactly. That means the same two vertices can behave very differently depending on which direction the edge points.

What does out-degree mean in a directed graph?

Out-degree is the number of directed edges leaving a vertex. It tells you how many places you can go next from that node. In many Combinatorics problems, out-degree helps you spot sources, compare vertices, or read a network more efficiently.

Why do directed graphs show up in shortest path and flow problems?

Shortest path problems only count routes that follow the arrows, so direction determines which paths are even valid. Flow problems also depend on direction because capacity moves through edges in a set direction. If you ignore the arrows, you can end up using edges that are not actually available.