Graphs as Models: Nodes, Edges and Euler's Seven Bridges

What do the Bridges of Königsberg, a rail map and a social network share, and why does adding a weight to an edge change the question?

Finger exercises

Short drills on what this video just taught. Write the code, run the checks, and reveal the answer only if you are stuck.

0 / 5 passed

Exercise 1 of 5

Count the bridges at each land mass

Euler's model of Königsberg has four land masses as nodes and seven bridges as undirected edges, given as pairs in bridges. Count how many bridge ends touch each land mass (an edge adds one to each of its two nodes) and store the counts in a dictionary degree mapping each land-mass name to its count.

bridges = [('Central', 'North'), ('Central', 'North'),
           ('Central', 'South'), ('Central', 'South'),
           ('Central', 'East'), ('East', 'North'), ('East', 'South')]
degree = {}
# Count the bridges at each land mass.

bridges = [('Central', 'North'), ('Central', 'North'),
           ('Central', 'South'), ('Central', 'South'),
           ('Central', 'East'), ('East', 'North'), ('East', 'South')]
degree = {}
# Count the bridges at each land mass.

Python runs in your browser

⌘/Ctrl + Enter runs

is a dict with the four land masses

counts both ends of every bridge

matches Euler's counts

←Previous Overlapping Subproblems and the Memoized Knapsack Next Coding a Graph in Python: Node, Edge, Digraph and Graph →