Vertices, edges, degrees
The basic vocabulary of graphs, directed or not: vertex, edge, arc, loop, simple graph, order, size, degree, the handshaking lemma and degree sequences.
- 26 cards
- 4 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
A few cards from the deck
Graph: what is it?
Show the answer
A set of vertices and edges, each edge joining two vertices (or a vertex to itself).
It models anything that links objects: cities and roads, accounts and follows, tasks and dependencies.
What does this program print? It counts the degree of each vertex.
```python
aretes = [("A","B"),("A","C"),("B","C"),("C","D"),("D","D")]
deg = {}
for u, v in aretes:
deg[u] = deg.get(u, 0) + 1
deg[v] = deg.get(v, 0) + 1
print(deg)`{'A': 2, 'B': 2, 'C': 3, 'D': 3}{'A': 2, 'B': 2, 'C': 3, 'D': 2}{'A': 2, 'B': 2, 'C': 3, 'D': 1}{'A': 2, 'B': 2, 'C': 2, 'D': 2}
Show the answer
{'A': 2, 'B': 2, 'C': 3, 'D': 3}The loop D-D goes through the
forbody once withuandvboth equal to D, so D gains 2, plus 1 for the edge C-D. The degree of D is 3.In an undirected graph with m edges, the sum of the degrees of the vertices is ….
Show the answer
In an undirected graph with m edges, the sum of the degrees of the vertices is 2m.
Each edge is counted once at each of its two ends.
Order and size of a graph: what is it?
Show the answer
The order is the number of vertices, written n; the size is the number of edges (or arcs), written m.
Algorithm costs are written with these two numbers, for example O(n + m) for a traversal.