standarddeviationcalculator.net

Updated Free · runs in your browser

Math

Graph theory calculator

Type a graph as a list of edges, with weights if it has them. The calculator draws it and works through the standard questions: degrees, connectivity, traversals, the shortest path between two vertices, the minimum spanning tree, Euler paths and whether it is bipartite.

Write "A B 4", "A-B 4" or "A -> B" (no weight means weight 1). A line with one name adds an isolated vertex.

Shortest path A → F 13
RouteA → C → B → D → E → F
Vertices, edges6, 9
ConnectedYes
EulerPath B to E
BipartiteNo
MST weight13
4215810263ABCDEF

Red: shortest path A → C → B → D → E → F. Vertices are placed evenly round a circle.

Degrees
VertexDegree
A2
B3
C4
D4
E3
F2
Sum18
Adjacency matrix (number of edges from row to column)
ABCDEF
A011000
B101100
C110110
D011011
E001101
F000110
PropertyResult
Vertices, edges6, 9 (simple graph)
Handshake checkΣ deg = 18 = 2 × 9 ✓
Connected?Yes
Components{A, B, C, D, E, F}
BFS from AA → B → C → D → E → F
DFS from AA → B → C → D → E → F
EulerEuler path: B → A → C → B → D → C → E → D → F → E. Exactly two vertices, B and E, have odd degree; the path must start at one and end at the other.
Bipartite?No. B and C are joined but would need the same side: the graph has an odd cycle.
Minimum spanning treeB–C (1), A–C (2), D–E (2), E–F (3), B–D (5); total weight 13
Dijkstra from A: tentative distance (previous vertex) after each step; bold = fixed this step, ✓ = fixed earlier
StepVisitABCDEF
1A04 (A)2 (A)∞∞∞
2C✓3 (C)210 (C)12 (C)∞
3B✓3✓8 (B)12 (C)∞
4D✓✓✓810 (D)14 (D)
5E✓✓✓✓1013 (E)
6F✓✓✓✓✓13
Show the working, step by step

  1. Read the 9 edges. The graph is undirected.

    V = {A, B, C, D, E, F}

  2. Degrees: each edge adds 1 to both of its ends (a loop adds 2). The handshake lemma says the degrees sum to twice the number of edges.

    2 + 3 + 4 + 4 + 3 + 2 = 18 = 2 × 9

  3. Breadth-first search from A visits vertices in order of distance (in edges); depth-first search follows one branch as far as it goes before backing up. Neighbours are taken in alphabetical order.

    BFS: A, B, C, D, E, F DFS: A, B, C, D, E, F

  4. Dijkstra: start with d(A) = 0 and every other distance ∞. Repeatedly fix the unvisited vertex with the smallest distance and relax its edges: if d(u) + w(u, v) < d(v), lower d(v).

    step 1: fix A at 0 step 2: fix C at 2 step 3: fix B at 3 step 4: fix D at 8 step 5: fix E at 10 step 6: fix F at 13

  5. Follow the previous-vertex links back from F.

    A → C → B → D → E → F, length 13

  6. Kruskal: sort the edges by weight and add each one unless it would close a cycle.

    B–C (1): add A–C (2): add D–E (2): add E–F (3): add A–B (4): skip, would make a cycle B–D (5): add total weight = 1 + 2 + 2 + 3 + 5 = 13

  7. Euler: Exactly two vertices, B and E, have odd degree; the path must start at one and end at the other.

Entering a graph

Put one edge on each line as two vertex names and an optional weight: A B 4, A-B 4 or A -> B. An edge without a weight has weight 1, so on an unweighted graph the shortest path counts edges. A line with a single name adds a vertex with no edges. Choose “Directed” to read A B as an arc from A to B. Repeated edges and loops are allowed; a loop adds 2 to its vertex’s degree.

A worked example

The default graph has six vertices and nine weighted edges:

A–B 4 A–C 2 B–C 1 B–D 5 C–D 8 C–E 10 D–E 2 D–F 6 E–F 3

  1. Degrees: A 2, B 3, C 4, D 4, E 3, F 2. They sum to 18 = 2 × 9, as the handshake lemma requires.
  2. Shortest path from A to F (Dijkstra): fix A at 0, then C at 2, B at 3 (through C, cheaper than the direct edge of 4), D at 8, E at 10 and F at 13. Following the links back gives A → C → B → D → E → F, length 13. The direct-looking route A → B → D → F costs 4 + 5 + 6 = 15.
  3. Minimum spanning tree (Kruskal): take B–C (1), A–C (2), D–E (2), E–F (3); skip A–B (4), which would close the triangle A, B, C; take B–D (5). Five edges join all six vertices, total weight 1 + 2 + 2 + 3 + 5 = 13.
  4. Euler: B and E are the only odd vertices, so there is an Euler path from B to E but no circuit. One such path is B → A → C → B → D → C → E → D → F → E.
  5. Bipartite: no. A, B and C form a triangle, an odd cycle.

That the shortest path and the spanning tree both total 13 is a coincidence. They answer different questions: the tree connects every vertex as cheaply as possible, and a shortest path between two vertices need not follow it.

What each result means

ResultMeaningMethod
ConnectedEvery vertex can reach every otherSearch from each unvisited vertex
BFS orderVertices by number of edges from the startQueue
DFS orderOne branch followed to its end before backing upRecursion
Shortest pathLeast total weight from start to endDijkstra
Spanning treeCheapest set of edges joining all verticesKruskal
Euler pathA walk using every edge exactly onceDegree test, then Hierholzer
BipartiteVertices split into two sides, edges only between themTwo-colouring

Neighbours are visited in alphabetical (or numerical) order, which is the usual convention in textbook exercises, so BFS and DFS orders match hand working. For a directed graph, the calculator reports in- and out-degrees, weak and strong connectivity, and the directed Euler conditions; a spanning tree is only computed for undirected graphs.

Common mistakes

  • Fixing a vertex too early in Dijkstra. B’s distance starts at 4 from the direct edge, but drops to 3 through C. Only the smallest tentative distance is final.
  • Negative weights with Dijkstra. A negative edge can undercut a vertex that is already fixed. The calculator skips Dijkstra if any weight is negative.
  • Confusing Euler and Hamilton. An Euler path uses every edge once; a Hamilton path visits every vertex once. There is no simple degree test for Hamilton paths.
  • Counting a loop once. A loop at a vertex adds 2 to its degree.

Common questions

How does Dijkstra’s algorithm find the shortest path?

It keeps a tentative distance for every vertex, starting at 0 for the source and ∞ for the rest. At each step it fixes the unvisited vertex with the smallest distance, which cannot get any shorter, and relaxes that vertex’s edges: if going through it gives a neighbour a shorter route, the neighbour’s distance drops. When the target is fixed, following the “previous vertex” links backwards gives the route. It needs weights of 0 or more.

When does a graph have an Euler path or an Euler circuit?

An Euler path uses every edge exactly once. In a connected undirected graph, an Euler circuit (ending where it started) exists when every vertex has even degree, and an Euler path exists when exactly two vertices have odd degree; it must start at one of them and end at the other. With four or more odd vertices there is neither. The default graph has odd vertices B and E, so it has an Euler path from B to E.

What is the handshake lemma?

The degrees of all the vertices add up to twice the number of edges, because every edge has two ends. So the number of odd-degree vertices is always even. In the default graph the degrees are 2, 3, 4, 4, 3 and 2, which sum to 18 = 2 × 9.

How do I know if a graph is bipartite?

Try to colour the vertices with two colours so that every edge joins different colours. Start anywhere, give each neighbour the other colour, and keep going. If an edge ever joins two vertices of the same colour, the graph is not bipartite. That happens exactly when the graph has a cycle of odd length, such as the triangle A, B, C in the default graph.

What is the difference between Kruskal’s and Prim’s algorithm?

Both find a minimum spanning tree. Kruskal sorts all edges by weight and adds each one that does not close a cycle, so the tree can grow in several pieces that join up. Prim starts from one vertex and repeatedly adds the cheapest edge leaving the tree built so far. They give the same total weight, and the same tree when all weights are different.

Written and reviewed by our editorial team. Last updated . Method and sources: how these numbers are computed.