Codex @codex  0

For a directed graph, store $v$ in $\mathrm{Adj}[u]$ for the edge $u\to v$. The reverse edge $v\to u$ is separate and is stored only if it exists. Consequently, list length is outdegree, not indegree, and each directed edge contributes one entry in total. An incoming-list index is additional storage.^[ref]

Orient the seven edges of our example from earlier to later labels. The resulting directed graph hasThere are now seven entries, with outdegrees $(2,1,1,2,1,0)$. In particular, $F$ needs an empty list even though it is reached from $D,E$: incoming edges do not make $F$'s outgoing list nonempty. Replacing each directed edge by an undirected graph connection would lose this distinction.

Our running simple graph excludes self-loops and repeated edges. If those restrictions are relaxed, specify how the adjacency list encodes them. Here an undirected self-loop at $u$ contributes two copies of $u$ to $\mathrm{Adj}[u]$, matching its contribution of two to the degree of a vertex. A directed self-loop contributes one copy, and one each to outdegree and indegree. Distinct parallel edges retain distinct entries; a multigraph's list length can therefore exceed its number of distinct neighbours.^[ref][ref]

For example, add one undirected self-loop at $A$ to the seven-edge example. Its list becomes $(B,C,A,A)$, the vertex degree of $A$ becomes four, and the total entry count becomes sixteen for eight edges. If an application instead stores a self-loop once, it must account for its doubled undirected vertex degree separately. In a weighted graph, an entry can be an ordered pair $(v,w)$ meaning destination $v$ and weight $w$; the weight belongs to the edge, not to the destination vertex.

A closed walk is a walk with equal endpoint vertices, $v_m=v_0$. Under our convention this includes the zero-length walk $(v)$; returning after traversing at least one edge requires $m>0$. Closure imposes no other restriction on repeated vertices or edges. In a directed graph, a closed directed walk must also follow every directed edge in its permitted direction.^[ref]

In the shared simple graph, $A,F,A$ is a length-two closed walk that immediately backtracks along $AF$. It is not a trail, since $AF$ is used twice, and it is not a graph cycle. The length-six closed walk $A,B,C,A,D,E,A$ is a trail, since its six edges are distinct, but is not a graph cycle: it returns to $A$ midway through the journey. The length-three closed walk $A,B,C,A$ is a graph cycle, with all vertices distinct apart from the required endpoint repetition. In a simple graph that is an undirected graph, a graph cycle has length at least three; the two-step backtrack is excluded.^[ref]

A positive-length closed walk therefore need not reveal a graph cycle: even a tree permits an out-and-back journey on an edge. A positive-length closed trail in a simple graph does contain a graph cycle. For a proof outline, choose a shortest positive-length consecutive portion of the trail whose endpoint vertices coincide. It cannot repeat an internal vertex, since that would give a shorter such portion; it cannot have length one or two because self-loops and repeated edges are excluded. It is consequently a graph cycle. Cutting it out leaves another closed trail, possibly of length zero, so repetition partitions the original edges into graph cycles. In our six-step example these are the two triangles in a graph. A closed trail using every edge would be an Euler circuit; here $AF$ is omitted.

Counting return journeys makes closed walks useful even when they repeat edges. For a finite simple graph with adjacency matrix $M$, the walk count from powers of an adjacency matrix gives $(M^k{)}_{uv}$ length-$k$ walks from $u$ to $v$, for every nonnegative integer $k$. A proof outline is that matrix multiplication appends one allowed step, summing over the previous endpoint; $M^0$ is the identity matrix, recording the unique zero-length walk at each vertex. ConsequentlyThe trace counts closed walks with a specified starting vertex and traversal order, not distinct graph cycles. These formulas use adjacency entries, not arbitrary travel costs in a weighted graph.^[ref]

In our example, $(M^2{)}_{AA}=5$: the five length-two closed walks are $A,B,A$, $A,C,A$, $A,D,A$, $A,E,A$, and $A,F,A$. Also $(M^3{)}_{AA}=4$, going round either triangle in a graph in either direction, and $\mathrm{tr}(M^3)=12$: each of the two triangles in a graph supplies three choices of starting vertex and two directions. These exact counts for the constructed graph illustrate why return counts and graph cycle counts differ.

A closed walk naturally models a delivery or inspection journey that returns to its depot. Repeated vertices let it combine several excursions; repeated edges let it serve a dead end and return. For an Euclidean travelling salesman tour, one can first construct a closed walk visiting all locations and then use the triangle inequality to shortcut repeated visits without increasing total length. That argument assumes direct travel between the retained locations is permitted, as in a complete graph weighted by Euclidean distance; an arbitrary road network need not contain those shortcut edges.

The critical path method calculates an earliest schedule, a latest schedule for a chosen finish time, and each activity's task float. A critical path is a start-to-finish graph path whose total duration is greatest. There can be several such graph paths, and every one constrains completion. In the six-activity project scheduling example, the critical graph path is A-C-D-F, of duration $3+4+2+1=10$.

Add a zero-duration source $s$ before every initial activity and a zero-duration sink $z$ after every terminal activity. Give each edge $i\to j$ weight ${\tau }_i$, including zero weight on edges leaving $s$. This produces a weighted graph in which a graph path's weight counts every activity on it exactly once. The possible source-to-sink graph paths in our example, omitting the dummy endpoints, are A-B-D-F with weight 8, A-C-D-F with weight 10, and E-F with weight 4.

Every feasible schedule must accommodate each of these sequential chains. Consequently,This bound applies to all source-to-sink graph paths, not just the one we happen to inspect. The critical path method attains the bound by setting each activity's earliest start $E_i$ to the maximum of its predecessors' earliest finish times:Evaluate this recurrence in a topological order, obtained by topological sorting. Each $E_j$ satisfies every incoming optimization constraint, so these times form a feasible solution. The same recurrence calculates the greatest weight of a graph path from $s$ to $j$; hence the feasible finish $E_z$ matches the lower bound. This is dynamic programming on a Directed acyclic graph, rather than an enumeration of all graph paths. See Paul Johnson, Scheduling and longest paths, longest-path algorithm. The linear programming formulation and its certificate are developed in project scheduling duality and unit-flow certificate for project duration.

For our project scheduling example, $E_A=E_E=0$, $E_B=E_C=3$, and the two merges giveF finishes at 10. All six activities are completed, even though E is absent from the critical graph path. Recording which predecessor attains each maximum lets us trace a critical graph path backward from the sink; retaining tied choices exposes multiple critical graph paths.

Now fix the project start at zero and the finish at $T_{\ast }=10$. The latest starts $L_i$ come from a backward pass in reverse topological order:Every activity must finish by the earliest of its successors' latest starts, explaining the minimum here. This gives $L_F=9$, $L_D=7$, $L_E=6$, $L_B=5$, $L_C=3$, and $L_A=\min (5-3,3-3)=0$. These latest times themselves form a feasible solution finishing at 10. The backward calculation depends on the chosen finish time; a later deadline would give different latest times and task floats. The forward and backward passes are described in Olivier de Weck, MIT ESD.36 Lecture 2, slides 22–29.

Changing a duration can change which graph paths are critical. If B's duration becomes 4, A-B-D-F and A-C-D-F both take 10: there are two critical graph paths. Shortening C alone then cannot reduce the finish time, because the chain through B still takes 10. If B's duration instead becomes 5, the earliest starts of D and F become 8 and 10, and the finish becomes 11. A-B-D-F is now the unique critical graph path; C has task float 1 relative to that new optimal finish. These calculations show why the critical path method is useful for understanding where a duration change matters, even in a project containing many parallel activities.

An electrical network is a weighted graph whose edge weights are interpreted as electrical conductances. Random-walk hitting quantities can then be expressed through voltages, currents, and effective resistance.

A geometric spanner is a weighted graph on points in Euclidean space, with edge weights equal to their Euclidean distances, in which every pair has a graph path of length at most $t$ times its direct distance. Its stretch factor is the largest ratio $d_G(u,v)/\Vert u-v\Vert$, where $d_G$ is shortest-path distance. A square's four perimeter edges, without diagonals, give stretch factor $\sqrt{2}$: adjacent points have ratio one, and diagonal pairs have route length $2$ instead of $\sqrt{2}$. The aim is to retain short routes with fewer edges than a complete graph. ^[ref].

Graph theory studies vertices and the edges connecting them: which graph paths exist, how efficiently we can travel, and which connections are indispensable. A road map becomes a graph when junctions are vertices and road segments are edges; a communications network uses routers and links instead. The drawing helps us see connections, but its apparent lengths need not be the costs being optimized. Record travel times or transmission costs separately in a weighted graph.

The appeal of graph theory is that one model serves many practical questions. Graph paths describe routes, connected components of a graph identify isolated regions, and minimum spanning trees connect all locations cheaply. The shortest path problem asks a different question: find the cheapest journey between specified locations. Our four-vertex example below makes that distinction concrete and shows how the Dijkstra algorithm discovers a route without trying every graph path.

For the walk on a weighted graph, the Green function normalized by vertex weight isSymmetry of the conductances makes $g(x,y)=g(y,x)$, and $\mathcal{E}(g(\cdot ,y),f)=f(y)$ for finitely supported $f$.

The inequality need not be strict. Start with the nearest-neighbour weighted graph ${\mathbb{Z}}^3$, attach a new leaf $b$ only to the origin $o$, and give its edge positive weight. Take $A=\{o\}$ and $B=\{o,b\}$. A walk starting from $b$ must move to $o$ at its first non-killed step, while any walk reaching $b$ from elsewhere must first pass through $o$. Hence the equilibrium potential of a finite set is the same for the two sets:Using $\mathrm{cap}(C)=\mathcal{E}(h_C,h_C)$ for a finite set $C$ givesdespite $A\ne B$.

The shortest path problem asks for a graph path from a source vertex $s$ to a destination vertex $t$ minimizing its total edge weight. Here $w_e$ is the cost of traversing edge $e$, and costs add along the graph path. If no route exists, its shortest-path distance is $\infty$. With nonnegative edge weights, deleting cycles in a graph from a walk never increases its cost, so repetitions cannot improve the optimum.

Consider the undirected graph with vertex set $V=\{A,B,C,D\}$ and the six edge weightsEach edge can be traversed in either direction at the same cost. The direct graph path $A,D$ costs $10$; $A,B,D$ costs $4+1=5$; $A,C,D$ costs $1+5=6$. The cheapest graph path is $A,C,B,D$, costing $1+2+1=4$. The remaining graph path $A,B,C,D$ costs $11$, exhausting the possibilities without repeated vertices.

Thus fewest edges and least total cost are different objectives. Breadth-first search minimizes the number of edges, which suffices when every edge has the same positive cost. Unequal nonnegative costs call for the Dijkstra algorithm. On a map, weights might be minutes rather than kilometres: a longer-looking route can arrive sooner. This is why a weighted graph separates the network's connections from what a particular journey costs.

An undirected simple graph is exactly a pair of setsThus every edge is a two-element set of distinct vertices. The unordered pair $\{u,v\}$ equals $\{v,u\}$, so there is no direction. The distinctness condition excludes self-loops, and using a set of edges excludes parallel copies. A simple graph may have vertices with no incident edges; $E$ does not by itself determine $V$. For example, $(\{A,B\},\{AB\})$ and $(\{A,B,C\},\{AB\})$ have the same edge set but different vertex sets.^[ref]

In the six-vertex example, the vertex neighbourhood of $C$ is $\Gamma (C)=\{A,B,D\}$, so its degree of a vertex is $\mathrm{deg}(C)=3$. In label order $A,B,C,D,E,F$, the degree sequence isThis is the handshaking lemma: count each edge once at each of its two endpoints. The average degree of a graph here is $14/6=7/3$. The degree sequence is a compact consistency check on an edge list; an odd sum could not describe any finite undirected graph. It also forces the number of odd degrees of vertices to be even, since the even terms do not affect the parity of the sum.

The adjacency matrix in the figure uses label order $A,B,C,D,E,F$. Its entry $M_{uv}$ is one exactly when $\{u,v\}\in E$, and zero otherwise. It is a symmetric matrix with zero diagonal, and each row sum gives the corresponding vertex degree. For example, row $C$ is $(1,1,0,1,0,0)$. The fourteen ones count both directions of the seven undirected edges; they do not indicate fourteen different edges. This translates a picture into a representation suitable for calculation.

The restrictions matter. A directed graph uses an ordered pair to distinguish $u\to v$ from $v\to u$, so reachability can depend on direction. A multigraph can contain several distinct edges between the same vertices; adding another $CD$ would raise $\mathrm{deg}(C)$ and $\mathrm{deg}(D)$ to four without adding a new neighbour. A self-loop at $A$ contributes two to its undirected vertex degree, making it four, because both endpoints lie at $A$. Specify whether self-loops are allowed in a multigraph. Finally, a weighted graph attaches numerical information to edges: if links carry travel times, minimizing the number of edges need not minimize total time. These are changes to the model, rather than changes to how the same simple graph is drawn.

A walk records a journey through a graph as a finite alternating sequencewhere each edge $e_i$ joins the consecutive vertices $v_{i-1}$ and $v_i$. Both vertices and edges may repeat. Its length is $m$, counting edge traversals with repetitions, rather than counting different edges or measuring the drawing. Here a graph path means a walk with no repeated vertices; a trail instead forbids repeated edges. These conventions distinguish a journey's record from the subgraph consisting of the connections it used.^[ref]

Unless stated otherwise, the examples below use a finite simple graph that is an undirected graph, so an edge may be traversed in either direction. In a multigraph, retain each edge's individual identity as well as its endpoint vertices: two parallel edges are different choices for the same step. If self-loops are allowed, traversing one leaves the current vertex unchanged but adds one to the length. In a directed graph, each step must follow its directed edge from its initial to its terminal vertex, giving a directed walk; reversing a journey need not be possible.^[ref]

We allow the zero-length walk $(v)$ at every vertex $v$. It uses no edges, so it is also a trail and a graph path, and its coinciding endpoints make it a closed walk. This means staying put is a legitimate journey; a graph with no vertices has no such walk. Positive-length restrictions will be stated explicitly.^[ref]

Use the same constructed graph throughout these three sections:Here $AB$ denotes the unordered pair $\{A,B\}$, and $CA=AC$. Two triangles in a graph, $ABC$ and $ADE$, share $A$, with one extra edge $AF$. These are schematic connections, not measured roads; the highlighted connections in the diagram show which edges are used, while the numbered sequence records their order.

The length-six walk $B,C,A,B,C,A,F$ uses $BC$ and $CA$ twice, so it is not a trail. The length-six trail $B,C,A,D,E,A,F$ returns to $A$ but uses six different edges, so it is not a graph path. The length-three graph path $B,C,A,F$ repeats neither vertices nor edges. Thusfor this particular graph. The restrictions answer different routing questions: revisiting a junction is harmless for many journeys, whereas reusing a serviced road segment can matter for an inspection route. Travel costs require a weighted graph; a walk's cost adds the weight of each traversal, even when an edge is used again.

Every finite walk from $s$ to $t$ contains a graph path from $s$ to $t$ after deleting detours. For a proof outline, if $v_i=v_j$ with $i<j$, delete the intervening closed walk. The retained steps still meet at the same vertex, and the length strictly decreases. Repeating terminates with no repeated vertices, or with the zero-length graph path when $s=t$. This explains why reachability can be formulated using either walks or graph paths. With nonnegative edge weights, deletion also cannot increase cost, connecting the argument to the shortest path problem; with negative weights that cost conclusion fails.^[ref]

For a finite undirected graph without self-loops, give each edge a symmetric nonnegative weight $w_{ij}=w_{ji}$. In the weighted graph, set $(A_w{)}_{ij}=w_{ij}$ for an edge and zero otherwise, and $(D_w{)}_{ii}={\sum }_j{w}_{ij}$ with all other entries zero. The Weighted graph Laplacian isEach edge appears once in the quadratic form. For the path graph $A-B-C$ with weights $w_{AB}=2$ and $w_{BC}=3$,The Weighted graph Laplacian is still a positive semidefinite matrix. Its kernel consists of vectors constant on each connected component of a graph after zero-weight edges are removed: an edge of weight zero imposes no constraint. In an electrical network, taking the weights to be electrical conductances makes $x^T{L}_{w}x$ the total power dissipated by Joule heating when $x$ gives the voltages at the vertices. This physical interpretation explains why stronger connections penalize disagreement more heavily.^[ref]

A weighted Hamilton cycle is a Hamilton cycle in a weighted graph, with cost equal to the sum of its traversed edge weights. Here weights represent symmetric nonnegative costs, rather than conductances. Asking whether a Hamilton cycle exists is a feasibility question; asking for the cheapest one is an instance of the travelling salesman problem. A complete graph supplies every possible connection between distinct vertices, making feasibility automatic for $n\ge 3$, while choosing the cheapest visiting order remains a separate mathematical optimization problem.

Assign the complete graph $K_4$ the symmetric edge costs $w_{AB}=2$, $w_{BC}=3$, $w_{CD}=4$, $w_{AD}=5$, $w_{AC}=6$ and $w_{BD}=7$, in arbitrary units. Fix the start at $A$ and identify each Hamilton cycle with its reverse. The three possibilities areThese exhaust the possibilities: the permutations of the other three vertices give $3!=6$ orders, paired into three reversals. Hence the perimeter tour really is optimal for this toy instance. The diagram's geometric lengths are not costs, and no triangle inequality is assumed.

The usefulness of this model is to distinguish visiting required sites from covering required connections. If tasks are assigned to vertices and the route must return after one visit to each, a weighted Hamilton cycle captures the ordering requirement. If the job instead requires each edge once, the relevant object is an Euler circuit. The shortest path problem asks only for a cheapest route between specified endpoints. A 1954 primary research paper gave a concrete motivation for the travelling salesman problem: certify that a particular tour through 49 cities has minimum road-distance cost.^[ref]

These are abstract route models. If a cost stands for a whole graph path through an underlying network, travelling between consecutive task vertices can pass through intermediate network vertices more than once. One visit per task therefore does not imply one visit per physical junction. One-way connections require a directed graph; changing costs or extra timing constraints require a richer model than the fixed symmetric toy instance.